\section{Introduction}\label{sec:Intro}

Machine learning is built on training data~\citep{Reddi:2021:DataEngineering}.
Without good training data, nothing else works.
How modern models learn from and use training data is increasingly opaque~\citep{Koh:2017:Understanding,Zhang:2021:UnderstandingGeneralizationStillRequires,Xiang:2022:IncreasinglyUnexplainableAI}.
Regarding state-of-the-art black-box models, \citet{Yampolskiy:2020:UnexplainableAI} 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~\citep{Black:2021:LeaveOneOut}.
Today's uncurated, internet-derived datasets
commonly contain numerous anomalous instances~\citep{Pleiss:2020:IdentifyingMislabeledData}.
These anomalies can arise from multiple potential sources.
For example, training data anomalies may have a natural cause such as
distribution shift~\citep{Rousseeuw:1997:RobustRegressionOutlierDetection,Yang:2021:OodSurvey},
measurement error,
or
non-representative samples drawn from the tail of the data distribution
\citep{Huber:1981:RobustStatistics,Feldman:2020:LearningRequiresMemorization,Jiang:2021:CScore}.
Anomalous training instances also occur due to human or algorithmic labeling errors -- even on well-known, highly-curated datasets~\citep{Ekambaram:17:LabelNoiseDatasets}.
Malicious adversaries can insert anomalous poison instances into the training data with the goal of manipulating specific model predictions~\citep{Biggio:2012:Poisoning,Chen:2017:Targeted,Shafahi:2018:PoisonFrogs,Hammoudeh:2023:CertifiedRegression}.
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~\citep{Bender:2021:StochasticParrots}.
Models trained on these huge public datasets encode and exhibit biases based on protected characteristics, including gender, race, religion, and disability~\citep{Basta:2019:GenderBiasWordEmbeddings,Kurita:2019:BiasedWordEmbeddings,Tan:2019:WordRepresentationBias,Zhang:2020:BiasClinicalWordEmbedding,Hutchingson:2020:NlpBiasDisabilities}.
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~\citep{Angwin:2016:CompasPropublica}.

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:
\begin{enumerate}
  \setlength{\itemsep}{0pt}
  \item Is a prediction well-supported by the training data, or was the prediction just random?
  \item Which portions of the training data improve a prediction? Which portions make it worse?
  %
  %
  \item Which instances in the training set caused the model to make a specific prediction?
  %
  %
  %
\end{enumerate}

One strategy to address basic questions like those above is to render them moot by exclusively using simple, transparent model classes~\citep{Lipton:2019:MythosOfInterpretability}.
Evidence exists that this ``interpretable-only'' strategy may be appropriate in some settings~\citep{Knight:2017:DarkSecretAI}.
However, even interpretable model classes can be grossly affected by training data issues~\citep{Huber:1981:RobustStatistics,Cook:1982:NoteOutlierModel,Cook:1982:InfluenceRegression}.
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.

\subsection{Relating Models and Their Training Data}

All model decisions are rooted in the training data. %
Training data \textit{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~\citep{Shapley:1988:ShapleyValue,Koh:2017:Understanding,Yeh:2018:Representer,Pruthi:2020:TracIn}.
Essentially, influence analysis tries to answer the question: \textit{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~\citep{Jaeckel:1972:InfinitesimalJackknife,Cook:1982:InfluenceRegression}.
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~\citep{Hogg:1979:StatisticalRobustness,Rousseeuw:1994:LeastMedianSquares}.

Since these early days, machine learning models have grown substantially in complexity and opacity~\citep{Devlin:2019:Bert,Krizhevsky:2012,Dosovitskiy:2021:VisionTransformer}.
Training datasets have also exploded in size~\citep{Black:2021:LeaveOneOut}.
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~\citep{Blum:1992:TrainingNpComplete}.

In practice, influence may not need to be measured exactly.
\keyword{Influence estimation} methods provide an approximation of training instances' true influence.
Influence estimation is generally much more computationally efficient and is now the approach of choice~\citep{Schioppa:2022:ScaledUpInfluenceFunctions}.
However, modern influence estimators achieve their efficiency via various assumptions about the model's architecture and learning environment~\citep{Koh:2017:Understanding,Yeh:2018:Representer,Ghorbani:2019:DataShapley}.
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~\citep{Pruthi:2020:TracIn}.

\subsection{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~\citep{Schioppa:2022:ScaledUpInfluenceFunctions}.

In the remainder of this paper, we first standardize the general notation used throughout this work (Sec.~\ref{sec:Preliminaries}).
Section~\ref{sec:EstimatorOverview} 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~\ref{sec:Estimators:RetrainBased} and~\ref{sec:Estimators:GradientBased} 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~\ref{sec:Applications} reviews various learning tasks where influence analysis has been applied.
We provide our perspective on future directions for influence analysis research in Section~\ref{sec:FutureDirections}.
 %
\section{General Notation}%
\label{sec:Preliminaries}

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.\footnote{Supplemental Table~\ref{tab:App:Nomenclature:MethodParams} provides a reference for all notation specific to a single influence analysis method.}
Supplemental Section~\ref{sec:App:Nomenclature} provides a full nomenclature reference.

Let $\setint{r}$ denote the set of integers $\set{1, \ldots, r}$.
${A \simN{m} 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 \keyword{singleton} set~$A$ (i.e., ${\abs{A} = 1}$), the sampling notation is simplified to ${A \simOne B}$.
Let $\powerSet{A}$ denote the \keyword{power set} of any set~$A$.
Set subtraction is denoted ${A \setminus B}$.
For singleton~${B = \set{b}}$, set subtraction is simplified to ${A \setminus b}$.

The \keyword{zero vector} is denoted~$\vec{0}$ with the vector's dimension implicit from context.
$\ind{a}$ is the \keyword{indicator function}, where ${\ind{a} = 1}$ if predicate~$a$ is true and~0 otherwise.

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

\keyword{Model} $\func{f}{\mathcal{X}}{\mathcal{Y}}$ is parameterized by ${\theta \in \real^{\dimW}}$, where ${p \coloneqq \abs{\theta}}$; $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 \keyword{loss function} $\func{\ell}{\mathcal{Y} \times \mathcal{Y}}{\mathbb{R}}$.
Let \eqsmall{${\risk{z}{\theta} \coloneqq \ell\big(\decFunc{x}{\theta}, y \big)}$} denote the \keyword{empirical risk} 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 \keyword{initial parameters}~${\wT[0]}$, the optimizer returns at the end of each iteration, ${t \in \setint{T}}$, updated model parameters~$\wT$, where $\wT$ is generated from previous parameters~$\wT[t - 1]$, loss function~$\ell$, \keyword{batch} ${\batchT \subseteq \mathcal{D}}$, \keyword{learning rate} ${\lrT > 0}$, and \keyword{weight decay} ($L_2$) strength ${\wdecay \geq 0}$.
Training gradients are denoted
${\nabla_{\w} \risk{\zIBase}{\wT}}$.
The training set's \keyword{empirical risk Hessian} for iteration $t$ is denoted \eqsmall{${\hessT \coloneqq \frac{1}{n} \sum_{\zIBase \in \mathcal{D}} \gradW^{2} \risk{\zIBase}{\wT}}$}, with the corresponding \keyword{inverse risk Hessian} denoted~\eqsmall{${(\hessT)^{-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 \setZi}$.
Let ${D \subset \mathcal{D}}$ denote an alternate training set, and denote model parameters trained on~$D$ as~$\wTSubBase{D}$.
For example, $\wTSub[T]{i}$ are the final parameters for a model trained on all of~$\mathcal{D}$ except training instance~${\zIBase \in \mathcal{D}}$ (note this alternate notation for compactness).
When training on all of the training data, subscript~$\mathcal{D}$ is dropped, i.e., ${\wT \equiv \wTSubBase{\mathcal{D}}}$.
 %
\section{Overview of Influence and Influence Estimation}%
\label{sec:EstimatorOverview}

As explained in Section~\ref{sec:Intro}, 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., $\decFunc{\X_{\teStr}}{\wT[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 $\risk{\z_{\teStr}}{\wT[T]}$.
Negative influence means that the training instance(s) make the quality measure worse.
Training instances with positive influence are referred to as \keyword{proponents} or \keyword{excitatory examples}.
Training instances with negative influence are called \keyword{opponents} or \keyword{inhibitory examples}~\citep{Koh:2017:Understanding,Yeh:2018:Representer}.

Highly expressive, overparameterized models remain functionally black boxes~\citep{Koh:2017:Understanding}.
Understanding why a model behaves in a specific way remains a significant challenge~\citep{Belle:2021:PrinciplesXAI},
and
the inclusion or removal of even a single training instance can drastically change a trained model's behavior~\citep{Rousseeuw:1994:LeastMedianSquares,Black:2021:LeaveOneOut}.
In the worst case, quantifying one training instance's influence may require repeating all of training.

Since measuring influence \textit{exactly} may be intractable or unnecessary, \textit{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.

\subsection{Pointwise Training Data Influence}%
\label{sec:EstimatorOverview:PointwiseInfluence}

\keyword{Pointwise 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 $\func{\mathcal{I}}{\mathcal{Z} \times \mathcal{Z}}{\mathbb{R}}$ with the pointwise influence of training instance~$\zIBase$ on test instance~$\z_{\teStr}$ denoted $\baseInfFunc{\influence}{\zIBase}{\z_{\teStr}}$.
Pointwise influence estimates are denoted ${\baseInfFunc{\infEstSym}{\zIBase}{\z_{\teStr}} \in \mathbb{R}}$.

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

\subsubsection{Early Pointwise Influence Analysis}%
\label{sec:EstimatorOverview:PointwiseInfluence:EarlyMethods}

\begin{figure}[t]
  \centering
  %
\begin{tikzpicture}
    \begin{axis}
      [
        hide axis,
        xmin=0,
        xmax=1,
        ymin=0,
        ymax=1,
        scale only axis,width=1mm, %
        legend cell align={left},              %
        legend style={font=\footnotesize},
        legend columns=5,
        legend image post style={scale=0.65}, %
        %
        legend style={/tikz/every even column/.append style={column sep=0.5cm}}
      ]
      %
      %
      %
      \addlegendimage{only marks,mark=square*,blue!30,draw=blue,mark size=3.5pt}
      \addlegendentry{Inlier}

      \addlegendimage{only marks,mark=*,red!30,draw=red,mark size=3.5pt,line width=0.6pt}
      \addlegendentry{Outlier}

      %
      %
      %

      %
      %
      %

      %
      \addlegendimage{dashed, domain=0:5, smooth, color=ForestGreen, line width=1.2pt, opacity=1}
      \addlegendentry{Least Squares Inliers Only}

      \addlegendimage{domain=0:5, smooth, color=BrickRed, line width=1.2pt, opacity=1}
      \addlegendentry{Least Squares All}
    \end{axis}%
\end{tikzpicture}%

  \vspace{8pt}
  %
\newcommand{2in}{2in}
\newcommand{\plotWidth}{2in}
\newcommand{\footnotesize}{\footnotesize}

\newcommand{0.5}{0.5}
\newcommand{5.5}{5.5}
\newcommand{0.7pt}{0.7pt}
\begin{tikzpicture}
  \pgfplotstableread[col sep=comma] {plots/src/data/linear_reg.csv}\thedata
  \begin{axis}
     [
       scale only axis,%
       width={2in},
       height={\plotWidth},
       %
       xmin={0.5},
       xmax={5.5},
       xtick={1,2,3,4,5},
       %
       x tick label style={font=\footnotesize,align=center},
       xlabel={\footnotesize$x$},
       xmajorgrids,
       %
       ymin=0.5,
       ymax=4.5,
       ylabel={\footnotesize$y$},
       ytick distance={1},
       ymajorgrids,
       y tick label style={font=\footnotesize,align=center},
       point meta=explicit,
       %
       %
       %
       %
       %
       %
       %
       %
       %
       %
       %
       %
       clip mode=individual,                %
       scatter/classes={
         0={mark=square*,blue!30,draw=blue,mark size=2.0pt},
         1={mark=*,red!30,draw=red,mark size=2.0pt,line width=0.6pt}
       },
     ]

     %
     \addplot[dashed, domain=0.5:5.5, smooth, color=ForestGreen, line width=0.7pt, opacity=1] { 1.997 * x + 0.007 } {};    %
     \label{leg:EstimatorOverview:PointwiseInfluence:EarlyMethods:LSq:InDist}

     %
     \addplot[domain=0.5:5.5, smooth, color=BrickRed, line width=0.7pt, opacity=1] { -0.3797 * x + 3.477 } {};    %
     \label{leg:EstimatorOverview:PointwiseInfluence:EarlyMethods:LSq:All}

     %
     \addplot[
       %
       %
       %
       scatter,
       only marks,
       %
       %
       line width=0.2,
       %
       mark size=0.7pt,
       %
       %
       %
     ]
     table[x index=0,y index=1, meta index=2] {\thedata};
     \label[0]{leg:EstimatorOverview:PointwiseInfluence:EarlyMethods:Clean}
     \label[1]{leg:EstimatorOverview:PointwiseInfluence:EarlyMethods:Outlier}
  \end{axis}
\end{tikzpicture}
   \caption{%
    \textbf{Outlier Pointwise Influence on Least-Squares Regression}:
    Influence of a single outlier
    %
    (\ref{leg:EstimatorOverview:PointwiseInfluence:EarlyMethods:Outlier})
    on a least-squares model where in-distribution data
    (\ref{leg:EstimatorOverview:PointwiseInfluence:EarlyMethods:Clean})
    are generated from
    linear distribution ${y = 2 x}$.
    %
    The single outlier sample
    %
    (${x = 5}$ \& ${y = 1.2}$)
    influences the inlier-only least-squares linear model
    (\ref{leg:EstimatorOverview:PointwiseInfluence:EarlyMethods:LSq:InDist})
    substantially such that a least-squares model trained on all instances
    (\ref{leg:EstimatorOverview:PointwiseInfluence:EarlyMethods:LSq:All})
    predicts all training $y$~values poorly.
    Adapted from \citet[Fig.~2(b)]{Rousseeuw:1997:RobustRegressionOutlierDetection}.
    %
  }
  \label{fig:EstimatorOverview:PointwiseInfluence:EarlyMethods:LeastSquares}
\end{figure}

The earliest notions of pointwise influence emerged out of robust statistics -- specifically the analysis of training outliers' effects on linear regression models~\citep{Cook:1977:DetectionInfluence}.
Given training set~$\mathcal{D}$, the least-mean squares linear model parameters are%
\footnote{%
  For simplicity, the bias term is considered part of $\theta$.%
}%
\begin{equation}%
  \label{eq:EstimatorOverview:LeastSquares}
  \w^{*}
    \coloneqq
      \argmin_{\theta}
        \frac{1}%
             {\abs{\mathcal{D}}}
        \sum_{(\xI,\yI) \in \mathcal{D}}
          \left( \yI - \theta^{\intercal}\xI \right)^2
  \text{.}
\end{equation}
\noindent
Observe that this least-squares estimator has a \keyword{breakdown point} of~0~\citep{Rousseeuw:1994:LeastMedianSquares}.
This means that least-squares regression is completely non-robust where a single training data outlier can shift model parameters~$\w^{*}$ arbitrarily.
For example, Figure~\ref{fig:EstimatorOverview:PointwiseInfluence:EarlyMethods:LeastSquares} visualizes how a single training data outlier~(\ref{leg:EstimatorOverview:PointwiseInfluence:EarlyMethods:Outlier}) 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~\citep{Srikantan:1961:SingleOutlier,Tietjen:1973:TestingSingleOutlier}.
A training outlier can be defined as the training instance with the largest negative influence on prediction $\decFunc{\X_{\teStr}}{\w^{*}}$.
Intuitively, each training instance's pointwise influence can be measured by training ${n \coloneqq \abs{\mathcal{D}}}$ models, where each model's training set leaves out a different training instance.
These $n$~models would then be compared to identify the outlier.%
\footnote{%
  Section~\ref{sec:Estimators:RetrainBased:LeaveOneOut} 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, \citet{Srikantan:1961:SingleOutlier}, \citet{Snedecor:1968:StatisticalMethods}, and \citet{Ellenberg:1976:SingleOutlierRegression} 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 \keyword{residual},~$\abs{\yI - {\w^{*}}^{\intercal} \xI}$.
However, \citet{Cook:1982:InfluenceRegression} 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, \citet{Rousseeuw:1994:LeastMedianSquares} replaces Eq.~\eqref{eq:EstimatorOverview:LeastSquares}'s mean operation with median;
this simple change increases the breakdown point of model parameters~$\w^{*}$ to the maximum value,~50\%.
In addition, multiple robust loss functions have been proposed that constrain or cap outliers' pointwise influence~\citep{Huber:1964:RobustEstimation,Beaton:1974:TukeyBiweight,Dennis:1978:WelschLoss,Leclerc:1989}.

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.

\subsubsection{Modern Pointwise Influence Analysis}%
\label{sec:EstimatorOverview:PointwiseInfluence:ModernMethods}

\begin{figure}[t]
  \centering
  %
  \makebox[\textwidth][c]{%
  \newcommand{\citeFig}[1]{}
  {
    \tikzset{
      my rounded corners/.append style={rounded corners=2pt},
    }
    %
    \scriptsize
    \begin{forest}
      %
      %
      %
      %
      %
      %
      %
      %
      %
      %
      %
      %
      %
      %
      %
      %
      %
      /tikz/every node/.append style={font=\scriptsize},
      for tree={
        line width=1pt,
        if={level()<4}{
          my rounded corners,
          draw=linecol,
        }{},
        %
        if level=0{%
          forked edges,
          l sep+=0.35cm,  %
          s sep+=0.35cm,  %
          align=center,
          %
          %
          %
          %
          %
          %
          %
          %
        }{%
          if level=1{%
            l 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={
                      %
                      %
                      \noexpand\path[\forestoption{edge}] (!to tier=parting ways.parent anchor) |- (.child anchor)\forestoption{edge label};
                    },
                    %
                    for descendants={
                      no edge,
                    },
                  },
                }{
                  %
                },
              },
            },
          },
        },%
      },
      [Influence Analysis Methods
        [Retraining-Based %
          %
          %
          [{},nice empty nodes,calign=child, calign child=2
             %
             %
             [ Leave-One-Out\citeFig{Cook:1982:InfluenceRegression}
                [
                  [ \knn{}~\loo{}{}\citeFig{Jia:2021:ScalabilityVsUtility} ]
                  [ \textsc{LeafRefit}{}\citeFig{Sharchilev:2018:TreeInfluence} ]
                  [ Inf.\ Sketching\citeFig{Wojnowicz:2016:InfluenceSketching} ]
                ]
             ]
             [ \textsc{Downsampling}{}\citeFig{Feldman:2020:InfluenceEstimation}
              [
                [ C\=/Score\citeFig{Jiang:2021:CScore} ]
                [ Generative\citeFig{Van:2021:Memorization} ]
              ]
             ]
             [ Shapley Value\citeFig{Shapley:1953}
               [
                 [ TMC\=/Shapley{}\citeFig{Ghorbani:2019:DataShapley} ]
                 [ G\=/Shapley{}\citeFig{Ghorbani:2019:DataShapley} ]
                 [ \knn{}~Shapley{}\citeFig{Jia:2019:KnnShapley} ]
                 [ Beta Shapley{}\citeFig{Kwon:2022:BetaShapley} ]
                 [ AME{}\citeFig{Lin:2022:InfluenceRandomizedExperiments} ]
                 [ SHAP{}\citeFig{Lundberg:2017:SHAP} ]
                 [ Neuron Shapley\citeFig{Ghorbani:2020:NeuronShapley} ]
                 %
               ]
             ]
          ]
        ]
        [Gradient-Based
           [Static
              [ Influence Func.\citeFig{Koh:2017:Understanding}
                [
                  [ \textsc{FastIF}{}\citeFig{Guo:2021:FastIF} ]
                  [ Scaled IF\citeFig{Schioppa:2022:ScaledUpInfluenceFunctions} ]
                  [ \textsc{LeafInfluence}{}\citeFig{Sharchilev:2018:TreeInfluence} ]
                  [ Group IF\citeFig{Koh:2019:GroupEffects} ]
                  [ Second-Order\citeFig{Basu:2020:OnSecond} ]
                  [ RelatIF\citeFig{Barshan:2020:RelatIF} ]
                  [ Renorm.\ IF\citeFig{Hammoudeh:2022:GAS} ]
                ]
              ]
              [ Representer Pt.\citeFig{Yeh:2018:Representer}
                [
                  [ RPS\=/LJE\citeFig{Sui:2021:LocalJacobianRepPt} ]
                  [ TREX{}\citeFig{Brophy:2022:TreeInfluence} ]
                ]
              ]
           ]
           [Dynamic
              [TracIn{}\citeFig{Pruthi:2020:TracIn}
                [
                  [ \tracin{}CP{}\citeFig{Pruthi:2020:TracIn} ]
                  [ \tracin{}RP{}\citeFig{Pruthi:2020:TracIn} ]
                  [ \tracin{}\=/Last{}\citeFig{Pruthi:2020:TracIn} ]
                  [ VAE\=/\tracin{}{}\citeFig{Kong:2021:VaeTracIn} ]
                  [ \tracin{}AD{}\citeFig{Thimonier:2022:TracInAD} ]
                  [ \tracin{}WE{}\citeFig{Yeh:2022:FirstBetterLast} ]
                  [ BoostIn{}\citeFig{Brophy:2022:TreeInfluence} ]
                  [ \textsc{GAS}{}\citeFig{Hammoudeh:2022:GAS} ]
                ]
              ]
              [\textsc{HyDRA}{}\citeFig{Chen:2021:Hydra}
                [
                  [ SGD\=/Influence\citeFig{Hara:2019:SgdInfluence} ]
                ]
              ]
           ]
        ]
        %
        %
        %
        %
        %
        %
        %
        %
        %
     ]
      %
      %
      %
      %
    \end{forest}
  }
 %
}

  \caption{%
    \textbf{Influence Analysis Taxonomy}:
    Categorization of the seven primary pointwise influence analysis methods.
    Section~\ref{sec:Estimators:RetrainBased} details the three primary retraining-based influence methods,
    leave-one-out (Sec.~\ref{sec:Estimators:RetrainBased:LeaveOneOut}),
    \textsc{Downsampling}{} (Sec.~\ref{sec:Estimators:RetrainBased:Feldman}),
    and
    Shapley value (Sec.~\ref{sec:Estimators:RetrainBased:Shapley}).
    Section~\ref{sec:Estimators:GradientBased} details gradient-based static estimators
    influence functions (Sec.~\ref{sec:Estimators:GradientBased:Static:IF})
    and
    representer point (Sec.~\ref{sec:Estimators:GradientBased:Static:RepresenterPoint})
    as well as dynamic estimators
    TracIn{} (Sec.~\ref{sec:Estimators:GradientBased:Dynamic:TracIn}) and
    \textsc{HyDRA}{} (Sec.~\ref{sec:Estimators:GradientBased:Dynamic:HyDRA}).
    Closely-related and derivative estimators are shown as a list below their parent method.
    See supplemental Table~\ref{tab:App:Nomenclature:InfDef} for the formal mathematical definition of all influence methods and estimators.
    Due to space, each method's citation is in supplemental Table~\ref{tab:App:Nomenclature:Methods}.
  }%
  \label{fig:Estimator:Taxonomy}
\end{figure}

Figure~\ref{fig:Estimator:Taxonomy} 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:
\begin{itemize}
  \item \keyword{Retraining-Based Methods}: Measure the training data's influence by repeatedly retraining model~$f$ using different subsets of training set~$\mathcal{D}$.

  \item \keyword{Gradient-Based Influence Estimators}: Estimate influence via the alignment of training and test instance gradients either throughout or at the end of training.
\end{itemize}
\noindent
An in-depth comparison of these influence analysis methods requires detailed analysis so we defer the extensive discussion of these two categories to Sections~\ref{sec:Estimators:RetrainBased} and~\ref{sec:Estimators:GradientBased}, respectively. %
Table~\ref{tab:InfluenceEstimators:Comparison} summarizes the key properties of Figure~\ref{fig:Estimator:Taxonomy}'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.

\afterpage{%
  \clearpage
  \newpage
  \begin{table}[t!]
    \centering
    \caption{%
      \textbf{Influence Analysis Method Comparison}:
      Comparison of the complexity, assumptions, strengths, and limitations of the seven primary influence estimators detailed in Sections~\ref{sec:Estimators:RetrainBased} and~\ref{sec:Estimators:GradientBased}.
      Recall that $n$, $p$, and $T$ are the training-set size, model parameter count, and training iteration count, respectively.
      LOO{} is the leave\=/one\=/out influence.
      ``Full time complexity" denotes the time required to calculate influence for the first test instance; ``incremental complexity" is the added time required for each subsequent test instance.
      ``Storage complexity" represents the amount of memory required to persistently save any additional model parameters needed by the influence method.
      For \textsc{HyDRA}{} and the three retraining-based methods, the storage complexity is implementation dependent and is marked with an asterisk.
      We report each method's worst-case storage complexity;
      for the retraining-based methods, this worst-case storage complexity yields the best-case incremental complexity.
      Static, gradient-based estimators -- influence functions and representer point -- require no additional storage.
      Differentiability encompasses both model~$f$ and loss function~$\ell$ except in the case of representer point where only the loss function must be differentiable.
      All criteria below are discussed in detail alongside the description of each method.
      %
    }
    \label{tab:InfluenceEstimators:Comparison}
    {
      \footnotesize%
      %
\renewcommand{\arraystretch}{1.2}
\setlength{\dashlinedash}{0.4pt}
\setlength{\dashlinegap}{1.5pt}
\setlength{\arrayrulewidth}{0.3pt}
\newcommand{\cdashline{1-8}}{\cdashline{1-8}}

\newcommand{$\bigO{2^{\nTr}\,\nItr}$}{$\bigO{2^{n}\,T}$}
\newcommand{$\bigO{2^{\nTr}}$}{$\bigO{2^{n}}$}
\newcommand{$\bigO{2^{\nTr}\,\dimW}$}{$\bigO{2^{n}\,p}$}
\newcommand{$\bigO{\nFeldModel\dimW}$}{$\bigO{\nFeldModelp}$}

\newcommand{0}{0}

\newcommand{\SectionRow}{
  Section reference
  & \ref{sec:Estimators:RetrainBased:LeaveOneOut}
  & \ref{sec:Estimators:RetrainBased:Feldman}
  & \ref{sec:Estimators:RetrainBased:Shapley}
  & \ref{sec:Estimators:GradientBased:Static:IF}
  & \ref{sec:Estimators:GradientBased:Static:RepresenterPoint}
  & \ref{sec:Estimators:GradientBased:Dynamic:TracIn}
  & \ref{sec:Estimators:GradientBased:Dynamic:HyDRA}
}

\newcommand{\checkmark}{\checkmark}
\begin{tabular}{@{}lccccccc@{}}
  \toprule
  %
                            %
                            & \multicolumn{3}{c}{\multirow{2}{*}{Retraining-Based}} &  \multicolumn{4}{c}{Gradient-Based}  \\\cmidrule(lr){5-8}
                            &            &            &              & \multicolumn{2}{c}{Static} & \multicolumn{2}{c}{Dynamic} \\\cmidrule(lr){2-4}\cmidrule(lr){5-6}\cmidrule(lr){7-8}
                            & LOO{}     & \textsc{Downsamp}.{} & Shapley      & Inf.\ Func.  & Rep.\ Pt.   & TracIn{} & \textsc{HyDRA}{}      \\
  \midrule
                          %
  \SectionRow{} \\\cdashline{1-8}
  Full time complexity      & $\bigO{\nTr\nItr}${}  & $\bigO{\nFeldModel\nItr}$    & $\bigO{2^{\nTr}\,\nItr}${}  & $\bigO{\nTr \dimW}$      & $\bigO{\nTr}$      & $\bigO{\nTr\dimW\nItr}$  & $\bigO{\nTr\dimW\nItr}${}     \\\cdashline{1-8}
  Incremental complexity    & $\bigO{\nTr}${}   & $\bigO{\nFeldModel}${}   & $\bigO{2^{\nTr}}${}   & $\bigO{\nTr \dimW}$      & $\bigO{\nTr}$      & $\bigO{\nTr\dimW\nItr}$  & $\bigO{\nTr\dimW}${}      \\\cdashline{1-8}
  Space complexity          & $\bigO{\nTr + \dimW}$  & $\bigO{\nTr + \dimW}$  & $\bigO{\nTr + \dimW}$    & $\bigO{\nTr + \dimW}$    & $\bigO{\nTr + \dimW}$   & $\bigO{\nTr + \dimW}$ & $\bigO{\nTr\dimW}${}      \\\cdashline{1-8}
  Storage complexity        & $\bigO{\nTr \dimW}${}* & $\bigO{\nFeldModel\dimW}${}* & $\bigO{2^{\nTr}\,\dimW}${}* & 0   & 0  & $\bigO{\dimW\nItr}$   & $\bigO{\dimW\nItr + \nTr\dimW}${}*   \\\cdashline{1-8}
  Assumes differentiable?   &            &            &              & \checkmark{}        & \checkmark{}*      & \checkmark{}     & \checkmark{}          \\\cdashline{1-8}
  Assumes convexity?        &            &            &              & \checkmark{}        & \checkmark{}       &           &                \\\cdashline{1-8}
  Assumes stationarity?     &            &            &              & \checkmark{}        & \checkmark{}       &           &                \\\cdashline{1-8}
  Assumes linear model?     &            &            &              &              & \checkmark{}       &           &                \\\cdashline{1-8}
  Optimizer specific?       &            &            &              &              &             & \checkmark{}     & \checkmark{}          \\\cdashline{1-8}
  Uses Hessian?             &            &            &              & \checkmark{}        &             &           & \checkmark{}          \\\cdashline{1-8}
  Any model class?          & \checkmark{}      & \checkmark{}      & \checkmark{}        &              &             &           &                \\\cdashline{1-8}
  Estimates LOO{}?         & \checkmark{}      & \checkmark{}      & \checkmark{}        & \checkmark{}        &             &           & \checkmark{}          \\\cdashline{1-8}
  Group influence?          &            & \checkmark{}      & \checkmark{}        & \checkmark{}        &             &           &                \\\cdashline{1-8}
  %
  Hyperparam.\ sensitive?   &            &            &              & \checkmark{}        &             &           & \checkmark{}          \\\cdashline{1-8}
  Generative models?        &            & \checkmark{}      & \checkmark{}        &              &             & \checkmark{}     &                \\\cdashline{1-8}
  High upfront cost?        & \checkmark{}      & \checkmark{}      & \checkmark{}        &              &             &           & \checkmark{}          \\\cdashline{1-8}
  High instance cost?       &            &            & \checkmark{}        & \checkmark{}        &             & \checkmark{}     &                \\\cdashline{1-8}
  Amortizable?              & \checkmark{}      & \checkmark{}      & \checkmark{}        &              &             & \checkmark{}     & \checkmark{}          \\
  \bottomrule
\end{tabular}
 %
    }
  \end{table}
  \clearpage
  \newpage
}

\subsection{Alternative Perspectives on Influence and Related Concepts}%
\label{sec:EstimatorOverview:AlternativeDefinitions}

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.

\noindent%
(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~\citep{Feldman:2020:InfluenceEstimation}, where group members
have a total effect much larger than the sum of their individual effects~\citep{Basu:2020:OnSecond,Das:2021:DataSubsetInfluence,Hammoudeh:2022:GAS}.
\keyword{Group influence} 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{\influence}$.
For example, given some test instance~$\z_{\teStr}$, the entire training set's group influence and group influence estimate are denoted $\baseInfFunc{\influence}{\mathcal{D}}{\z_{\teStr}}$ and $\baseInfFunc{\infEstSym}{\mathcal{D}}{\z_{\teStr}}$, 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~\citep{Koh:2019:GroupEffects}.
Put simply, the true influence of a coherent group is \textit{more than the sum of its parts}, or formally, for coherent ${D \subseteq \mathcal{D}}$, it often holds that
\begin{equation}%
  \label{eq:EstimatorOverview:GroupInfluence:Bound}%
  \abs{%
    \baseInfFunc{\influence}{D}{\z_{\teStr}}%
  }%
  >
    \sum_{\zIBase \in D}
      \abs{%
        \baseInfFunc{\influence}{\zIBase}%
                {\z_{\teStr}}%
      }%
  \text{.}
\end{equation}
\noindent
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.

\noindent%
(2)~%
\keyword{Joint influence} extends influence to consider \textit{multiple test instances} collectively~\citep{Jia:2022:CertifiedKNN,Chen:2022:BaggingTrainingSetAttacks}.
These test instances may be a specific subpopulation within the test distribution -- for example in \keyword{targeted data poisoning attacks}~\citep{Jagielski:2021:Subpopulation,Wallace:2021}.
The test instances could also be a representative subset of the entire test data distribution -- for example in \keyword{core-set selection}~\citep{Borsos:2020:BilevelCoresetSelection} or \keyword{indiscriminate poisoning attacks}~\citep{Biggio:2012:Poisoning,Fowl:2021:Adversarial}.

Most (pointwise) influence analysis methods are \keyword{additive} meaning for target set~${\trainSet_{\teStr} \subseteq \mathcal{Z}}$, the joint (pointwise) influence simplifies to
\begin{equation}\label{eq:Estimators:MultitargetInfluence}
  \baseInfFunc{\influence}{\zIBase}{\trainSet_{\teStr}}
    =
      \sum_{\z_{\teStr} \in \trainSet_{\teStr}}
        \baseInfFunc{\influence}{\zIBase}%
                {\z_{\teStr}}
  \text{.}
\end{equation}
\noindent
Additivity is not a requirement of influence analysis, and there are provably non-additive influence estimators~\citep{Yan:2021:ShapleyCore}.

\noindent%
(3)~%
Overparameterized models like deep networks are capable of achieving near-zero training loss in most settings~\citep{Bartlett:2020:BenignOverfitting,Feldman:2020:LearningRequiresMemorization,DAmour:2020:Underspecification}.
This holds even if the training set is large and randomly labeled~\citep{Zhang:2017:RethinkingGeneralization,Arpit:2017:DeepMemorization}.
Near-zero training loss occurs because deep models often memorize some training instances.

Both \citet{Pruthi:2020:TracIn} and \citet{Feldman:2020:InfluenceEstimation} separately define a model's \keyword{memorization}\footnote{\citet{Pruthi:2020:TracIn} term ``memorization'' as \keyword{self-influence}. We use \citepos{Feldman:2020:InfluenceEstimation} terminology here since it is more consistent with other work~\citep{Van:2021:Memorization,Kandpal:2022:DeduplicatingPrivacyRisks}.} of training instance~$\zIBase$ as the pointwise influence of $\zIBase$ \textit{on itself}.
Formally
\begin{equation}
  \labelAndRemember{eq:EstimatorOverview:Memorization}{%
    \mem{\zIBase}
    \coloneqq
      \baseInfFunc{\influence}{\zIBase}{\zIBase}
  }
  \approx
    \baseInfFunc{\infEstSym}{\zIBase}{\zIBase}
  \text{.}
\end{equation}

\noindent
(4)~%
\keyword{Cook's distance} measures the effect of training instances on the model parameters themselves~\citep[Eq.~(5)]{Cook:1977:DetectionInfluence}.
Formally, the pointwise Cook's distance of ${\zIBase \in \mathcal{D}}$ is
\begin{equation}
  \labelAndRemember{eq:EstimatorOverview:CooksDistance:Pointwise}{%
    \infCookFunc{\zIBase}
      \coloneqq
        \wT[T]
        -
        \wTSub[T]{\trIdx}
  }%
  \text{.}
\end{equation}
\noindent%
Eq.~\eqref{eq:EstimatorOverview:CooksDistance:Pointwise} trivially extends to groups of training instances where for any ${D \subseteq \mathcal{D}}$
\begin{equation}
  %
  \infCookFunc{D}
    \coloneqq
      \wT[T]
      -
      \wFinSubBase{\mathcal{D} \setminus D}
  %
  \text{.}
\end{equation}
Cook's distance is particularly relevant for interpretable model classes where feature weights are most transparent.
This includes linear regression~\citep{Rousseeuw:1997:RobustRegressionOutlierDetection,Wojnowicz:2016:InfluenceSketching} and decision trees~\citep{Brophy:2022:TreeInfluence}.

\noindent%
(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~\citep{Basu:2021:InfluenceFunctionsFragile}.
\keyword{Expected influence} is the average influence across all possible instantiations within a given model class~\citep{K:2021:RevisitingInfluentialExamples}.
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~\citep{Chen:2017:Targeted,Shafahi:2018:PoisonFrogs,Fowl:2021:Adversarial}.

\noindent%
(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 \keyword{influence ranking} orders (groups of) training instances from most positively influential to most negatively influential.
These rankings are useful in a wide range of applications~\citep{Kwon:2022:BetaShapley}, including data cleaning and poisoning attack defenses as discussed in Section~\ref{sec:Applications}.

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

\section{Retraining-Based Influence Analysis}%
\label{sec:Estimators:RetrainBased}

Training instances can only influence a model if they are used during training.
As Section~\ref{sec:EstimatorOverview:PointwiseInfluence:ModernMethods} 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~\ref{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.

\begin{remark}
  This section treats model training as \keyword{deterministic} 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~\citep{Lin:2022:InfluenceRandomizedExperiments}.
  For simplicity of presentation, expectation over randomness is dropped from the influence and influence estimator definitions below.
\end{remark}

\begin{remark}
  Section~\ref{sec:Preliminaries} 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.
\end{remark}

\begin{remark}%
  \label{rem:Estimators:RetrainBased:TimeComplexity}
  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~$\bigO{\nItr}${}.
  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$.
  %
\end{remark}

\begin{remark}
  It may be possible to avoid full model retraining by using machine unlearning methods capable of certifiably ``forgetting'' training instances~\citep{Guo:2020:CertifiedRemoval,Brophy:2021:MachineUnlearningForests,Nguyen:2022:MachineUnlearningSurvey,Eisenhofer:2022:VerifiableMachineUnlearning}.
  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.
\end{remark}

\subsection{Leave-One-Out Influence}%
\label{sec:Estimators:RetrainBased:LeaveOneOut}

\keyword{Leave-one-out}~(LOO) is the simplest influence measure described in this work.
LOO{} is also the oldest, dating back to \citet{Cook:1982:InfluenceRegression}  %
  %
who term it \keyword{case deletion diagnostics}.

As its name indicates, \keyword{leave-one-out influence} is the change in $\z_{\teStr}$'s risk due to the removal of a single instance,~$\zIBase$, from the training set~\citep{Koh:2017:Understanding,Black:2021:LeaveOneOut,Jia:2021:ScalabilityVsUtility}.
Formally,
\begin{equation}
  \labelAndRemember{eq:Estimators:RetrainBased:LOO}
  {%
    \baseInfFunc{\influence_{\textsc{LOO}}}{\zIBase}{\z_{\teStr}}
    \coloneqq
      \risk{\z_{\teStr}}{\wTSub[T]{\trIdx}}
      -
      \risk{\z_{\teStr}}{\wT[T]}
  }%
  \text{,}
\end{equation}
\noindent
where $\wTSub[T]{\trIdx}$~are the final model parameters when training on subset ${\mathcal{D} \setminus \zIBase}$ and $\wT[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~\citep{Boyd:2004:ConvexOptimization}), 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$.

\subsubsection{Time, Space, and Storage Complexity}%
\label{sec:Estimators:RetrainBased:LeaveOneOut:Complexity}

Training a single model has time complexity~$\bigO{\nItr}${} (see Remark~\ref{rem:Estimators:RetrainBased:TimeComplexity}).
By additivity, training ${(n + 1)}$ models has total time complexity $\bigO{\nTr\nItr}${}.
Since these ${(n + 1)}$ models are independent, they can be trained in parallel.

Pointwise influence analysis always has space complexity of at least~$\bigO{\nTr}${}, i.e.,~the space taken by the $n$~influence values ${\forall_{i} \, \baseInfFunc{\influence}{\zIBase}{\z_{\teStr}}}$.
Training a single model has space complexity~$\bigO{\dimW}${}, where ${p \coloneqq \abs{\theta}}$; this complexity scales linearly with the number of models trained in parallel.
Table~\ref{tab:InfluenceEstimators:Comparison} treats the level of training concurrency as a constant factor, which is why LOO{}'s total space complexity is listed as~$\bigO{\nTr + \dimW}${}.

A naive implementation of LOO{} would train the $n$~additional models and immediately discard them after measuring $\z_{\teStr}$'s~test loss.
This simple version of LOO{} has $\bigO{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 $\bigO{\nTr}${} forward passes -- a huge saving.%
\footnote{%
  LOO{}'s incremental computational cost can be (significantly) reduced in practice via batching.%
}
Note that this amortization of the retraining cost induces an $\bigO{\nTr \dimW}${} storage complexity as listed in Table~\ref{tab:InfluenceEstimators:Comparison}.

\subsubsection{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~\citep{Black:2021:LeaveOneOut}.

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~\citep{Dishkin:2021:DistributedDeepLearning}.
For even the biggest players, it is impractical to train ${(n + 1)}$~such models given huge modern datasets~\citep{Basu:2021:InfluenceFunctionsFragile}.
The climate effects of such retraining also cannot be ignored~\citep{Strubell:2020:EnergyDeepLearning}.

LOO{}'s simple definition in Eq.~\eqref{eq:Estimators:RetrainBased:LOO} is premised on deterministic training.
However, even when training on the \textit{same} data, modern models may have significant predictive variance for a given test instance~\citep{Black:2021:LeaveOneOut}.
This variance makes it difficult to disentangle the effect of an instance's deletion from training's intrinsic variability~\citep{Basu:2021:InfluenceFunctionsFragile}.
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~\citep{Feldman:2020:InfluenceEstimation}.

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.,~\textsc{Downsampling}{} (Sec.~\ref{sec:Estimators:RetrainBased:Feldman}),
influence functions (Sec.~\ref{sec:Estimators:GradientBased:Static:IF}),
\textsc{HyDRA}{} (Sec.~\ref{sec:Estimators:GradientBased:Dynamic:HyDRA})
--
or are very similar to LOO{} --
e.g.,~Shapley value (Sec.~\ref{sec:Estimators:RetrainBased:Shapley}).

\subsubsection{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~\citep{Aha:1991:InstanceBasedLearning}.
For example, \citet{Jia:2021:ScalabilityVsUtility} propose the \keyword{$\kNeigh$NN{} leave-out-one} (\knn{}~\loo{}) estimator, which calculates the LOO{}~influence over a surrogate $k$\=/nearest neighbors classifier instead of over target model~$f$.
\knn{}~\loo{}{} relies on a simple two-step process.
First, the features of test instance~$\z_{\teStr}$ and training set~$\mathcal{D}$ are extracted using a pretrained model.
Next, a $\kNeigh$NN{} classifier's LOO{} influence is calculated exactly~\citep[Lemma~1]{Jia:2021:ScalabilityVsUtility} using these extracted features.
\citeauthor{Jia:2021:ScalabilityVsUtility} prove that \knn{}~\loo{}{} influence only requires $\bigO{n \log n}$~time -- significantly faster in practice than vanilla LOO{}'s $\bigO{\nTr\nItr}${} complexity.
\citeauthor{Jia:2021:ScalabilityVsUtility} also demonstrate empirically that \knn{}~\loo{}{} and vanilla LOO{} generate similar influence rankings across various learning domains and tasks.

In addition, \citet{Sharchilev:2018:TreeInfluence} propose \textsc{LeafRefit}{}, an efficient LOO{} estimator for decision-tree ensembles.
\textsc{LeafRefit}{}'s efficiency derives from the simplifying assumption that instance deletions do not affect the trees' structure.
In cases where this assumption holds, \textsc{LeafRefit}{}'s tree influence estimates are exact.
To the extent of our knowledge, \textsc{LeafRefit}{}'s suitability for surrogate influence analysis of deep models has not yet been explored.

Furthermore, for least-squares linear regression, \citet{Wojnowicz:2016:InfluenceSketching} 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~\citep{Johnson:1984}, 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 \keyword{leave\=/$m$\=/out} for any integer ${m \leq n}$.
Leave\=/$m$\=/out%
\footnote{%
  Leave\=/$m$\=/out influence analysis is also called \keyword{multiple-case deletion diagnostics}~\citep{Rousseeuw:1997:RobustRegressionOutlierDetection}.
}
has time complexity $\bigO{\binom{n}{m}}$, which is exponential in the worst case.
Shapley value influence~\citep{Shapley:1953} (Sec.~\ref{sec:Estimators:RetrainBased:Shapley}) shares significant similarity with leave\=/$m$\=/out.

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

\subsection{\textsc{Downsampling}{}}%
\label{sec:Estimators:RetrainBased:Feldman}

Proposed by \citet{Feldman:2020:InfluenceEstimation}, \textsc{Downsampling}{}%
\footnote{%
  \citet{Feldman:2020:InfluenceEstimation} do not specify a name for their influence estimator.
  Previous work has referred to \citeauthor{Feldman:2020:InfluenceEstimation}'s method as ``subsampling''~\citep{Brophy:2022:TreeInfluence} and as ``counterfactual influence''~\citep{Zhang:2021:CounterfactualMemorization}.
  We use ``\textsc{Downsampling}{}'' to differentiate \citeauthor{Feldman:2020:InfluenceEstimation}'s method from the existing, distinct task of dataset subsampling~\citep{Ting:2018:OptimalSubsampling} 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.

\textsc{Downsampling}{} relies on an ensemble of $K$~submodels each trained on a u.a.r.\ subset of full training set~$\mathcal{D}$.
Let ${\feldDatasetK \,\simN{m}\, \mathcal{D}}$ be the $k$\=/th submodel's training set where ${\forall_{k} \, \abs{\feldDatasetK} = m < n}$.%
\footnote{%
  \citet{Feldman:2020:InfluenceEstimation} propose setting ${m = \ceil{0.7n}}$.%
}
Define
${\nFeldModelI \coloneqq \sum_{k = 1}^{K} \ind{\zIBase \in \feldDatasetK}}$
as the number of submodels that used instance~$\zIBase$ during training.
The \keyword{\textsc{Downsampling}{} pointwise influence estimator}%
\footnote{%
  \citet{Feldman:2020:InfluenceEstimation} define their estimator specifically for classification.
  \textsc{Downsampling}{}'s definition in Eq.~\eqref{eq:Estimators:RetrainBased:Feldman} uses a more general form to cover additional learning tasks such as regression.
  \citeauthor{Feldman:2020:InfluenceEstimation}'s original formulation would be equivalent to defining the risk as ${\risk{\z_{\teStr}}{\wFeldK} = \indBig{\y_{\teStr} \ne \decFunc{\X_{\teStr}}{\wFeldK}}}$, i.e., the accuracy subtracted from one.%
}
is then
\begin{equation}%
  \labelAndRemember{eq:Estimators:RetrainBased:Feldman}{%
    \baseInfFunc{\infEstSym_{\textsc{Down}}}{\zIBase}{\z_{\teStr}}
      \coloneqq
      \frac{1}
           {K - \nFeldModelI}
      \sum_{\substack{k \\ \zIBase \notin \feldDatasetK}}
        \risk{\z_{\teStr}}{\wFeldK}
      -
      \frac{1}
           {\nFeldModelI}
      \sum_{\substack{\feldIdx' \\ \zIBase \in \feldDatasetK[\feldIdxAlt]}}
        \risk{\z_{\teStr}}{\wFeldK[\feldDatasetKAlt]}
  }%
  \text{.}
\end{equation}
\noindent
Intuitively, Eq.~\eqref{eq:Estimators:RetrainBased:Feldman} is the change in $\z_{\teStr}$'s average risk when $\zIBase$ is not used in submodel training.
By holding out multiple instances simultaneously and then averaging, each \textsc{Downsampling}{} submodel provides insight into the influence of \textit{all} training instances.
This allows \textsc{Downsampling}{} to require (far) fewer retrainings than LOO{}.

Since each of the $K$~training subsets is i.i.d., then
\begin{equation}\label{eq:Estimators:RetrainBased:Feldman:Expectation}
  \lim_{K \rightarrow \infty}
  \baseInfFunc{\infEstSym_{\textsc{Down}}}{\zIBase}{\z_{\teStr}}
    =
    \expectS{\trainSetAlt' \,\simN{m}\, \trainSet^{\setminus \setZi}}%
            {\risk{\z_{\teStr}}{\wFinSubBase{\trainSetAlt'}}}
    -
    \expectS{D \,\simN{m - 1}\, \trainSet^{\setminus \setZi}}%
            {\risk{\z_{\teStr}}{\wFinSubBase{\trainSetAlt \cup \zIBase}}}
    \text{.}%
\end{equation}%
\noindent%
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.~\eqref{eq:Estimators:RetrainBased:LOO}, Eq.~\eqref{eq:Estimators:RetrainBased:Feldman:Expectation} reformulates as
{
  %
  \begin{align}\label{eq:Estimators:RetrainBased:Feldman:ExpectedLOO}
    %
    \lim_{K,n,m \rightarrow \infty}
    \baseInfFunc{\infEstSym_{\textsc{Down}}}{\zIBase}{\z_{\teStr}}
      &=
      \expectS{\trainSetAlt' \,\simN{m - 1}\, \trainSet^{\setminus \setZi}}%
              {\risk{\z_{\teStr}}{\wFinSubBase{\trainSetAlt'}}}
      -
      \expectS{D \,\simN{m - 1}\, \trainSet^{\setminus \setZi}}%
              {\risk{\z_{\teStr}}{\wFinSubBase{\trainSetAlt \cup \zIBase}}}
      \\
      &= \expectS{D \,\simN{m - 1}\, \trainSet^{\setminus \setZi}}%
                 {%
                   \risk{\z_{\teStr}}{\wFinSubBase{D}}
                   -
                   \risk{\z_{\teStr}}{\wFinSubBase{\trainSetAlt \cup \zIBase}}
                 }  \\
      &= \expectS{D \,\simN{m - 1}\, \trainSet^{\setminus \setZi}}
                 {\baseInfFunc{\infLoo}{\zI}{\zTe}\vphantom{\bigg[}}
      \text{.}
  \end{align}%
}%

Hence, \textsc{Downsampling}{} is a statistically \keyword{consistent} estimator of the \keyword{expected LOO{} influence}.
This means that \textsc{Downsampling}{} does not estimate the influence of training instance~$\zIBase$ on a single model instantiation.
Rather, \textsc{Downsampling}{} estimates $\zIBase$'s \emph{influence on the training algorithm and model architecture as a whole}.
By considering influence in expectation, \textsc{Downsampling}{} addresses LOO{}'s inaccuracy caused by stochastic training's implicit variance.

In practice, $K$, $n$, and~$m$ are finite. Nonetheless, \citet[Lemma~2.1]{Feldman:2020:InfluenceEstimation} prove that, with high probability, \textsc{Downsampling}{}'s LOO{} influence estimation error is bounded given~$K$ and~$\frac{m}{n}$.

\begin{remark}
  \label{remark:Estimators:RetrainBased:Downsampling:Assumption}
  \textsc{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, \citeauthor{Feldman:2020:InfluenceEstimation} propose fixing ${\frac{m}{n} = 0.7}$.
  This choice balances satisfying the aforementioned assumption against the number of submodels \textsc{Downsampling}{} requires since $K$ and ratio~$\frac{m}{n}$ combined dictate $\nFeldModelI$, the number of submodels that are trained on $\zIBase$.
\end{remark}

\subsubsection{Time, Space, and Storage Complexity}%
\label{sec:Estimators:RetrainBased:Feldman:Complexity}

\textsc{Downsampling}{}'s complexity analysis is identical to that of LOO{} (Sec.~\ref{sec:Estimators:RetrainBased:LeaveOneOut:Complexity}) except, instead of the time and storage complexities being dependent on training-set size~$n$, \textsc{Downsampling}{} depends on submodel count~$K$.
For perspective, \citeauthor{Feldman:2020:InfluenceEstimation}'s empirical evaluation used ${K = 2,000}$ for ImageNet~\citep{Deng:2009:ImageNet} (${n > 14\text{M}}$) as well as ${K = 4,000}$ for MNIST~\citep{MNIST} (${n = 60,000}$) and CIFAR10~\citep{CIFAR10} (${n = 50,000}$)  --  a savings of one to four orders of magnitude over vanilla~LOO{}.

\begin{remark}
  \textsc{Downsampling}{}'s incremental time complexity is technically ${\bigO{K + n} \in \bigO{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 \textsc{Downsampling}{}; fewer forward passes translate to \textsc{Downsampling}{} being much faster than LOO{} in practice.
\end{remark}

\subsubsection{Strengths and Weaknesses}

Although more complicated than LOO{}, \textsc{Downsampling}{} is still comparatively simple to understand and implement.
\textsc{Downsampling}{} makes only a single assumption that should generally hold in practice (see Remark~\ref{remark:Estimators:RetrainBased:Downsampling:Assumption}).
\textsc{Downsampling}{} is also flexible and can be applied to most applications.

While \textsc{Downsampling}{}'s formulation above is w.r.t.\ a single training instance,
\textsc{Downsampling}{} trivially extends to estimate the \keyword{expected group influence} 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 \textsc{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 \textsc{Downsampling}{} to be applied at much larger scales than other methods.
For example, \citet{Feldman:2020:InfluenceEstimation} measure all pointwise influence estimates for the entire ImageNet dataset~\citep{Deng:2009:ImageNet} (${n > 14\text{M}}$).
These large-scale experiments enabled \citeauthor{Feldman:2020:InfluenceEstimation} to draw novel conclusions about neural training dynamics -- including that training instance memorization~\eqref{eq:EstimatorOverview:Memorization} 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 \textsc{Downsampling}{} is less computationally expensive than LOO{}, \textsc{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.

\subsubsection{Related Methods}

\textsc{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~\citep{Kandpal:2022:DeduplicatingPrivacyRisks}.
\citet{Van:2021:Memorization} extend \textsc{Downsampling}{} to deep generative models -- specifically, density models (e.g., variational autoencoders~\citep{Kingma:2014:VAE,Rezende:2014:DeepGenerativeModels}) that estimate posterior probability~${p(x \vert \mathcal{P}, \theta)}$, where $\mathcal{P}$ denotes the training data distribution.
Like \textsc{Downsampling}{}, \citeauthor{Van:2021:Memorization}'s approach relies on training multiple submodels.%
\footnote{%
  Rather than training submodels using i.i.d.\ subsets of~$\mathcal{D}$, \citet{Van:2021:Memorization} propose training the submodels via repeated $d$\=/fold cross-validation.
  While technically different, \citeauthor{Van:2021:Memorization}'s approach is functionally equivalent to \citepos{Feldman:2020:InfluenceEstimation} u.a.r.\ sampling procedure.%
}
The primary difference is that \citeauthor{Van:2021:Memorization} consider generative risk
\begin{equation}
  \risk{\X_{\teStr}}{\wT[T]}
  =
    -
    \log p(\X_{\teStr} \vert \mathcal{P}, \wT[T])
  \text{.}
\end{equation}
\noindent%
Beyond that, \citeauthor{Van:2021:Memorization}'s method is the same as \textsc{Downsampling}{} as both methods consider the LOO{} influence~\eqref{eq:Estimators:RetrainBased:Feldman}.

  \textsc{Downsampling}{}'s second closely related method is \citepos{Jiang:2021:CScore} \keyword{consistency profile}, defined formally as%
\footnote{%
  \citet{Jiang:2021:CScore} define their estimator specifically for classification. We present their method more generally to apply to other losses/domains (e.g.,~regression).
  As with \textsc{Downsampling}{}, it is trivial to map between Eq.~\eqref{eq:Estimators:Retrain:Feldman:ConsistencyProfile}'s formulation and that of \citeauthor{Jiang:2021:CScore}%
}
\begin{equation}\label{eq:Estimators:Retrain:Feldman:ConsistencyProfile}
  \cProfile
    \coloneqq
      %
      - \expectS{D \,\simN{\feldDatasetSize}\, \mathcal{D}}{\risk{\z_{\teStr}}{\wFinSubBase{D}}}
      %
      \text{.}
\end{equation}
\noindent
By negating the risk in Eq.~\eqref{eq:Estimators:Retrain:Feldman:ConsistencyProfile}, a higher expected risk corresponds to a lower consistency profile.
Consistency profile differs from \textsc{Downsampling}{} in two ways. (1)~\textsc{Downsampling}{} implicitly considers a single submodel training-set size~$m$ while
consistency profile disentangles the estimator from $m$.
(2)~\textsc{Downsampling}{} estimates $\zIBase$'s influence on $\z_{\teStr}$ 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 \abs{D}}$.

\citet{Jiang:2021:CScore} also propose the \keyword{consistency score} (C\=/score), defined formally as
\begin{equation}\label{eq:Estimators:Retrain:Feldman:ConsistencyScore}
  \cScore
  \coloneqq
    \expectS{\feldDatasetSize \,\simOne\, \setint{n}}%
            {\cProfile}
  \text{,}
\end{equation}
\noindent
where $\feldDatasetSize$ is drawn uniformly from set~$\setint{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_{\teStr}$ is harder for the model to confidently predict.
Large C\=/score{}s generally correspond to rare/atypical test instances from the tails of the data distribution.
Since \textsc{Downsampling}{} considers the effect of each training instance individually, \textsc{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 \textsc{Downsampling}{} and C\=/score{}.

\subsection{Shapley Value}%
\label{sec:Estimators:RetrainBased:Shapley}

Derived from cooperative game theory,
\keyword{Shapley value}~(SV{}) quantifies the increase in value when a group of players cooperates to achieve some shared objective \citep{Shapley:1953,Shapley:1988:ShapleyValue}.
Given $n$~total players, \keyword{characteristic function} $\func{\nu}{\powerSetInt{n}}{\mathbb{R}}$ defines the value of any player coalition ${A \subseteq \setint{n}}$
\citep{Dubey:1975:ShapleyValueUniqueness}.
By convention, a larger $\shapValFunc{A}$ is better.
Formally, player $i$'s Shapley value w.r.t.\ $\nu$ is
\begin{equation}%
  \label{eq:Estimators:RetrainBased:Shapley:Base}
  \shapValComplete{i}%
                  {\nu}%
    \coloneqq
    \sum_{A \subseteq \setint{n} \setminus i}
      \frac{\shapValFunc{A \cup i} - \shapValFunc{A}}%
           {\binom{n - 1}{\abs{A}}}
  \text{,}
\end{equation}
\noindent
where $\binom{n - 1}{\abs{A}}$ is the binomial coefficient.

\citet{Ghorbani:2019:DataShapley} 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.%
\footnote{%
  ``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 ${\shapValFunc{A} \coloneqq -\risk{\z_{\teStr}}{\wFinSubBase{A}}}$ where the negation is needed because more ``valuable'' training subsets have lower risk.
Then, $\zIBase$'s \keyword{Shapley value pointwise influence} on $\z_{\teStr}$ is
\begin{equation}%
  \labelAndRemember{eq:Estimators:RetrainBased:ShapleyInfluence}{%
    \baseInfFunc{\influence_{\text{SV}}}{\zIBase}{\z_{\teStr}}
        \coloneqq
        c
        \sum_{D \subseteq \trainSet^{\setminus \setZi}}
          \frac{\risk{\z_{\teStr}}{\wFinSubBase{D}} - \risk{\z_{\teStr}}{\wFinSubBase{\trainSetAlt \cup \zIBase}}}
               {\binom{n - 1}{\abs{D}}}
  }
  \text{,}
\end{equation}
\noindent
where $c$ is a constant, multiplicative scaling factor.
More intuitively, SV{} is the weighted change in $\z_{\teStr}$'s risk when $\zIBase$ is added to a random training subset; the weighting ensures all training subset sizes~($\abs{D}$) are prioritized equally.
Eq.~\eqref{eq:Estimators:RetrainBased:ShapleyInfluence} 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.~\eqref{eq:Estimators:RetrainBased:ShapleyInfluence} only considers the influence of a single training instance, both \citet{Shapley:1953} and \citet{Ghorbani:2019:DataShapley} discuss extending Shapley value to larger coalitions/groups.
Formally, the \keyword{Shapley value group influence} of any subset ${A \subseteq \mathcal{D}}$ is
\begin{equation}
  \labelAndRemember{eq:Estimators:RetrainBased:ShapleyGroupInfluence}{%
    \baseInfFunc{\influence_{\text{SV}}}{A}{\z_{\teStr}}
        \coloneqq
        c
        \sum_{D \subseteq \mathcal{D} \setminus A}
          \frac{\risk{\z_{\teStr}}{\wFinSubBase{D}} - \risk{\z_{\teStr}}{\wFinSubBase{D \cup A}}}
               {\binom{n - \abs{A}}{\abs{D}}}
  }
  \text{.}
\end{equation}
\noindent

\subsubsection{Time, Space, and Storage Complexity}%
\label{sec:Estimators:RetrainBased:Shapley:Complexity}

\citet{Deng:1994:ComplexityCooperativeGames} prove that computing Shapley values is \#P\=/complete.
Therefore, in the worst case, SV{} requires exponential time to determine exactly assuming ${\text{P} \ne \text{NP}}$.
There has been significant follow-on work to develop tractable SV{} estimators, many of which are reviewed in Sec.~\ref{sec:Estimators:RetrainBased:Shapley:RelatedMethods}.

The analysis of SV{}'s space, storage, and incremental time complexities follows that of LOO{} (Sec.~\ref{sec:Estimators:RetrainBased:LeaveOneOut:Complexity}) with the exception that SV{} requires up to $2^{n}$~models, not just $n$~models as with LOO{}.

\subsubsection{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~\citep{Shapley:1953,Dubey:1975:ShapleyValueUniqueness}.
Given any two data valuation metrics~$\nu'$ and~$\nu''$, it holds that
\begin{equation}%
  \label{eq:Estimators:RetrainBased:Shapley:Linearity}
  \shapValComplete{D}%
                  {\nu' + \nu''}
      =
        \shapValComplete{D}{\nu'}
        +
        \shapValComplete{D}{\nu''} \text{.}
\end{equation}
\noindent
SV{}'s additivity property makes it possible to estimate both pointwise and joint SV{} influences without repeating any data collection~\citep{Ghorbani:2019:DataShapley}.

Furthermore, by evaluating training sets of different sizes, SV{} can detect subtle influence behavior that is missed by methods like \textsc{Downsampling}{} and LOO{}, which evaluate a single training-set size.
\citet{Lin:2022:InfluenceRandomizedExperiments} 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~\citep{Kwon:2022:BetaShapley}.
For that reason, numerous (heuristic) SV{} speed-ups have been proposed, with the most prominent ones detailed next.

\subsubsection{Related Methods}%
\label{sec:Estimators:RetrainBased:Shapley:RelatedMethods}

\citet{Ghorbani:2019:DataShapley} propose two SV{} estimators.
First, \keyword{truncated Monte Carlo Shapley} (TMC\=/Shapley{}) relies on randomized subset sampling from training set~$\mathcal{D}$.\footnote{The 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 ${\zIBase[1], \ldots, \zIBase[\nTr]}$.
For each permutation, $n$~models are trained where the $i$\=/th model's training set is instances $\set{\zIBase[1], \ldots, \zIBase}$.
To measure each $\zIBase$'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 $\set{\zIBase[1], \ldots, \zIBase[\trIdx - 1]}$ and $\set{\zIBase[1], \ldots, \zIBase}$, respectively.
TMC\=/Shapley{} generates additional training-set permutations and trains new models until the SV{} estimates converge.
\citeauthor{Ghorbani:2019:DataShapley} state that TMC\=/Shapley{} convergence usually
requires analyzing on the order of $n$~training-set permutations.
Given training each model has time complexity $\bigO{\nItr}${} (Remark~\ref{rem:Estimators:RetrainBased:TimeComplexity}), TMC\=/Shapley{}'s full time complexity is in general $\bigO{\nTr^2 \nItr}${}.

TMC\=/Shapley{} may be feasible for simple models that are fast to train.
For more complex systems, $\bigO{\nTr^2}${} complete retrainings are impractical.
\citet{Ghorbani:2019:DataShapley} also propose \keyword{Gradient Shapley}~(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 \textit{one} gradient step.
This means that G\=/Shapley{}'s full and incremental time complexity is only $\bigO{\nTr^2}${} -- a substantial speed-up over TMC\=/Shapley{}'s full $\bigO{\nTr^2 \nItr}${} complexity.\footnote{%
  G\=/Shapley{} and TMC\=/Shapley{} have the same incremental time complexity -- $\bigO{\nTr^2}${}.
  Both estimators' storage complexity is $\bigO{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,
\citet{Jia:2019:KnnShapley} prove that for $k$\=/nearest neighbors classification, SV{} pointwise influence can be calculated exactly in $\bigO{n \lg n}$~time.
Formally, SV{}'s characteristic function for $\kNeigh$NN{} classification is
\begin{equation}\label{eq:Estimators:RetrainBased:Shapley:Knn:CharacteristicFunc}
  \nu_{k\text{NN}}(D)
    \coloneqq
      -
      \frac{1}%
           {k}
      \sum_{\yI \in \neighAlt{\X_{\teStr}}{D}}
      \ind{\yI = \y_{\teStr}}
  \text{,}
\end{equation}
where $\neighAlt{\X_{\teStr}}{D}$ is the set of $k$~neighbors in~$D$ nearest to~$\X_{\teStr}$ and $\ind{\cdot}$ is the indicator function. %
Each training instance either has no effect on Eq.~\eqref{eq:Estimators:RetrainBased:Shapley:Knn:CharacteristicFunc}'s value (${\zIBase \notin \neighAlt{\X_{\teStr}}{D}}$ or ${\yI \ne \y_{\teStr}}$).
Otherwise, the training instance increases the value by one (${\zIBase \in \neighAlt{\X_{\teStr}}{D}}$ and ${\yI = \y_{\teStr}}$).

Assuming the training instances are sorted by increasing distance from $\X_{\teStr}$ (i.e.,~$\xI[1]$ is closest to~$\X_{\teStr}$ and $\xI[n]$ is furthest), then $\zIBase$'s pointwise \keyword{\knn{}~Shapley{} influence} is
\begin{equation}
  \labelAndRemember{eq:Estimators:RetrainBased:Shapley:Knn:Influence}{%
    \baseInfFunc{\influence_{k\text{NN-SV}}}{\zIBase}{\z_{\teStr}}
        \coloneqq
          \frac{\ind{\yI[n] = \y_{\teStr}}}%
               {n}%
          + %
          \sum_{j = i}^{n - 1}%
          \frac{\ind{\yI[j] = \y_{\teStr}} - \ind{\yI[j + 1] = \y_{\teStr}}}%
                   {k}
                   %
                   \frac{\min\set{k,j}}
                   {j}
  }
  \text{.}
\end{equation}
\noindent
Observe that $\influence_{k\text{NN-SV}}$'s closed form is linear in~$n$ and requires no retraining at all.
In fact, \knn{}~Shapley{}'s most computationally expensive component is sorting the training instances by distance from~$\X_{\teStr}$.
Similar to \knn{}~\loo{}{} above, \citet{Jia:2019:KnnShapley} propose using \knn{}~Shapley{} as a surrogate SV{} estimator for more complex model classes.
For example, \knn{}~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.~\eqref{eq:Estimators:RetrainBased:Shapley:Base}).
Counterintuitively, \citet{Kwon:2022:BetaShapley} show theoretically and empirically that influence estimates on larger training subsets are \textit{more} affected by training noise than influence estimates on smaller subsets.
As such, rather than assigning all data subset sizes~($\abs{D}$) uniform weight, \citeauthor{Kwon:2022:BetaShapley} argue that smaller training subsets should be prioritized.
Specifically, \citeauthor{Kwon:2022:BetaShapley} propose \keyword{Beta Shapley}, 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, \keyword{Neuron Shapley} applies SV{} to identify the model neurons that are most critical for a given prediction~\citep{Ghorbani:2020:NeuronShapley}.
\citepos{Lundberg:2017:SHAP} 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 \citet{Sundararajan:2020:ManyShapleyValues} and a more recent update by \citet{Rozemberczki:2022:ShapleyValueSurvey}.
 %
\section{Gradient-Based Influence Estimation}%
\label{sec:Estimators:GradientBased}

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~\citep{Yeh:2018:Representer} or both the model and loss~\citep{Koh:2017:Understanding,Pruthi:2020:TracIn,Chen:2021:Hydra}.

The exact analytical framework each gradient-based method employs depends on the set of model parameters considered~\citep{Hammoudeh:2022:GAS}.
\keyword{Static, gradient-based methods} -- discussed first -- estimate the effect of retraining by studying gradients w.r.t.\ final model parameters~$\wT[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, \keyword{dynamic, gradient-based influence estimators} reconstruct the training data's influence by studying model parameters throughout training, e.g.,~${\wT[0], \ldots, \wT[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.

\subsection{Static, Gradient-Based Influence Estimation}%
\label{sec:Estimators:GradientBased:Static}

As mentioned above, static estimators are so named because they measure influence using only final model parameters~$\wT[T]$.
Static estimators' theoretical formulations assume \keyword{stationarity} (i.e.,~the model parameters have converged to a risk minimizer) and \keyword{convexity}.

Below we focus on two static estimators -- \keyword{influence functions}~\citep{Koh:2017:Understanding} and \keyword{representer point}~\citep{Yeh:2018:Representer}.
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.%

\subsubsection{Influence Functions}%
\label{sec:Estimators:GradientBased:Static:IF}

Along with Shapley value (Sec.~\ref{sec:Estimators:RetrainBased:Shapley}),
\citepos{Koh:2017:Understanding} \keyword{influence functions} is one of the best-known influence estimators.
The estimator derives its name from influence functions (also known as \keyword{infinitesimal jackknife}~\citep{Jaeckel:1972:InfinitesimalJackknife}) in robust statistics~\citep{Hampel:1974:InfluenceCurve}.
These early statistical analyses consider how a model changes if training instance~$\zIBase$'s weight is infinitesimally perturbed by~${\epsilon_{\trIdx}}$.
More formally, consider the change in the \keyword{empirical risk minimizer} from
\begin{equation}\label{eq:Estimators:GradientBased:Static:IF:ErmBase}
  \wT[T]
    =
    \argmin_{\theta}
    \frac{1}{n}
    \sum_{z \in \mathcal{D}}
      \risk{z}{\theta}
\end{equation}
\noindent
to
\begin{equation}\label{eq:Estimators:GradientBased:Static:IF:ErmPerturb}
  \wFin_{+\epsI}
    =
    \argmin_{\theta}
    \frac{1}{n}
    \sum_{z \in \mathcal{D}}
      \risk{z}{\theta}
    +
    \epsilon_{\trIdx} \risk{\zIBase}{\theta}
  \text{.}
\end{equation}

Under the assumption that model~$f$ and loss function~$\ell$ are twice-differentiable and strictly convex, \citet{Cook:1982:InfluenceRegression} prove via a first-order Taylor expansion that
\begin{equation}\label{eq:Estimators:GradientBased:Static:ParamDeriv}
  \frac{d \wFin_{+\epsI}}%
       {d \epsilon_{\trIdx}}
  \Big\vert_{\epsI = 0}
    =
    -{(\hessFin)^{-1}}
    \nabla_{\w}
    \risk{\zIBase}{\wT[T]}
  \text{,}
\end{equation}
\noindent
where empirical risk Hessian ${\hessT[\nItr] \coloneqq \frac{1}{n}\sum_{z \in \mathcal{D}} \gradW^{2} \risk{z}{\wT[T]}}$ is by assumption positive definite.
\citet{Koh:2017:Understanding} extend \citeauthor{Cook:1982:InfluenceRegression}'s result to consider the effect of this infinitesimal perturbation on $\z_{\teStr}$'s~risk, where
\begin{align}
  \frac{d \risk{\z_{\teStr}}{\wT[T]}}
       {d \epsilon_{\trIdx}}
  \Big\vert_{\epsI = 0}
  &=
  \frac{d \risk{\z_{\teStr}}{\wT[T]}}
       {d \wFin_{+\epsI}}
  %
  ^{\intercal}
  \frac{d \wFin_{+\epsI}}
       {d \epsilon_{\trIdx}}
  \Big\vert_{\epsI = 0}
  &
  \text{\algcomment{Chain rule}}
  \\
  &=
    -
    \nabla_{\w} \risk{\z_{\teStr}}{\wT[T]}^{\intercal}
    {(\hessFin)^{-1}}
    \nabla_{\w} \risk{\zIBase}{\wT[T]}
  \text{.}
  \label{eq:Estimators:GradientBased:Static:LossDerivEps}
\end{align}

Removing training instance~$\zIBase$ from~$\mathcal{D}$ is equivalent to ${\epsilon_{\trIdx} = -\frac{1}{n}}$ making the \keyword{pointwise influence functions estimator}
\begin{equation}%
  \labelAndRemember{eq:Estimators:GradientBased:Static:IF}{%
    \baseInfFunc{\infEstSym_{\textsc{IF}}}{\zIBase}{\z_{\teStr}}
    \coloneqq
      \frac{1}
           {n}
      \nabla_{\w} \risk{\z_{\teStr}}{\wT[T]}^{\intercal}
      {(\hessFin)^{-1}}
      \nabla_{\w} \risk{\zIBase}{\wT[T]}
  }%
  \text{.}
\end{equation}
\noindent
More intuitively, Eq.~\eqref{eq:Estimators:GradientBased:Static:IF} is the influence functions' estimate of the leave\=/one\=/out influence of $\zIBase$ on~$\z_{\teStr}$.

\paragraph{Time, Space, and Storage Complexity}

Calculating inverse Hessian~\eqsmall{${(\hessFin)^{-1}}$} directly requires $\bigO{np^2 + p^3}$~time and $\bigO{p^2}$ space~\citep{Koh:2017:Understanding}.
For large models, this is clearly prohibitive.
Rather than computing~\eqsmall{${(\hessFin)^{-1}}$} directly, \citeauthor{Koh:2017:Understanding} instead estimate \textit{Hessian-vector product} (HVP)
\begin{equation}%
  \label{eq:Estimators:GradientBased:Static:IF:STest}
  s_{\text{test}}
    \coloneqq
    {(\hessFin)^{-1}}
    \nabla_{\w} \risk{\z_{\teStr}}{\wT[T]}
  \text{,}
\end{equation}
\noindent%
with each training instance's pointwise influence then
\begin{equation}%
  \baseInfFunc{\infEstSym_{\textsc{IF}}}{\zIBase}{\z_{\teStr}}
  =
    \frac{1}
         {n}
    %
    %
    s_{\text{test}}^{\intercal}
    \nabla_{\w} \risk{\zIBase}{\wT[T]}
  \text{.}
\end{equation}

\citet{Koh:2017:Understanding} use the stochastic algorithm of \citet{Pearlmutter:1994} and \citet{Agarwal:2017} to estimate~$s_{\text{test}}$.
This reduces influence functions' complexity to just $\bigO{\nTr\dimW}${} time and $\bigO{\nTr + \dimW}${} space.
Since $s_{\text{test}}$ is specific to test instance~$\z_{\teStr}$, $s_{\text{test}}$ must be \textit{estimated for each test instance individually}.
This increases influence functions' computational cost but also means that influence functions require no additional storage.

\paragraph{Strengths and Weaknesses}%
\label{sec:Estimators:GradientBased:Static:IF:StrengthWeaknesses}

Influence functions' clear advantage over retraining-based methods is that influence functions eliminate the need to retrain any models.
Recall from Table~\ref{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~\citep{Yeh:2018:Representer,Guo:2021:FastIF,Hammoudeh:2022:GAS}), it is still significantly faster than retraining $\bigO{\nTr}${} 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, \textit{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 $\hessT[\nItr]$ is positive definite often does not hold for deep models~\citep{Basu:2021:InfluenceFunctionsFragile}.
To ensure inverse ${(\hessFin)^{-1}}$ exists, \citeauthor{Koh:2017:Understanding} 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~\citep{Yeh:2018:Representer,Hara:2019:SgdInfluence,Hammoudeh:2022:GAS}.

More generally, \citet{Basu:2021:InfluenceFunctionsFragile} show that training hyperparameters also significantly affect influence functions' performance.
Specifically, \citeauthor{Basu:2021:InfluenceFunctionsFragile} empirically demonstrate that model initialization, model width, model depth, weight-decay strength, and even the test instance being analyzed~($\z_{\teStr}$) all can negatively affect influence functions' LOO{} estimation accuracy.
Their finding is supported by the analysis of \citet{Zhang:2022:RethinkingInfluenceFunctions} who show that HVP estimation's accuracy depends heavily on the model's training regularizer with HVP accuracy ``pretty low under weak regularization.''

\citet{Bae:2022:InfluenceFunctionsQuestion} also empirically analyze the potential sources of influence functions' fragility on deep models.
\citeauthor{Bae:2022:InfluenceFunctionsQuestion} identify five common error sources, the first three of which are the most important.%
\footnote{%
  \citet[Table~1]{Bae:2022:InfluenceFunctionsQuestion} provide a formal mathematical definition of influence functions' five error sources.%
}
\begin{itemize}
  \item \textit{Warm-start gap}:
    Influence functions more closely resembles performing fine-tuning close to final model parameters~$\wT[T]$ than retraining from scratch (i.e.,~starting from initial parameters~$\wT[0]$).
    This difference in starting conditions can have a significant effect on the LOO{} estimate.
  \item \textit{Proximity gap}:
    The error introduced by the dampening term included in the HVP~($s_{\text{test}}$) estimation algorithm.
    %
  \item \textit{Non-convergence gap}:
      %
    The error due to final model parameters~$\wT[T]$ not being a stationary point, i.e.,~${\sum_{\zIBase \in \mathcal{D}} \nabla_{\w} \risk{\zIBase}{\wT[T]} \ne \vec{0}}$.
  \item \textit{Linearization error}:
    The error induced by considering only a first-order Taylor approximation when deleting~$\zIBase$ and ignoring the potential effects of curvature on~$\baseInfFunc{\infEstSym_{\textsc{IF}}}{\zIBase}{\z_{\teStr}}$~\citep{Basu:2020:OnSecond}.
    %
  \item \textit{Solver error}:
    General error introduced by the specific solver used to estimate~$s_{\text{test}}$.
\end{itemize}
\noindent
Rather than estimating the LOO{} influence,
\citeauthor{Bae:2022:InfluenceFunctionsQuestion} argue that influence functions more closely estimate a different measure they term the \keyword{proximal Bregman response function}~(PBRF).
\citeauthor{Bae:2022:InfluenceFunctionsQuestion} provide the intuition that PBRF ``approximates the effect of removing a data point while trying to keep predictions consistent with the \ldots{} trained model''~\citep{Bae:2022:InfluenceFunctionsQuestion}.
Put simply, PBRF mimics a prediction-constrained LOO influence.

\citeauthor{Bae:2022:InfluenceFunctionsQuestion} assert that PBRF can be applied in many of the same situations where LOO{} is useful.
\citeauthor{Bae:2022:InfluenceFunctionsQuestion} further argue that influence functions' fragility reported by earlier works~\citep{Basu:2021:InfluenceFunctionsFragile,Zhang:2022:RethinkingInfluenceFunctions} 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.

\paragraph{Related Methods}%
\label{sec:Estimators:GradientBased:Static:IF:RelatedMethods}

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~\citep{Barshan:2020:RelatIF,Yeh:2022:FirstBetterLast}.%
\footnote{%
  Section~\ref{sec:Estimators:GradientBased:Static:RepresenterPoint:StrengthWeaknesses} discusses some of the pitfalls associated with estimating influence using only a model's final (linear) layer.%
}
Moreover, \citepos{Guo:2021:FastIF} \keyword{fast influence functions} (\textsc{FastIF}) integrate multiple speed-up heuristics.
First, they leverage the inherent parallelizability of \citepos{Pearlmutter:1994} HVP estimation algorithm.
In addition, \textsc{FastIF}{} includes recommended hyperparameters for \citeauthor{Pearlmutter:1994}'s HVP algorithm that reduces its execution time by 50\%~on average.

More recently, early results from \citet{Schioppa:2022:ScaledUpInfluenceFunctions} 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, \citeauthor{Schioppa:2022:ScaledUpInfluenceFunctions} use \citepos{Arnoldi:1951} famous algorithm that quickly finds the dominant (in absolute terms) eigenvalues and eigenvectors of \eqsmall{$\hessT[\nItr]$}.
These dominant eigenvectors serve as the basis when projecting all gradient vectors to a lower-dimensional subspace.
\citeauthor{Schioppa:2022:ScaledUpInfluenceFunctions} evaluate their revised influence functions estimator on large transformer networks (e.g.,~ViT\=/L32 with 300M parameters~\citep{Dosovitskiy:2021:VisionTransformer}), which are orders of magnitude larger than the simple networks \citet{Koh:2017:Understanding} consider.

Another approach to speed up influence functions is to specialize the estimator to model architectures with favorable computational properties.
For example, \citepos{Sharchilev:2018:TreeInfluence} \textsc{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, \textsc{LeafInfluence}{}'s tree-based estimates are significantly faster than influence functions on deep models~\citep{Brophy:2022:TreeInfluence}.

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, %
\citepos{Koh:2019:GroupEffects} follow-on paper analyzes influence functions' empirical performance estimating group influence.
In particular, \citet{Koh:2019:GroupEffects} 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, \citet{Koh:2019:GroupEffects} observe that simply summing influence functions estimates tends to \textit{underestimate} the true group influence.
More formally, let ${D \subseteq \mathcal{D}}$ be a coherent training-set subpopulation, then
\begin{equation}
  \sum_{\zIBase \in D}
    %
    {\big\lvert
      \baseInfFunc{\infEstSym_{\textsc{IF}}}%
                  {\zIBase}%
                  {\z_{\teStr}}%
    \big\rvert}
    %
  <
    %
    {\big\lvert
      \baseInfFunc{\mathcal{I}}%
                  {D}%
                  {\z_{\teStr}}%
    \big\rvert}
    %
  \text{.}
\end{equation}
\noindent
Nonetheless, influence functions' additive group estimates tend to have strong rank correlation w.r.t.\ subpopulations' true group influence.
In addition, \citet{Basu:2020:OnSecond} extend influence functions to directly account for subpopulation group effects by considering higher-order %
terms in influence functions' Taylor-series approximation.

\subsubsection{Representer Point Methods}%
\label{sec:Estimators:GradientBased:Static:RepresenterPoint}

Unlike this section's other gradient-based estimators, \citepos{Yeh:2018:Representer} \keyword{representer point} method does not directly rely on a Taylor-based expansion.
Instead, \citeauthor{Yeh:2018:Representer} build on \citepos{Scholkopf:2001:RepresenterTheorem} \keyword{generalized representer theorem}.
The derivation below assumes that model~$f$ is linear.
\citeauthor{Yeh:2018:Representer} use a simple ``trick'' to extend linear representer point methods to multilayer models like neural networks.

Representer-based methods rely on \keyword{kernels}, which are functions $\func{\mathcal{K}}{\mathcal{X} \times \mathcal{X}}{\mathbb{R}}$ that measure the similarity between two vectors~\citep{Hofmann:2008:KernelMethods}.
\citeauthor{Scholkopf:2001:RepresenterTheorem}'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
\begin{equation}\label{eq:Estimators:GradientBased:Static:RepPt:ERM}
  \w^{*}
    \coloneqq
      \argmin_{\theta}
      \frac{1}{n}
      \sum_{\zIBase \in \mathcal{D}}
        \risk{\zIBase}%
             {\theta}
        +
        \wdecay
        \norm{\theta}_{2}
  \text{,}
\end{equation}
\noindent
with ${\wdecay > 0}$ the $L_2$ regularization strength.
Note that Eq.~\eqref{eq:Estimators:GradientBased:Static:RepPt:ERM} defines minimizer~$\w^{*}$ slightly differently than the last section~\eqref{eq:Estimators:GradientBased:Static:IF:ErmBase} since the representer theorem \textit{requires} regularization.

Empirical risk minimizers are \keyword{stationary points} meaning
\begin{equation}
  \nabla_{\w}
  %
  \bigg(
    \frac{1}{n}
    \sum_{\zIBase \in \mathcal{D}}
      \risk{\zIBase}{\w^{*}}
      +
      \wdecay \norm{\w^{*}}_{2}
  \bigg)
  %
  =
  \vec{0}
  \text{,}
\end{equation}
\noindent
where $\vec{0}$~is the $p$\=/dimensional, zero vector.  The above simplifies to
\begin{align}
  \frac{1}%
       {n}
  \sum_{\zIBase \in \mathcal{D}}
    \frac{\partial \risk{\zIBase}{\w^{*}}}%
         {\partial \theta}
    + 2 \wdecay \w^{*}
  &=
    \vec{0}
  \\
  \w^{*}
  &=
    -
    \frac{1}%
         {2 \wdecay n}
    \sum_{\zIBase \in \mathcal{D}}
      \frac{\partial \risk{\zIBase}{\w^{*}}}%
           {\partial \theta}
  \text{.}
  \label{eq:Estimators:GradientBased:Static:RepresenterPoint:WoptOne}
\end{align}

For a linear model where ${\decFunc{x}{\theta} = \theta^{\intercal} x \eqqcolon \hatFunc{\y}}$, Eq.~\eqref{eq:Estimators:GradientBased:Static:RepresenterPoint:WoptOne} further simplifies via the chain rule to
{\small%
  \begin{align}
    \w^{*} &=
      -\frac{1}{2 \wdecay n}
      \sum_{(\xI,\yI) \in \mathcal{D}}
      \frac{\partial \lDecFunc{\xI}{\w^{*}}{\yI}}{\partial \theta}
    \\
    &=
      -\frac{1}{2 \wdecay n}
      \sum_{(\xI,\yI) \in \mathcal{D}}
      \frac{\partial \lFunc{\yHatI}{\yI}}{\partial \yHat}
      \,
      \frac{\partial \yHatI}{\partial \theta}
    &
    \text{\algcomment{Chain Rule}}
    \\
    &=
      -\frac{1}{2 \wdecay n}
      \sum_{(\xI,\yI) \in \mathcal{D}}
      \frac{\partial \lFunc{\yHatI}{\yI}}{\partial \yHat}
      \,
      \xI
    &
    \text{\algcomment{$\hatFunc{\y} = \theta^{\intercal} x$}}
    \\
    &=
      \sum_{(\xI,\yI) \in \mathcal{D}}
      \rpValSym_{\trIdx}
      \xI
    \text{,}
  \end{align}%
}%
\noindent
where $\ell$~is any once-differentiable loss function, \eqsmall{$\frac{\partial \lFunc{\yHatI}{\yI}}{\partial \yHat}$} is the gradient of \textit{just the loss function} itself w.r.t.\ model output~$\hatFunc{\y}$,%
\footnote{%
  In the case of classification, \eqsmall{$\frac{\partial \lFunc{\yHatI}{\yI}}{\partial \yHat}$} has $\abs{\mathcal{Y}}$~dimensions, i.e.,~its dimension equals the number of classes.%
}
 and \eqsmall{${\rpValSym_{\trIdx} \coloneqq -\frac{1}{2\wdecayn} \frac{\partial \lFunc{\yHatI}{\yI}}{\partial \yHat}}$} is the $i$\=/th training instance's \keyword{representer value}.
\citet{Yeh:2018:Representer} provide the intuition that a larger magnitude~$\rpValSym_{\trIdx}$ indicates that training instance~$\zIBase$ has larger influence on the final model parameters~$\w^{*}$.

Following \citepos{Scholkopf:2001:RepresenterTheorem} representer theorem kernelized notation, the training set's group influence on test instance~$\z_{\teStr}$ for any linear model is
\begin{equation}
  \baseInfFunc{\influence_{\textsc{RP}}}{\mathcal{D}}{\z_{\teStr}}
  =
    \sum_{i = 1}^{n}
      \rpValSym_{\trIdx} \xI^{\intercal} \X_{\teStr} \,\vert_{\yTe}
  =
    \sum_{i = 1}^{n}
      {\kernel(\xI, \xTe, \rpValSym_{\trIdx})\,\vert_{\yTe}}
  =
    \sum_{i = 1}^{n}
    \baseInfFunc{\influence_{\textsc{RP}}}{\zIBase}{\z_{\teStr}}
  \text{,}
\end{equation}
\noindent
where kernel function~${\kernelFunc{\xI}{\X_{\teStr}}{\rpValSym_{\trIdx}} \coloneqq \rpValSym_{\trIdx} \xI^{\intercal} \X_{\teStr}}$ returns a vector.
${{\kernel(\xI, \xTe, \rpValSym_{\trIdx})\,\vert_{\yTe}}}$~denotes the kernel value's $\y_{\teStr}$\=/th dimension.
Then, $\zIBase$'s \keyword{pointwise linear representer point influence} on~$\z_{\teStr}$ is
\begin{equation}
  \labelAndRemember{eq:Estimators:GradientBased:Static:RepresenterPoint:LinearIdeal}{%
    \baseInfFunc{\influence_{\textsc{RP}}}{\zIBase}{\z_{\teStr}}
    =
      \rpValSym_{\trIdx} \xI^{\intercal} \X_{\teStr} \,\vert_{\yTe}
  }
  =
    {\kernel(\xI, \xTe, \rpValSym_{\trIdx})\,\vert_{\yTe}}
  \text{.}
\end{equation}

\noindent
\textbf{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, \citet{Yeh:2018:Representer} rely on what they (later) term \keyword{last layer similarity}~\citep{Yeh:2022:FirstBetterLast}.

Formally, \citet{Yeh:2018:Representer} partition the model parameters~%
\eqsmall{${\wT[T] = \lbrack~\itrSup{\dot{\w}}{\nItr}~~\itrSup{\ddot{\w}}{\nItr}~\rbrack}$}
into two subsets, where $\itrSup{\ddot{\w}}{\nItr}$~is the last linear (i.e.,~classification) layer's parameters and \eqsmall{${\itrSup{\dot{\w}}{\nItr} \coloneqq \wT[T] \setminus \itrSup{\ddot{\w}}{\nItr}}$}~is all other model parameters.
Since $\itrSup{\ddot{\w}}{\nItr}$~is simply a linear function, the representer theorem analysis above still applies to it.
\citet{Yeh:2018:Representer} treat the other parameters,~$\itrSup{\dot{\w}}{\nItr}$, as a fixed feature extractor and ignore them in their influence analysis.

To use \citepos{Yeh:2018:Representer} multilayer trick,
one small change to Eq.~\eqref{eq:Estimators:GradientBased:Static:RepresenterPoint:LinearIdeal} is required.
Obviously, in multilayer models, the final (linear) layer does not operate over feature vectors $\xI$ and $\X_{\teStr}$ 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~$\itrSup{\dot{\w}}{\nItr}$, i.e.,~vector $\mathbf{f}$ is the input to the model's last linear layer given input~$x$.
Then the \keyword{representer point influence estimator} for a multilayer model is
\begin{equation}
  \labelAndRemember{eq:Estimators:GradientBased:Static:RepresenterPoint:Estimate}{%
    \baseInfFunc{\infEstSym_{\textsc{RP}}}{\zIBase}{\z_{\teStr}}
    \coloneqq
      \rpValSym_{\trIdx}
      \featI^{\intercal} \featI[\teStr] \,\vert_{\yTe}
  }
  =
  \kernelFunc{\featI}{\featI[\teStr]}{\rpValSym_{\trIdx}}\,\vert_{\yTe} \text{.}
\end{equation}

\paragraph{Time, Space, and Storage Complexity}

Treating as constants feature representation dimension~$\abs{\mathbf{f}}$ and the overhead to calculate \eqsmall{$\frac{\partial \lFunc{\yHatI}{\yI}}{\partial \yHat}$}, estimating the entire training set's representer point influence only requires calculating $n$~dot products. %
This only takes $\bigO{\nTr}${} time and $\bigO{\nTr + \dimW}${} space with no additional storage requirements.

\paragraph{Strengths and Weaknesses}
\label{sec:Estimators:GradientBased:Static:RepresenterPoint:StrengthWeaknesses}

Representer point's primary advantage is its theoretical and computational simplicity.
Eq.~\eqref{eq:Estimators:GradientBased:Static:RepresenterPoint:Estimate} only considers the training and test instances' final feature representations and loss function gradient~\eqsmall{$\frac{\partial \lFunc{\yHatI}{\yI}}{\partial \yHat}$}.
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~\ref{sec:Estimators:GradientBased:Dynamic}'s dynamic estimators~\citep{Hammoudeh:2021:Simple}.

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, \citet{Yeh:2018:Representer} recommend freezing all model layers except the final one (i.e.,~freezing $\itrSup{\dot{\w}}{\nItr}$) and then fine-tuning the classification layer~($\itrSup{\ddot{\w}}{\nItr}$) 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, \citet{Hammoudeh:2022:GAS} 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, %
\citet{Yeh:2022:FirstBetterLast} 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''.
\citet{Yeh:2022:FirstBetterLast} further state that the feature representations in the final layer -- and by extension representer point's influence estimates -- can be ``too reductive.''

In short, \citepos{Yeh:2018:Representer} 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.

\paragraph{Related Methods}

Given the accuracy limitations of relying on last-layer similarity, limited follow-on work has adapted representer-point methods.
\citet{Brophy:2022:TreeInfluence} extend representer point methods to decision forests via their Tree-ensemble Representer Point Examples~(TREX) estimator.  Specifically, they use \keyword{supervised tree kernels} -- which provide an encoding of a tree's learned representation structure~\citep{Davies:2014:RandomForestKernel,He:2014:PredictingClicks} -- for similarity comparison.

In addition, \citet{Sui:2021:LocalJacobianRepPt} propose \keyword{representer point selection based on a local Jacobian expansion} (RPS\=/LJE), which can be viewed as a generalizing \citepos{Yeh:2018:Representer} base method.
Rather than relying on \citepos{Scholkopf:2001:RepresenterTheorem} representer theorem, \citeauthor{Sui:2021:LocalJacobianRepPt}'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 ${
    \baseInfFunc{\infEstSym_{\textsc{RP}}}{\zIBase}{\z_{\teStr}}
    \coloneqq
    %
      \rpValSym_{\trIdx}
      \featI^{\intercal} \featI[\teStr]
      %
}$, albeit with $\rpValSym_{\trIdx}$ defined differently.

RPS\=/LJE{} addresses two weaknesses of \citepos{Yeh:2018:Representer} base approach.
First, \citeauthor{Sui:2021:LocalJacobianRepPt}'s formulation does not presume that $\wT[T]$ is a stationary point.
Therefore, RPS\=/LJE{} does not require post-training fine-tuning to enforce stationarity.
Second, as Section~\ref{sec:Estimators:GradientBased:TradeOff} 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 $\rpValSym_{\trIdx}$ is less influenced by a training instance's loss value, which enables RPS\=/LJE{} to generate more semantically meaningful influence rankings.

\subsection{Dynamic, Gradient-Based Influence Estimation}%
\label{sec:Estimators:GradientBased:Dynamic}

All preceding influence methods -- static, gradient-based and retraining-based -- define and estimate influence using only final model parameters,~$\wFinSubBase{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~\citep{Blum:1992:TrainingNpComplete}, 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 \textit{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_{\teStr}$ may not be known before model training, in-situ influence analysis may not be possible.
Instead, as shown in Alg.~\ref{alg:GradientBased:Dynamic:Training}, intermediate model parameters ${\Theta \subseteq \set{\wT[0], \ldots, \wT[T - 1]}}$ are stored during training for post hoc influence analysis.%
\footnote{%
  In practice, only a subset of~$\set{\wT[0], \ldots, \wT[T - 1]}$ is actually stored.
  Heuristics are then applied to this subset to achieve acceptable influence estimation error~\citep{Pruthi:2020:TracIn,Hammoudeh:2022:GAS}.%
}

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.

\begin{figure}[t]
  \centering
  \begin{minipage}{0.72\textwidth}
    \begin{algorithm}[H]
      {%
        \footnotesize%
        \caption{Dynamic influence estimation's training phase}\label{alg:GradientBased:Dynamic:Training}
        %
\begin{algorithmic}[1]
  \setstretch{1.22}%
  \Require Training set~$\mathcal{D}$;{}
           iteration count~$T$;{}
           learning rates ${\lrT[1], \ldots, \lrT[\nItr]}$;{}
           batch sizes~${\batchSizeBase{1}, \ldots, \batchSizeBase{T}}$;{}
           and
           initial parameters~$\wT[0]$

  \Ensure Final parameters~$\wT[T]$ and stored parameter set~$\Theta$

  \State $\Theta \gets \emptyset$
  \For{$t \gets 1 \textbf{ to } T$}
    \State $\Theta \gets \Theta \cup \set{\wT[t - 1]}$ \algcomment{Store intermediate params.}
    \State $\batchT \,\simN{\batchSizeBase{t}}\, \mathcal{D}$
    \State $\wT \gets \textsc{Update}(\lrT, \wT[t - 1], \batchT)$
  \EndFor
  \State \Return $\wT[T]$, $\Theta$
\end{algorithmic}
       }%
    \end{algorithm}
  \end{minipage}
\end{figure}

\subsubsection{TracIn{} -- Tracing Gradient Descent}%
\label{sec:Estimators:GradientBased:Dynamic:TracIn}

  %
  Fundamentally, all preceding methods define influence w.r.t.\ changes to the training set.
  \citet{Pruthi:2020:TracIn} take an orthogonal perspective.
  They treat training set~$\mathcal{D}$ as fixed, and consider the \textit{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_{\teStr}$ is
\begin{equation}\label{eq:Estimators:GradientBased:Dynamic:TracIn:DatasetGroup}
  %
  \baseInfFunc{\influence}{\mathcal{D}}%
          {\z_{\teStr}}
  =
    \risk{\z_{\teStr}}{\wT[0]}
    -
    \risk{\z_{\teStr}}{\wT[T]}
  \text{.}
\end{equation}
\noindent
In words, training set~$\mathcal{D}$ causes the entire change in test loss between random initial parameters~$\wT[0]$ and final parameters~$\wT[T]$.
Eq.~\eqref{eq:Estimators:GradientBased:Dynamic:TracIn:DatasetGroup} decomposes by training iteration~$t$ as
\begin{equation}\label{eq:Estimators:GradientBased:Dynamic:Tracin:DatasetGroup}
  %
  \baseInfFunc{\influence}{\mathcal{D}}{\z_{\teStr}}
  =
    \sum_{t = 1}^{T}
      \left(
        \risk{\z_{\teStr}}{\wT[t - 1]}
        -
        \risk{\z_{\teStr}}{\wT}
      \right)
  \text{.}
\end{equation}

Consider training a model with vanilla stochastic gradient descent, where each training minibatch~$\batchT$ is a single instance and gradient updates have no momentum~\citep{Rumelhart:1986:BackProp}.
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~$\batchT$.
Under this regime, \citet{Pruthi:2020:TracIn} define the \keyword{ideal TracIn{} pointwise influence} as
\begin{equation}
  \labelAndRemember{eq:Estimators:GradientBased:Dynamic:TracInIdeal}{%
    \baseInfFunc{\influence_{\text{TracIn{}}}}{\zIBase}{\z_{\teStr}}
        \coloneqq
        %
        %
        %
        %
        %
        %
        %
        %
        \sum_{\substack{t \\ \zIBase = \batchT}}
          \left(
            \risk{\z_{\teStr}}{\wT[t - 1]}
            -
            \risk{\z_{\teStr}}{\wT}
          \right)
  }
  \text{,}
\end{equation}
where the name ``TracIn{}'' derives from ``tracing gradient descent influence.''
Eq.~\eqref{eq:Estimators:GradientBased:Dynamic:Tracin:DatasetGroup} under vanilla stochastic gradient descent decomposes into the sum of all pointwise influences
\begin{equation}\label{eq:Estimators:GradientBased:Dynamic:Tracin:DatasetGroup:IndividualInstance}
  \baseInfFunc{\influence}{\mathcal{D}}{\z_{\teStr}}
  %
  =
    \sum_{i = 1}^{n}
      \Bigg(
        \sum_{\substack{t \\ \zIBase = \batchT}}
          \risk{\z_{\teStr}}{\wT[t - 1]}
          -
          \risk{\z_{\teStr}}{\wT}
      \Bigg)
  =
    \sum_{i = 1}^{n}
      \baseInfFunc{\influence_{\text{TracIn{}}}}{\zIBase}{\z_{\teStr}}
  \text{.}
\end{equation}

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~\citep{You:2017:LargeBatchTraining,Goyal:2017:LargeMinibatchSGD,Brown:2020:GPT3}.

A naive fix to Eq.~\eqref{eq:Estimators:GradientBased:Dynamic:TracInIdeal} to support non-singleton batches assigns the same influence to all instances in the minibatch, or more formally, divide the change in loss ${\risk{\z_{\teStr}}{\wT[t - 1]} - \risk{\z_{\teStr}}{\wT}}$ by batch size~$\abs{\batchT}$ for each ${\zIBase \in \batchT}$.
This naive approach does not differentiate those instances in batch~$\batchT$ that had positive influence on the prediction from those that made the prediction worse.

Instead, \citet{Pruthi:2020:TracIn} estimate the contribution of each training instance within a minibatch via a first-order Taylor approximation. Formally,
\begin{equation}\label{eq:Estimators:GradientBased:Dynamic:TracIn:TaylorExpansion}
  \risk{\z_{\teStr}}{\wT}
  \approx
  \risk{\z_{\teStr}}{\wT[t - 1]}
  +
  \dotprod{{\nabla_{\w} \risk{\zTe}{\wTOne}}}
          {(\wT - \wT[t - 1])}
  %
  \text{.}
\end{equation}
\noindent
Under gradient descent without momentum, the change in model parameters is directly determined by the batch instances' gradients,~i.e.,
\begin{equation}\label{eq:Estimators:GradientBased:Dynamic:TracIn:ParamChangeInstance}
  \wT - \wT[t - 1]
  =
    -
    \frac{\lrT}{\abs{\batchT}}
    \sum_{\zIBase \in \batchT}
      {\nabla_{\w} \risk{\zI}{\wTOne}}
  \text{,}
\end{equation}
\noindent
where $\lrT$ is iteration~$t$'s learning rate.

Combining Eqs.~\eqref{eq:Estimators:GradientBased:Dynamic:Tracin:DatasetGroup:IndividualInstance} to~\eqref{eq:Estimators:GradientBased:Dynamic:TracIn:ParamChangeInstance}, the \keyword{TracIn{} pointwise influence estimator} is
\begin{equation}%
  \labelAndRemember{eq:Estimators:GradientBased:TracIn}{%
    \baseInfFunc{\infEstSym_{\text{TracIn{}}}}{\zIBase}{\z_{\teStr}}
      \coloneqq
      \sum_{\substack{t \\ \zIBase \in \batchT}}
        \frac{\lrT}
             {\abs{\batchT}}
        \,
        \dotprod{{\nabla_{\w} \risk{\zI}{\wTOne}}}
                {{\nabla_{\w} \risk{\zTe}{\wTOne}}}
  }
  \text{,}
\end{equation}
\noindent
with the complete TracIn{} influence estimation procedure shown in Alg.~\ref{alg:GradientBased:Dynamic:TracIn}.

\noindent
\textbf{A More ``Practical'' TracIn{}}
Training's stochasticity can negatively affect the performance of both ideal TracIn{}~\eqref{eq:Estimators:GradientBased:Dynamic:TracInIdeal} and the TracIn{} influence estimator~\eqref{eq:Estimators:GradientBased:TracIn}.
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~\citep{Hammoudeh:2022:GAS}.
This is despite identical training instances always having the same \textit{expected} TracIn{} influence.

\citet{Pruthi:2020:TracIn} recognize randomness's effect on TracIn{} and propose the \keyword{TracIn{} Checkpoint influence estimator}~(\tracin{}CP{}) as a ``practical'' alternative.
Rather than retrace all of gradient descent, \tracin{}CP{} considers only a subset of the training iterations (i.e.,~checkpoints) ${\mathcal{T} \subseteq \setint{T}}$.
More importantly, at each ${t \in \mathcal{T}}$, \textit{all} training instances are analyzed -- not just those in recent batches.
Eq.~\eqref{eq:Estimators:GradientBased:TracInCP} formalizes \tracin{}CP{}, with its modified influence estimation procedure shown in Alg.~\ref{alg:GradientBased:Dynamic:TracInCP}.
\begin{equation}%
  \labelAndRemember{eq:Estimators:GradientBased:TracInCP}{%
    \baseInfFunc{\infEstSym_{\text{\tracin{}CP}}}{\zIBase}{\z_{\teStr}}
      \coloneqq
      \sum_{t \in \mathcal{T}}
        \lrT \, \dotprod{{\nabla_{\w} \risk{\zI}{\wTOne}}}{{\nabla_{\w} \risk{\zTe}{\wTOne}}}
  }
\end{equation}

Observe that, unlike TracIn{}, \tracin{}CP{} assigns identical training instances the same influence estimate.
Therefore, \tracin{}CP{} more closely estimates expected influence than TracIn{}.
\citet{Pruthi:2020:TracIn} use \tracin{}CP{} over TracIn{} in much of their empirical evaluation.
Other work has also shown that \tracin{}CP{} routinely outperforms TracIn{} on many tasks~\citep{Hammoudeh:2022:GAS}.

\begin{figure}[t]
  \centering
  \begin{minipage}[t]{0.49\textwidth}
    \begin{algorithm}[H]
      {%
        \footnotesize%
        \caption{TracIn{} influence estimation}\label{alg:GradientBased:Dynamic:TracIn}
        %
\begin{algorithmic}[1]
  \setstretch{1.22}%
  \Require Training param.\ set~$\Theta$;{}
           iteration count~$T$;{}
           batches ${\batchT[1], \ldots, \batchT[T]}$;{}
           learning rates ${\lrT[1], \ldots, \lrT[\nItr]}$;{}
           training instance~$\zIBase$;{}
           and
           test example~$\z_{\teStr}$

  \Ensure TracIn{} influence estimate~$\baseInfFunc{\infEstSym_{\text{TracIn{}}}}{\zIBase}{\z_{\teStr}}$

  %
    \State $\widehat{\influence} \gets 0$
    \For{$t \gets 1 \textbf{ to } T$}
      \If{${\zIBase \in \batchT}$}
        \State ${\wT[t - 1] \gets \Theta\sbrack{t}}$
        %
      %
        %
        \State {%
          \scriptsize%
          $\widehat{\influence} \gets \widehat{\influence} %
                            + \frac{\lrT}{\abs{\batchT}} %
                              \dotprod{{\nabla_{\w} \risk{\zI}{\wTOne}}}{{\nabla_{\w} \risk{\zTe}{\wTOne}}}$%
        }%
      %
      \EndIf%
    \EndFor%
    \State \Return $\widehat{\influence}$%
  %
\end{algorithmic}
       }%
    \end{algorithm}
  \end{minipage}
  \hfill
  \begin{minipage}[t]{0.455\textwidth}
    \begin{algorithm}[H]
      {%
        \footnotesize%
        \caption{\tracin{}CP{} influence estimation}\label{alg:GradientBased:Dynamic:TracInCP}
        %
\begin{algorithmic}[1]
  \setstretch{1.22}%
  \Require Training param.\ set~$\Theta$;{}
           iteration subset~$\mathcal{T}$;{}
           %
           learning rates ${\lrT[1], \ldots, \lrT[\nItr]}$;{}
           training instance~$\zIBase$;{}
           and
           test example~$\z_{\teStr}$

  \Ensure \tracin{}CP{} influence est.~$\baseInfFunc{\infEstSym_{\text{\tracin{}CP}}}{\zIBase}{\z_{\teStr}}$

  %
    \State $\widehat{\influence} \gets 0$
    \For{\textbf{each} $t \in \mathcal{T}$}
      \State ${\wT[t - 1] \gets \Theta\sbrack{t}}$
      %
      %
      \State {%
        \scriptsize%
        $\widehat{\influence} \gets \widehat{\influence} %
                          %
                          + \lrT
                            \dotprod{{\nabla_{\w} \risk{\zI}{\wTOne}}}{{\nabla_{\w} \risk{\zTe}{\wTOne}}}$%
      }
    \EndFor
    \State \Return $\widehat{\influence}$
  %
\end{algorithmic}
       }%
    \end{algorithm}
  \end{minipage}
\end{figure}

\begin{remark}
  \citeauthor{Pruthi:2020:TracIn}'s empirical evaluation uses ${\abs{\mathcal{T}} \ll T}$.
  For example, when identifying mislabeled examples using \tracin{}CP{}, \citeauthor{Pruthi:2020:TracIn} evaluate every 30th~iteration.
  Furthermore, \citeauthor{Pruthi:2020:TracIn} note that prioritizing the small number of checkpoints where $\z_{\teStr}$'s loss changes significantly generally outperforms evaluating a larger number of evenly-spaced checkpoints.
\end{remark}

\paragraph{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 \tracin{}CP{}'s time complexity since it is simpler to derive.
From Alg.~\ref{alg:GradientBased:Dynamic:TracInCP}, each checkpoint in ${\mathcal{T}}$ requires $n$, $p$\=/dimensional dot products making \tracin{}CP{}'s complexity $\bigO{n p \abs{\mathcal{T}}}$.
For vanilla TracIn{}, consider Alg.~\ref{alg:GradientBased:Dynamic:TracIn}.
For each iteration ${t \in \setint{T}}$, a $p$\=/dimensional dot product is performed for each instance in $\batchT$.
Let ${b \coloneqq \max_{t} \abs{\batchT}}$ denote the maximum batch size, then TracIn{}'s time complexity is $\bigO{b p T}$.
In the worst case where ${\forall_{t} \, \batchT = \mathcal{D}}$ (full-batch gradient descent), TracIn{} time complexity is $\bigO{\nTr\dimW\nItr}${}.

Recall that, by definition, ${\abs{\mathcal{T}} \leq T}$ meaning \tracin{}CP{} is \textit{asymptotically} faster than TracIn{}.
However, this is misleading.
In practice, \tracin{}CP{} is generally \textit{slower} than TracIn{} as \citeauthor{Pruthi:2020:TracIn} note.

Since each gradient calculation is independent, TracIn{} and \tracin{}CP{} are fully parallelizable.
Table~\ref{tab:InfluenceEstimators:Comparison} treats the level of concurrency as a constant factor, making the space complexity of both TracIn{} and \tracin{}CP{} $\bigO{\nTr + \dimW}${}.

Lastly, as detailed in Alg.~\ref{alg:GradientBased:Dynamic:Training}, 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~$\bigO{\dimW\nItr}${}.
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.

\paragraph{Strengths and Weaknesses}%
\label{sec:Estimators:GradientBased:Dynamic:TracIn:StrengthsWeaknesses}

TracIn{} and \tracin{}CP{} avoid many of the primary pitfalls associated with static, gradient-based estimators.

First, recall from Section~\ref{sec:Estimators:GradientBased:Static:IF} 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 accuracy%
\footnote{%
  Last layer only TracIn{} is also referred to as \tracin{}\=/Last{}.
  \citet{Yeh:2022:FirstBetterLast} 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 \textit{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 \textit{uninfluential} at the end of training.
Unlike static estimators, dynamic methods like TracIn{} may still be able to detect these instances.
See Section~\ref{sec:Estimators:GradientBased:TradeOff} 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~\citep{Kingma:2015:Adam}) significantly accelerate model convergence~\citep{Qian:1999:MomentumGradientDescent,Duchi:2011:Adagrad,Kingma:2015:Adam}.
To align more closely with these sophisticated optimizers, Eq.~\eqref{eq:Estimators:GradientBased:TracIn} and Alg.~\ref{alg:GradientBased:Dynamic:TracIn} would need to change significantly.
For context, Section~\ref{sec:Estimators:GradientBased:Dynamic:HyDRA} details another dynamic estimator, \textsc{HyDRA}{}, which incorporates support for just momentum with the resulting increase in estimator complexity substantial.

\paragraph{Related Methods}

TracIn{} has been adapted by numerous derivative/heuristic variants.
For example, \keyword{\tracin{}\=/Last{}} is identical to vanilla TracIn{} except gradient vectors ${\nabla_{\w} \risk{\zI}{\wTOne}}$ and ${\nabla_{\w} \risk{\zTe}{\wTOne}}$ only consider the model's final linear layer~\citep{Pruthi:2020:TracIn}.
This can make TracIn{} significantly faster at the risk of (significantly) worse accuracy~\citep{Yeh:2022:FirstBetterLast}.

As a counter to the disadvantages of solely considering a model's last layer,%
\footnote{See Section~\ref{sec:Estimators:GradientBased:Static:RepresenterPoint:StrengthWeaknesses} for an extended discussion of last-layer similarity.}
TracIn{}'s authors subsequently proposed
\keyword{TracIn{} word embeddings}~(\tracin{}WE), which targets large language models and considers only the gradients in those models' word embedding layer~\citep{Yeh:2022:FirstBetterLast}.
Since language-model word embeddings can still be very large (e.g.,~BERT\=/Base's word embedding layer has 23M~parameters~\citep{Devlin:2019:Bert}), the authors specifically use the gradients of only those tokens that appear in both training instance~$\zIBase$ and test instance~$\z_{\teStr}$.

\citet{Pruthi:2020:TracIn} also propose \keyword{TracIn{} Random Projection}~(\tracin{}RP{}) -- a low-memory version of TracIn{} that provides unbiased estimates of~$\infEstSym_{\text{TracIn{}}}$ (i.e.,~an estimate of an estimate).
Intuitively, \tracin{}RP{} 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~\eqsmall{${\mathcal{N}\big(0,\frac{1}{d}\big)}$}.
These low-memory gradient ``sketches'' are used in place of the full gradient vectors in Eq.~\eqref{eq:Estimators:GradientBased:TracIn} \citep{Woodruff:2014:SketchingLinearAlgebra}.
\tracin{}RP{} is primarily targeted at applications where $p$ is sufficiently large that storing the full training set's gradient vectors~(${\forall_{t,i}~{\nabla_{\w} \risk{\zI}{\wTOne}}}$) is prohibitive.

Note also that TracIn{} can be applied to any iterative, gradient-based model, including those that are non-parametric.
For example, \citepos{Brophy:2022:TreeInfluence} \keyword{BoostIn{}} adapts TracIn{} for gradient-boosted decision tree ensembles.

TracIn{} has also been used outside of supervised settings.
For example, \citet{Kong:2021:VaeTracIn} apply TracIn{} to unsupervised learning, in particular density estimation;
they
propose \keyword{variational autoencoder TracIn{}}~(VAE\=/\tracin{}{}), which quantifies the TracIn{} influence in $\beta$\=/VAEs~\citep{Higgins:2017:BetaVAE}.
Moreover,
\citepos{Thimonier:2022:TracInAD} \keyword{TracIn{} anomaly detector}~(\tracin{}AD) functionally estimates the distribution of influence estimates -- using either \tracin{}CP{} or VAE\=/\tracin{}{}.
\tracin{}AD{} then marks as anomalous any test instance in the tail of this ``influence distribution''.

\subsubsection{\textsc{HyDRA}{} -- Hypergradient Data Relevance Analysis}%
\label{sec:Estimators:GradientBased:Dynamic:HyDRA}

Unlike TracIn{} which uses a novel definition of influence~\eqref{eq:Estimators:GradientBased:Dynamic:TracInIdeal},
\citepos{Chen:2021:Hydra} \keyword{hypergradient data relevance analysis}~(\textsc{HyDRA}) estimates the leave\=/one\=/out influence~\eqref{eq:Estimators:RetrainBased:LOO}.
\textsc{HyDRA}{} leverages the same Taylor series-based analysis as \citepos{Koh:2017:Understanding} influence functions.
The key difference is that \textsc{HyDRA}{} addresses a fundamental mismatch between influence functions' assumptions and deep models.

Section~\ref{sec:Estimators:GradientBased:Static:IF} explains that influence functions consider infinitesimally perturbing the weight of training sample~$\zIBase$ by~${\epsilon_{\trIdx}}$.
Recall that the change in $\z_{\teStr}$'s test risk w.r.t.\ to this infinitesimal perturbation is
\begin{equation}
  \label{eq:Estimators:GradientBased:Static:Hydra:LossDerivEps}
  \frac{d \risk{\z_{\teStr}}{\wT[T]}}
       {d \epsilon_{\trIdx}}
  %
  =
  \frac{\partial \risk{\z_{\teStr}}{\wT[T]}}
       {\partial \wT[T]}
  ^{\intercal}
  \,
  \frac{d \wT[T]}
       {d \epsilon_{\trIdx}}
  =
  \frac{\partial \risk{\z_{\teStr}}{\wT[T]}}
       {\partial \wT[T]}
  ^{\intercal}
  \,
  \hyperGradTI[\nItr]
\end{equation}
where
\eqsmall{${\hyperGradTI[\nItr] \coloneqq \frac{d \wFin_{+\epsI}} {d \epsilon_{\trIdx}}}$}
denotes the $p$\=/dimensional \keyword{hypergradient} of training instance~$i$ at the end of training.

\citepos{Koh:2017:Understanding} assumptions of differentiability and strict convexity mean that Eq.~\eqref{eq:Estimators:GradientBased:Static:Hydra:LossDerivEps} has a closed form.
However, deep neural models are not convex.
Under non-convex gradient descent without momentum and with $L_2$ regularization, ${\wT \coloneqq \wT[t - 1] - \lrT \gradT[\itr - 1]}$ where gradient%
\footnote{%
  Eq.~\eqref{eq:Estimators:GradientBased:Dynamic:HyDRA:Grad}'s definition of risk with weight decay is slightly different than in Section~\ref{sec:Estimators:GradientBased:Static:RepresenterPoint} where ${2\wdecay}$ is used.
  This difference is done to align more closely with \citepos{Chen:2021:Hydra} original formulation.%
}
\begin{equation}\label{eq:Estimators:GradientBased:Dynamic:HyDRA:Grad}
  \gradT[\itr - 1]
  \coloneqq
    \nabla_{\w}
      \risk{\batchT}{\wTOne}
      %
      %
      %
      %
      %
      %
      %
      %
    +
    \wdecay \wT[t - 1]
  \text{.}
\end{equation}
\noindent%
The exact definition of gradient~$\gradT[\itr - 1]$ depends on the specific contents of batch~$\batchT$ so for simplicity, we encapsulate the batch's contribution to the gradient using catch-all term~${\nabla_{\w} \risk{\batchT}{\wTOne}}$.

Using Eq.~\eqref{eq:Estimators:GradientBased:Dynamic:HyDRA:Grad},
hypergradient~\eqsmall{$\hyperGradTI[\nItr]$} can be defined recursively as
\begin{align}
  \hyperGradTI[\nItr]
  \coloneqq
  \frac{d \wFin_{+\epsI}}
       {d \epsilon_{\trIdx}}
  &=
  \frac{d }
       {d \epsilon_{\trIdx}}
  \left(
    \wTEpsI[T - 1]
    -
    \lrT \gradT[\itr - 1]
  \right)
  \\
  &=
  \hyperGradTI[T - 1]
  -
  \lrT[T]
  \frac{d }
       {d \epsilon_{\trIdx}}
  \left(
    \nabla_{\w}
    \risk{\batchFin}{\wTEpsI[\nItr - 1]}
    +
    \wdecay
    \wTEpsI[T - 1]
  \right)
  \\
  &=
  (1 - \lrT[T] \wdecay) \hyperGradTI[T - 1]
  -
  \lrT
  \,
  \frac{d }
       {d \epsilon_{\trIdx}}
  \,
  \nabla_{\w}
  \risk{\batchFin}{\wTEpsI[\nItr - 1]}
  \label{eq:Estimators:GradientBased:Dynamic:Hydra:FinUnrolledHypergrad}
\end{align}
\noindent
The recursive definition of hypergradient~$\hyperGradTI[\nItr]$ needs to be unrolled all the way back to initial parameters~$\wT[0]$.

The key takeaway from Eq.~\eqref{eq:Estimators:GradientBased:Dynamic:Hydra:FinUnrolledHypergrad} is that training hypergradients affect the model parameters \textit{throughout all of training}.
By assuming a convex model and loss, \citepos{Koh:2017:Understanding} simplified formulation ignores this very real effect.
As \citet{Chen:2021:Hydra} observe, hypergradients often cause non-convex models to converge to a vastly different risk minimizer.
By considering the hypergradients' cumulative effect, \textsc{HyDRA}{} can provide more accurate LOO{} estimates than influence functions on non-convex models -- albeit via a significantly more complicated and computationally expensive formulation.

\noindent
\textbf{Unrolling Gradient Descent Hypergradients}
The exact procedure to unroll \textsc{HyDRA}{}'s hypergradient~$\hyperGradTI[\nItr]$ is non-trivial.
For the interested reader, supplemental Section~\ref{sec:App:HypergradientUnrolling} provides hypergradient unrolling's full derivation for vanilla gradient descent without momentum.
Below, we briefly summarize Section~\ref{sec:App:HypergradientUnrolling}'s important takeaways, and Section~\ref{sec:App:HypergradientUnrolling}'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~$\batchT$.%
\footnote{%
  For clarity, this is \textit{not} the inverse Hessian ${(\hessFin)^{-1}}$ used by influence functions.%
}
This significantly slows down \textsc{HyDRA}{} (by a factor of about 1,000$\times$~\citep{Chen:2021:Hydra}).
As a workaround, \citet{Chen:2021:Hydra} propose treating these risk Hessians as all zeros, proving that, under mild assumptions, the approximation error of this simplified version of \textsc{HyDRA}{} is bounded.
Alg.~\ref{alg:GradientBased:Dynamic:Hydra} shows \keyword{\textsc{HyDRA}{}'s fast approximation algorithm} without Hessians for vanilla gradient descent.%
\footnote{%
  See \textsc{HyDRA}{}'s original paper \citep{Chen:2021:Hydra} for the fast approximation algorithm with momentum.%
}
After calculating the final hypergradient, substituting
\eqsmall{${\hyperGradTI[\nItr]}$}
into Eq.~\eqref{eq:Estimators:GradientBased:Static:Hydra:LossDerivEps} with \eqsmall{${\epsilon_{\trIdx} = -\frac{1}{n}}$}%
\footnote{%
  ${\epsilon_{\trIdx} = -\frac{1}{n}}$ is equivalent to deleting instance $\zIBase$ from the training set.
  Influence functions follow the same procedure for~$\epsilon_{\trIdx}$.
  See Eqs.~\eqref{eq:Estimators:GradientBased:Static:LossDerivEps} and~\eqref{eq:Estimators:GradientBased:Static:IF}.%
}
yields training instance~$\zIBase$'s \keyword{\textsc{HyDRA}{} pointwise influence estimator}
\begin{equation}
  \labelAndRemember{eq:Estimators:GradientBased:Dynamic:HyDRA}{%
    \baseInfFunc{\infEstSym_{\textsc{HyDRA}}}{\zIBase}{\z_{\teStr}}
    \coloneqq
      -
      \frac{1}{n}
      \nabla_{\w}
      \risk{\z_{\teStr}}{\wT[T]}
      ^{\intercal}
      \,
      \hyperGradTI[\nItr]
  }
  \text{.}
\end{equation}

\begin{figure}[t]
  \centering
  \begin{minipage}{0.72\textwidth}
    \begin{algorithm}[H]
      {%
        \footnotesize%
        \caption{Fast \textsc{HyDRA}{} influence estimation for gradient descent without momentum}\label{alg:GradientBased:Dynamic:Hydra}
        %
\begin{algorithmic}[1]
  \setstretch{1.22}%
  \Require Training parameter set~$\Theta$;{}
      final parameters~$\wT[T]$;{}
      training set size~$n$;{}
      iteration count~$T$;{}
      batches ${\batchT[1], \ldots, \batchT[T]}$;{}
      learning rates ${\lrT[1], \ldots, \lrT[\nItr]}$;{}
      weight decay~$\wdecay$;{}
      training instance~$\zIBase$;{}
      and
      test example~$\z_{\teStr}$

  \Ensure \textsc{HyDRA}{} influence estimate~$\baseInfFunc{\infEstSym_{\textsc{HyDRA}}}{\zIBase}{\z_{\teStr}}$

  \State $\hyperGradTI[0] \gets \vec{0}$
          \algcomment{Initialize to zero vector}
  \For{$t \gets 1 \textbf{ to } T$}
    \If{${\zIBase \in \batchT}$}
      \State ${\wT[t - 1] \gets \Theta\sbrack{t}}$
      \State $\hyperGradTI \gets (1 - \lrT \wdecay)\hyperGradTI[\itr - 1] - \frac{\lrTn}{\abs{\batchT}}\nabla_{\w} \risk{\zIBase}{\wT[t - 1]}$
    \Else
      \State $\hyperGradTI \gets (1 - \lrT \wdecay)\hyperGradTI[\itr - 1]$
    \EndIf
  \EndFor
  \State $\widehat{\influence} \gets -\frac{1}{n} \nabla_{\w} \risk{\z_{\teStr}}{\wT[T]} ^{\intercal} \, \hyperGradTI[\nItr]$
          \algcomment{Influence estimate}
  \State \Return$\widehat{\influence}$
  %
\end{algorithmic}
       }%
    \end{algorithm}
  \end{minipage}
\end{figure}

\noindent
\textbf{Relating \textsc{HyDRA}{} and TracIn{}}
When ${\wdecay = 0}$ or weight decay's effects are ignored (as done by TracIn{}), \textsc{HyDRA}{}'s fast approximation for vanilla gradient descent simplifies to
\begin{align}
  \baseInfFunc{\infEstSym_{\textsc{HyDRA}}}{\zIBase}{\z_{\teStr}}
    &\approx
      -\frac{1}{n}
      \nabla_{\w} \risk{\z_{\teStr}}{\wT[T]}^{\intercal}
      %
        \sum_{\substack{t \\ \zIBase \in \batchT}}
          - \frac{\lrTn}
                 {\abs{\batchT}}
            \nabla_{\w} \risk{\zIBase}{\wT[t - 1]}
      %
    \\
    &=
      \sum_{\substack{t \\ \zIBase \in \batchT}}
        \frac{\lrT}
             {\abs{\batchT}}
        \nabla_{\w} \risk{\z_{\teStr}}{\wT[T]}^{\intercal}
        \nabla_{\w} \risk{\zIBase}{\wT[t - 1]}
    \label{eq:Estimators:GradientBased:Hydra:FastNoWeightDecay}
    \\
    &=
      \nabla_{\w} \risk{\z_{\teStr}}{\wT[T]}^{\intercal}
      %
        \sum_{\substack{t \\ \zIBase \in \batchT}}
          \frac{\lrT}
               {\abs{\batchT}}
          \nabla_{\w} \risk{\zIBase}{\wT[t - 1]}
      %
    \text{.}
\end{align}
\noindent%
Eq.~\eqref{eq:Estimators:GradientBased:Hydra:FastNoWeightDecay} is very similar to TracIn{}'s definition in Eq.~\eqref{eq:Estimators:GradientBased:TracIn}, despite the two methods \textit{estimating different definitions of influence} (LOO{} vs.\ ideal TracIn{}~\eqref{eq:Estimators:GradientBased:Dynamic:TracInIdeal}).
The only difference between~\eqref{eq:Estimators:GradientBased:Hydra:FastNoWeightDecay} and~\eqref{eq:Estimators:GradientBased:TracIn} is that \textsc{HyDRA}{} always uses final test gradient ${\nabla_{\w} \risk{\z_{\teStr}}{\wT[T]}}$ while TracIn{} uses each iteration's test gradient ${\nabla_{\w} \risk{\z_{\teStr}}{\wT[t - 1]}}$

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

\paragraph{Time, Space, and Storage Complexity}

When unrolling the $T$~training iterations,
\textsc{HyDRA}{}'s fast approximation performs a $p$\=/dimensional (hyper)gradient calculation for each of the $n$~training instances.
If \textsc{HyDRA}{}'s full version with Hessian vector products is used, \citepos{Agarwal:2017} Hessian approximation algorithm estimates each HVP in $\bigO{\dimW}${} time and space.
Therefore, the fast and standard versions of \textsc{HyDRA}{} both have full time complexity $\bigO{\nTr\dimW\nItr}${} -- same as TracIn{}, albeit with potentially much worse constant factors.

Observe that each hypergradient~$\hyperGradTI[\nItr]$ only needs to be computed once and can be reused for each test instance.
Therefore, the fast and standard version of \textsc{HyDRA}{} have incremental time complexity of just $n$~gradient dot products -- $\bigO{\nTr\dimW}${} complexity total.
This incremental complexity is much faster than TracIn{} and asymptotically equivalent to influence functions.
In practice though, \textsc{HyDRA}{}'s incremental cost is much lower than that of influence functions.

Alg.~\ref{alg:GradientBased:Dynamic:Hydra} requires storing vector~$\hyperGradTI$ throughout \textsc{HyDRA}{}'s entire unrolling procedure, where each training instance's hypergradient takes $\bigO{\dimW}${} space.
To analyze all training instances simultaneously, \textsc{HyDRA}{} requires $\bigO{\nTr\dimW}${} total space.
In contrast, TracIn{} only requires $\bigO{\nTr + \dimW}${} 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 $\bigO{\dimW}${} for both fast and standard \textsc{HyDRA}{}.

Like TracIn{}, \textsc{HyDRA}{} requires storing model parameters ${\Theta \subseteq  \set{\wT[0], \ldots, \wT[T - 1]}}$ making its minimum storage complexity~$\bigO{\dimW\nItr}${}.
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~$\bigO{\nTr\dimW}${}.
This makes \textsc{HyDRA}{}'s total storage complexity $\bigO{\dimW\nItr + \nTr\dimW}${}.

\begin{remark}
  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~$\bigO{\dimW\nItr}${} or~$\bigO{\nTr\dimW}${} -- both of which are still substantial.
\end{remark}

\paragraph{Strengths and Weaknesses}

\textsc{HyDRA}{} and TracIn{} share many of the same strengths.
For example, \textsc{HyDRA}{} does not require assumptions of convexity or stationarity.
Moreover, as a dynamic method, \textsc{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~\ref{sec:Estimators:GradientBased:TradeOff} for more discussion).

\textsc{HyDRA}{} also has some advantages over TracIn{}.
For example,
as shown in Alg.~\ref{alg:GradientBased:Dynamic:TracIn}, TracIn{} requires that each \textit{test} instance be retraced through the entire training process.
This significantly increases TracIn{}'s incremental time complexity.
In contrast, \textsc{HyDRA}{} only unrolls gradient descent for the \textit{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, \textsc{HyDRA}{} is much faster than TracIn{} -- potentially by orders of magnitude.
In addition,
\textsc{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.

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

\paragraph{Related Methods}

The method most closely related to \textsc{HyDRA}{} is \citepos{Hara:2019:SgdInfluence} \keyword{SGD\=/influence}.
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 \textsc{HyDRA}{}, \citeauthor{Hara:2019:SgdInfluence} assume that the model and loss function are convex.
Next, SGD\=/influence primarily applies unrolling to quantify the Cook's distance, \eqsmall{${\wT[T] - \wTSub[T]{\trIdx}}$}.
To better align their approach with dataset influence, \citeauthor{Hara:2019:SgdInfluence} 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.

\citet{Terashita:2021:InfluenceGAN} 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.~\ref{sec:Estimators:GradientBased:Static:IF:RelatedMethods}), \citepos{Schioppa:2022:ScaledUpInfluenceFunctions} basic approach to scale up influence functions via faster Hessian calculation could similarly be applied to speed up \textsc{HyDRA}{}'s standard (non-fast) algorithm.

\subsection{Trade-off between Gradient Magnitude and Direction}%
\label{sec:Estimators:GradientBased:TradeOff}

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:

\noindent
(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.

\noindent
(2)~Either vector has a large magnitude, e.g.,~\eqsmall{$\norm{\nabla_{\w} \risk{z}{\theta}}$}.
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~\citep{Sui:2021:LocalJacobianRepPt}.
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~\citep{Sui:2021:LocalJacobianRepPt}.
\citet{Barshan:2020:RelatIF} describe such training instances as \keyword{globally influential}.
However, globally influential training instances provide very limited insight into individual model predictions.
As \citeauthor{Barshan:2020:RelatIF} note, \keyword{locally influential} training instances are generally much more relevant and insightful when analyzing specific predictions.

To yield a more semantically meaningful influence ranking, \citeauthor{Barshan:2020:RelatIF} propose the \keyword{$\theta$\=/relative influence functions estimator}~(RelatIF), which normalizes \citepos{Koh:2017:Understanding} influence functions' estimator by HVP magnitude
\eqsmall{${\big\lVert \invHessFin \, \gradW \riskIFin \big\rVert }$}.%
\footnote{%
  Note that this HVP is different than ${ s_{\text{test}} \coloneqq {(\hessFin)^{-1}} \nabla_{\w} \risk{\z_{\teStr}}{\wT[T]} }$ in Eq.~\eqref{eq:Estimators:GradientBased:Static:IF:STest}.%
}
Formally,
\begin{equation}%
  \labelAndRemember{eq:Estimators:GradientBased:TradeOff:RelatIF}{%
    \baseInfFunc{\infEstSym_{\text{RelatIF}}}{\zIBase}{\z_{\teStr}}
      \coloneqq
      \frac{\baseInfFunc{\infEstSym_{\textsc{IF}}}{\zIBase}{\z_{\teStr}}}
           {\norm{\invHessFin \, \gradW \riskIFin}}
  }
    =
    \frac{1}
         {n}
    \,
    \frac{%
            \nabla_{\w} \risk{\z_{\teStr}}{\wT[T]}^{\intercal}
            {(\hessFin)^{-1}}
            \nabla_{\w} \risk{\zIBase}{\wT[T]}
         }
         {\norm{\invHessFin \, \gradW \riskIFin}}
  \text{.}
\end{equation}
\noindent%
RelatIF{}'s normalization inhibits training gradient magnitude
${\big\lVert \nabla_{\w} \risk{\zIBase}{\wT[T]} \big\rVert}$
dominating the influence estimate.

RelatIF{}'s biggest limitation is the need to estimate an HVP \textit{for every training instance}.
As discussed in Section~\ref{sec:Estimators:GradientBased:Static:IF:StrengthWeaknesses}, HVP estimation is expensive and often highly inaccurate in deep models.
To work around these issues in their evaluation of RelatIF{}, \citeauthor{Barshan:2020:RelatIF} use either very small neural models or just consider a large model's final layer, both of which can be problematic.

\citet{Hammoudeh:2022:GAS} make a similar observation as \citeauthor{Barshan:2020:RelatIF} but motivate it differently.
By the chain rule, gradient vectors decompose as
\begin{equation}\label{eq:Estimators:GradientBased:TradeOff:ChainRule}
  \nabla_{\w} \risk{z}{\theta}
    \coloneqq
    \frac{\partial \lDecFunc{x}{\theta}{y}}
         {\partial \theta}
    =
    \frac{\partial \lDecFunc{x}{\theta}{y}}
         {\partial \decFunc{x}{\theta}}
    \,
    \frac{\partial \decFunc{x}{\theta}}
         {\partial \theta}
  \text{.}
\end{equation}
\noindent
\citeauthor{Hammoudeh:2022:GAS} note that for many common loss functions (e.g.,~squared, binary cross-entropy), loss value \eqsmall{$\lDecFunc{x}{\theta}{y}$}
induces a strict ordering over loss norm
\eqsmall{$%
  %
  \big\lVert
    \frac{\partial \lDecFunc{x}{\theta}{y}}
         {\partial \decFunc{x}{\theta}}
  \big\rVert%
  %
$}.
\citeauthor{Hammoudeh:2022:GAS} term this phenomenon a \keyword{low-loss penalty}, 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, \citet{Hammoudeh:2022:GAS} propose \keyword{renormalized influence} which replaces all gradient vectors -- both training and test -- in an influence estimator with the corresponding \keyword{unit vector}.
Renormalization can be applied to any gradient-based estimator.
For example, \citeauthor{Hammoudeh:2022:GAS} observe that renormalized \tracin{}CP{}, which they term \keyword{gradient aggregated similarity}~(\textsc{GAS}),
\begin{equation}%
  \labelAndRemember{eq:Estimators:GradientBased:TradeOff:GAS}{%
    \baseInfFunc{\infEstSym_{\textsc{GAS}}}{\zIBase}{\z_{\teStr}}
    \coloneqq
    \sum_{t \in \mathcal{T}}
      \lrT
      \,
      \frac{\dotprod{{\nabla_{\w} \risk{\zI}{\wTOne}}}{{\nabla_{\w} \risk{\zTe}{\wTOne}}}}
           {%
             \norm{{\nabla_{\w} \risk{\zI}{\wTOne}}}
             \,
             \norm{{\nabla_{\w} \risk{\zTe}{\wTOne}}}%
           }%
  }
  \text{,}
\end{equation}
\noindent
is particularly effective at generating influence rankings.
\citeauthor{Hammoudeh:2022:GAS} also provide a renormalized version of influence functions,%
\begin{equation}%
  \labelAndRemember{eq:Estimators:GradientBased:TradeOff:RenormIF}{%
    \baseInfFunc{\infEstSym_{\text{RenormIF}}}{\zIBase}{\z_{\teStr}}
      \coloneqq
      \frac{\baseInfFunc{\infEstSym_{\textsc{IF}}}{\zIBase}{\z_{\teStr}}}
           {\norm{\nabla_{\w} \risk{\zI}{\wFin}}}
  }
    =
    \frac{1}
         {n}
    \,
    \frac{%
            \nabla_{\w} \risk{\z_{\teStr}}{\wT[T]}^{\intercal}
            {(\hessFin)^{-1}}
            \nabla_{\w} \risk{\zIBase}{\wT[T]}
         }
         {\norm{\nabla_{\w} \risk{\zI}{\wFin}}}
  \text{.}
\end{equation}
\noindent
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.%
\footnote{%
  \citet{Hammoudeh:2022:GAS} 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 \textit{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.

\begin{remark}
  \citeauthor{Barshan:2020:RelatIF}'s RelatIF{} and \citeauthor{Hammoudeh:2022:GAS}'s renormalization do not change the corresponding influence estimators' time and space complexities.
\end{remark}

  %
\section{Applications of Influence Analysis}%
\label{sec:Applications}

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~\citep{Han:2020:InfluenceToxicSpeech}, social network graph labeling~\citep{Zhang:2021:ActiveInfluenceGraphs}, user engagement detection~\citep{Liang:2021:UserEngagementDetection}, medical imaging annotation~\citep{Braun:2022:InfluenceMedicalImaging}, etc.

First,
\keyword{data cleaning} 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.~\citep{Krishnan:2016:ActiveClean,Liu:2018:FinePruning,Krishnan:2019:AlphaClean}.
Intuitively, ``bad'' training instances are generally anomalous, and their features clash with the feature distribution of typical ``clean'' data~\citep{Wojnowicz:2016:InfluenceSketching}.
In practice, overparameterized neural networks commonly memorize these ``bad'' instances to achieve zero training loss~\citep{Hara:2019:SgdInfluence,Feldman:2020:InfluenceEstimation,Pruthi:2020:TracIn,Thimonier:2022:TracInAD}.
As explained in Section~\ref{sec:EstimatorOverview:AlternativeDefinitions}, 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~\citep{Kong:2022:InfluenceDataRelabeling} and the model retrained.

\keyword{Poisoning and backdoor attacks} 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~\citep{Shafahi:2018:PoisonFrogs}.
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~\citep{Fang:2020:InfluenceFunctionsPoisoning,Jagielski:2021:Subpopulation,Oh:2022:RecommenderInteractionPerturbations}.
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~\citep{Chen:2017:Targeted}.

Influence and memorization analysis have also been used to improve \keyword{membership inference attacks}, where the adversary attempts to extract sensitive training data provided only a pretrained (language) model~\citep{Demontis:2019:WhyAttacksTransfer,Cohen:2022:InfluenceMembershipInferenceAttack}.

\keyword{Training set attack defenses} detect and mitigate poisoning and backdoor attacks~\citep{Li:2022:Survey}.
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~\citep{Wallace:2021}, the target of a training set attack can be identified by searching for test instances that have a few exceptionally influential training instances~\citep{Hammoudeh:2022:GAS}.
The training set attack mitigation removes these anomalously influential instances from the training data and then retrains the model~\citep{Wang:2019:NeuralCleanse}.
In addition, influence estimation has been applied to the related task of \keyword{evasion attack detection}, where the training set is pristine and only test instances are perturbed~\citep{Cohen:2020:DetectInfluenceFunctions}.

\keyword{Algorithmic fairness} 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~\citep{Mehrabi:2022:SurveyBiasFairness}.
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~\citep{Angwin:2016:CompasPropublica}.
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~\citep{Awad:2018:MoralMachine}.
Yet, how to quantify the extent to which an algorithm is ``fair'' remains an area of active study~\citep{Dwork:2012:FairnessThroughAwareness,Glymour:2019:MeasuringBiases,Saxena:2019:FairnessFare}.
\citet{Black:2021:LeaveOneOut} propose \keyword{leave\=/one\=/out unfairness} 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 \textit{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.

\keyword{Explainability} attempts to make a black-box model's decisions understandable by humans~\citep{Burkart:2021:ExplainableSupervisedLearning}.
Transparent explanations are critical to achieving user trust of and satisfaction with ML systems~\citep{Lim:2009:ExplainationsIntelligibility,Kizilcec:2016:EffectTransperancyTrust,Zhou:2019:EffectInfluenceUserTrust}.
\keyword{Example-based explanations} communicate why a model made a particular prediction via visual examples~\citep{Cai:2019,Sui:2021:LocalJacobianRepPt} -- e.g.,~training images --  as social science research has shown that humans can understand complex ideas using only examples~\citep{Renkl:2009:ExampleBasedLearning,Renkl:2014:ExampleBasedLearning}.
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, \keyword{normative explanations} -- which collectively establish a ``standard'' for a given class~\citep{Cai:2019} -- 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.

\keyword{Subsampling} reduces the computational requirements of large datasets by training models using only a subset of the training data~\citep{Ting:2018:OptimalSubsampling}.
Existing work has shown that high-quality training subsets can be created by greedily selecting training instances based on their overall influence~\citep{Khanna:2018:FisherKernels,Wang:2020:UnweightedSubsampling}.
Under mild assumptions, \citet{Wang:2020:UnweightedSubsampling} 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~\cite{Braun:2022:InfluenceMedicalImaging}.
Compared to labeling instances u.a.r., \keyword{active learning} reduces labeling costs by prioritizing annotation of particularly salient unlabeled data.
In practice, active learning often simplifies to maximizing the \keyword{add-one-in influence} 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~\citep{Liu:2021:InfluenceActiveLearning,Jia:2021:ScalabilityVsUtility,Zhang:2021:ActiveInfluenceGraphs}.

To enhance the benefit of limited labeled data, influence analysis has been used to create better augmented training data~\citep{Lee:2020:InfluenceAugmentationNetwork,Oh:2021:InfluenceTensorCompletion}.
These influence-guided \keyword{data augmentation} methods outperform traditional random augmentations, albeit with a higher computational cost.
 %
\newcommand{\futureHeading}[1]{%
  \noindent
  \textit{#1}:%
}

\section{Future Directions}%
\label{sec:FutureDirections}

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~\citep{Zhou:2019:EffectInfluenceUserTrust}, which points to the field growing in importance and relevance.
This section identifies important directions we believe influence analysis research should take going forward.

\futureHeading{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~\citep{Feldman:2020:LearningRequiresMemorization}.
Instead, most predictions are moderately influenced by multiple training instances working in concert~\citep{Feldman:2020:InfluenceEstimation,Das:2021:DataSubsetInfluence,Basu:2020:OnSecond}.

As an additional complicating factor, pointwise influence within data-distribution modes is often approximately \keyword{supermodular} where the marginal effect of a training instance's deletion \textit{increases} as more instances from a group are removed~\citep{Hammoudeh:2022:GAS}.
This makes pointwise influence a particularly poor choice for understanding most model behavior.
To date, very limited work has systematically studied group influence~\citep{Koh:2019:GroupEffects,Basu:2020:OnSecond,Hammoudeh:2022:GAS}.
Better group influence estimators could be immediately applied in various domains such as poisoning attacks, core-set selection, and model explainability.

\futureHeading{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~\citep{Steinhardt:2017,Levine:2021:DPA,Jia:2022:CertifiedKNN,Wang:2022:DeterministicAggregation,Hammoudeh:2023:CertifiedRegression}.
These methods can be viewed as upper bounding the training data's group influence -- albeit very coarsely.
Most certified poisoning defenses achieve their bounds by leveraging ``tricks'' associated with particular model architectures (e.g., instance-based learners~\citep{Jia:2022:CertifiedKNN} and ensembles~\citep{Levine:2021:DPA,Wang:2022:DeterministicAggregation}) as opposed to a detailed analysis of a prediction's stability~\citep{Hammoudeh:2023:CertifiedRegression}.
With limited exception~\citep{Jia:2019:KnnShapley}, today's influence estimators do not provide any meaningful guarantee of their accuracy.
Rather, most influence estimates should be viewed as only providing -- at best -- guidance on an instance's ``possible influence.''
Guaranteed or even probabilistic bounds on an instance's influence would enable influence estimation to be applied in settings where more than a ``heuristic approximation'' is required~\citep{Hammoudeh:2023:CertifiedRegression}.

\futureHeading{Improved Scalability}
Influence estimation is slow.
Analyzing each training instance's influence on a single test instance can take several hours or more~\citep{Barshan:2020:RelatIF,Kobayashi:2020:EfficientInfluenceEstimation,Guo:2021:FastIF,Hammoudeh:2022:GAS}.
For influence estimation to be a practical tool, it must be at least an order of magnitude faster.
Heuristic influence analysis speed-ups could prove very useful~\citep{Guo:2021:FastIF,Schioppa:2022:ScaledUpInfluenceFunctions}.
However, the consequences (and limitations) of any empirical shortcuts need to be thoroughly tested, verified, and understood.
Similarly, limited existing work has specialized influence methods to particular model classes~\citep{Jia:2021:ScalabilityVsUtility} or data modalities~\citep{Yeh:2022:FirstBetterLast}.
While application-agnostic influence estimators are useful, their flexibility limits their scalability and accuracy.
Both of these performance metrics may significantly improve via increased influence estimator specialization.

\futureHeading{Surrogate Influence and Influence Transferability}
An underexplored opportunity to improve influence analysis lies in the use of surrogate models~\citep{Sharchilev:2018:TreeInfluence,Jia:2019:TowardsEfficientShapley,Jia:2021:ScalabilityVsUtility,Brophy:2022:TreeInfluence}.
For example, linear surrogates have proven quite useful for model explainability~\citep{Lundberg:2017:SHAP}.
While using only a model's linear layer as a surrogate may be ``overly reductive''~\citep{Yeh:2022:FirstBetterLast}, it remains an open question whether other compact models remain an option.
Any surrogate method must be accompanied by rigorous empirical evaluation to identify any risks and ``blind spots'' the surrogate may introduce~\citep{Rudin:2018:StopExplainingBlackBox}.

\futureHeading{Increased Evaluation Diversity}
Influence analysis has the capability to provide salient insights into why models behave as they do~\citep{Feldman:2020:InfluenceEstimation}.
As an example, \citet{Black:2021:LeaveOneOut} demonstrate how influence analysis can identify potential unfairness in an algorithmic decision.
However, influence estimation evaluation is too often superficial and focuses on a very small subset of possible applications.
For instance, most influence estimation evaluation focuses primarily on contrived data cleaning and mislabeled training data experiments~\citep{Wojnowicz:2016:InfluenceSketching,Koh:2017:Understanding,Khanna:2018:FisherKernels,Ghorbani:2019:DataShapley,Yeh:2018:Representer,Pruthi:2020:TracIn,Chen:2021:Hydra,Terashita:2021:InfluenceGAN,K:2021:RevisitingInfluentialExamples,Sui:2021:LocalJacobianRepPt,Brophy:2022:TreeInfluence,Yeh:2022:FirstBetterLast,Kong:2022:InfluenceDataRelabeling,Kwon:2022:BetaShapley}.
It is unclear how these experiments translate into real-world or adversarial settings, with recent work pointing to generalization fragility~\citep{Basu:2021:InfluenceFunctionsFragile,Bae:2022:InfluenceFunctionsQuestion}.
We question whether these data cleaning experiments -- where specialized methods already exist~\citep{Krishnan:2016:ActiveClean,Krishnan:2019:AlphaClean,Wang:2019:NeuralCleanse} -- adequately satisfy influence analysis's stated promise of providing ``understanding [of] black-box predictions''~\citep{Koh:2017:Understanding}.

\futureHeading{Objective Over Subjective Evaluation Criteria}
A common trope when evaluating an influence analysis method is to provide a test example and display training instances the estimator identified as most similar or dissimilar.
These ``eye test'' evaluations are generally applied to vision datasets~\citep{Koh:2017:Understanding,Yeh:2018:Representer,Jia:2019:KnnShapley,Pruthi:2020:TracIn,Feldman:2020:InfluenceEstimation} and to a limited extent other modalities.
Such experiments are unscientific.
They provide limited meaningful insight given the lack of a ground truth by which to judge the results.
Most readers do not have detailed enough knowledge of a dataset to know whether the selected instances are especially representative. %
Rather, there may exist numerous training instances that are much more similar to the target that the influence estimator overlooked.
Moreover, such visual assessments are known to be susceptible to confirmation and expectancy biases~\citep{Mahoney:1977:PublicationPrejudices,Nakhaeizadeh:2013:ConfirmationBias,Kassin:2013:ForensicConfirmationBias}.

Influence analysis evaluation should focus on experiments that are quantifiable and verifiable w.r.t.\ a ground truth.
 %
\section{Conclusions}\label{sec:Conclusions}

While influence analysis has received increased attention in recent years, significant progress remains to be made.
Influence estimation is computationally expensive and can be prone to inaccuracy.
Going forward, fast certified influence estimators are needed.
Nonetheless, despite these shortcomings, existing applications already demonstrate influence estimation's capabilities and promise.

This work reviews numerous methods with different perspectives on -- and even definitions of -- training data influence.
It would be a mistake to view this diversity of approaches as a negative.
While no single influence analysis method can be applied to all situations, most use cases should have at least one method that fits well.
An obvious consequence then is the need for researchers and practitioners to understand the strengths and limitations of the various methods so as to know which method best fits their individual use case.
This survey is intended to provide that insight from both empirical and theoretical viewpoints.

\section*{Acknowledgments}
  %

  %
  This work was supported by a grant from the Air Force Research Laboratory and the Defense Advanced Research Projects Agency (DARPA) — agreement number FA8750\=/16\=/C\=/0166, subcontract K001892\=/00\=/S05, as well as a second grant from DARPA, agreement number HR00112090135.
  %
  %

\newrefcontext[sorting=nyt]
\renewcommand*{\bibfont}{\small}
\printbibliography%
\newrefcontext[sorting=ynt]

\newpage
\onecolumn
\thispagestyle{empty}
\pagenumbering{arabic}%
\renewcommand*{\thepage}{A\arabic{page}}