# Formatting Instructions for ICLR 2022
Conference Submissions

Antiquus S. Hippocampus, Natalia Cerebro & Amelie P. Amygdale
Department of Computer Science
Cranberry-Lemon University
Pittsburgh, PA 15213, USA
<EMAIL_ADDRESS>
&Ji Q. Ren & Yevgeny LeNet
Department of Computational Neuroscience
University of the Witwatersrand
Joburg, South Africa
<EMAIL_ADDRESS>
Coauthor
Affiliation
Address
email Use footnote for providing further information about author (webpage,
alternative address)— _not_ for acknowledging funding agencies. Funding
acknowledgements go at the end of the paper.

###### Abstract

The abstract paragraph should be indented 1/2 inch (3 picas) on both left and
right-hand margins. Use 10 point type, with a vertical spacing of 11 points.
The word Abstract must be centered, in small caps, and in point size 12. Two
line spaces precede the abstract. The abstract must be limited to one
paragraph.

##  1 Introduction

Recognizing data’s highest agency in defining deep neural networks’ (DNNs)
performance, the pursuit of state-of-the-art has made datasets for training
modern DNNs grow to sizes that can no longer be curated by humans. This has
acutely aggravated data issues like noise and mislabeled data: Noise is
characteristic of tasks, where training data is crawled from the Web (e.g.
machine translation) and where golden-truth labels are heuristically paired to
inputs uszkoreit2010large, leaving ample room for errors and inheriting biases
of the heuristic. Wrong labels can be also introduced by non-expert crowd
annotators who, considering the amount of data to be labeled, are hard to
incentivize for quality within available budgets bowman.

Given the above, a natural way to interpret and fix DNN models would be to
track their bad (or good) predictions down to the training examples that
caused them cook80; koh2017undestanding; yeh, and take appropriate action on
the found examples or annotation policies. Addressing this,
koh2017undestanding proposed _influence functions_ (IFs) as a theoretically
motivated method, grounded in robust statistics cook88, of quantifying the
effect of training examples on predictions: For a query example $z$, IFs find
the most influential example $x$ in training data $\mathcal{D}$ in terms of
absolute change of loss $L$ if $x$ were infinitesimally up-weighted in
$\mathcal{D}$:

$\mathcal{I}_{H}(x,z)=\langle\nabla_{\Theta}L(z),H^{-1}\nabla_{\Theta}L(x)\rangle$
(1)

where $H=\nabla^{2}_{\Theta}L$ is the Hessian of the model at parameters
$\Theta$. The straight-forward IF implementation, using the approximate
Hessian inversion procedure LISSA lissa_paper, has $O(p)$ memory complexity
and $O(r\cdot b\cdot p)$ time complexity, where $r$ is the LISSA iteration
count, $b$ is the batch size and $p=|\Theta|$. Besides the need of careful
tuning of LISSA, the $O(p)$-memory has been the major obstacle on the way to
IF deployment for debugging industry-relevant DNNs with _hundreds of millions_
(or more) training examples and model parameters; thus noise or mislabeling
issues remain unfixed or even undetected, and are adversely impacting
predictions.

In this work, we focus on reducing the IF memory footprint by not
materializing $O(p)$-size gradients and decoupling the required number of $H$
estimations, $O(r\cdot|\mathcal{D}|)$, from the training data size. This
allows to parallelize computation over larger batches and scale to huge
datasets and models. Specifically, we use Arnoldi iteration arnoldi to find
the dominant (in absolute value) eigenvalues of $H$ and their orthonormal
eigenvectors on a random data subset,
$|\mathcal{D}^{\prime}|\ll|\mathcal{D}|$, and then cheaply invert the
diagonalized $H$, avoiding calls to LISSA as well as its convergence and
stability issues. While previous work cached gradients of training points to
improve IFs usability fast_if, it only spares one backward pass per $x$ and
requires to re-estimate the product of the (unstorable) $H^{-1}$ with
$\nabla_{\Theta}L(x)$ every time an influence on $x$ is requested (as $H$ is
Hermitian, the situation is symmetric w.r.t. $x$ and $z$). The crux of our
approach is that instead we cache $H$ in the trivially-invertable diagonalized
form and only for the small-dimensional subspace spanned by a few dominant
eigenvectors, $\tilde{p}\ll p$. Hessian-gradient products are then reduced to
simple scalar-gradient products, which do not need to be materialized in
memory as equation 1 can now be implemented with Jacobian-vector products. In
summary, our approach renders repeated re-estimations of
$H^{-1}\nabla_{\Theta}L(x)$ at every $x$ unnecessary and they are replaced
with the memory- and time-efficient forward-mode differentiations.

Empirically, IFs with Arnoldi iteration achieve speed-ups of 10,000x over the
LISSA-powered IFs koh2017undestanding and of 10x over TracIn tracin, a
heuristic gradient-only alternative to IFs (§5). With this improvement, we
successfully evaluated IFs on both language and vision, full-size Transformer
models (with up to 300M of parameters) in image classification and sequence-
to-sequence tasks trained on 14M (ImageNet) and 100M (Paracrawl) examples.

Note that the standard conditions for the IFs to be a correct influence
estimate, i.e. locally strictly-convex $L\in C^{2}$ koh2017undestanding,
remain in place and their fulfilment would depend on the concrete task,
network, training algorithm and its convergence status. Naturally, the time-
and memory-complexity are also the same, however, our contribution improves
constants hidden in the $O$-notation, and thus permits evaluation of the IFs
on industry-size model and datasets on standard memory-limited hardware. This
opens the way for developers to evaluate IFs on full data/models, and then
decide if IFs are appropriate for the task at hand, rather than to resort to
heuristics from the start. This is encouraging, since the existing brute-force
recipes of “soothing” the $O(p)$ complexity by subsetting parameters, e.g.
focusing on few layers only han-etal-2020-explaining; multistage, is prone to
produce incorrect results fast_if (see also §5), on the other hand, running IF
on subsets of $|\mathcal{D}|$ to improve runtime fast_if, can introduce
unwanted biases and misattribute prediction failures and would not be enough
for identifying mislabeled examples tracin or “hard” examples requiring
memorization feldman_practical. Nevertheless, these approaches remain
compatible with our method and may compound speed-ups.

We open-sourced our implementation of IFs with Arnoldi iteration at
http://anonymous.org.

##  2 Related work

Explaining DNN predictions falls under a broader interpretability umbrella,
where the lingering complexity of the data-explainability approach made
research historically focus on instance-based methods, that explain
predictions in terms of task-specific structural units of inputs, e.g. pixels
or tokens. Rich literature offers different variations of the idea: gradient-
based saliency maps simonyan2013deep; shrikumar2017learning;
sundararajan2017axiomatic, input perturbations LiMJ16a or LIME
ribeiro2016should, which fits a linear model in the inputs neighborhood.
However, being limited to specific inputs, their insights are rarely
actionable for system developers. And while it is possible to repurpose them
to data explainability, e.g. via clustering of saliency maps muller, this
solves a more difficult task than necessary, introduces new hyperparameters
(incl. the saliency method itself) and relies on human experts to make sense
of the clusters.

In contrast to instance-explanations in the form of token level heatmaps, the
IF provides a method for tracing model predictions back to training examples.
Existing approaches to reduce IF runtime mostly address salient problem
dimensions – dimensionality of active parameters, cardinality of data subset
or number of iterations – without addressing the procedure itself; or they
drop theoretical foundations to use simpler than IF heuristics tracin; yeh:
tracin reduce influence to tracking loss changes with the cumulative (over
training model checkpoints, i.e. model snapshots) dot products of gradients,
and in yeh authors leverage kernel functions evaluated at the training samples
for explaining inference decisions. These methods often lack the universality
that IFs offer. Yet another line of work focuses on leveraging Shapley values
as the metric to quantify the contribution of individual examples jia;
shapley; Ghorbani2019DataSE.

Mathematically, the closest to our work is spectrum_guys who use a
specialization of Arnoldi iteration to Hermitian matrices (Lanczos iteration)
to study the dynamics of spectra of entire Hessians at different snapshots
during training. Because of this different goal, they use full-batch Hessians
(i.e computed on the full datasets), while we “spread” the Hessian
approximation across smaller batches that do not cover the full dataset. In
result, we can work with larger models and datasets, e.g. ResNet50/ViT vs.
ResNet18, and at a larger speed (simultaneously bumping the number of
Lanczos/Arnoldi iterations from 90 to 200 to increase precision).

##  3 Influence and Influence Functions

The _true_ influence of $x$ on $z$, $\mathcal{I}_{\rm true}(x,z)$ is defined
as the change in the loss $L$ at $z$ between having learned the model
parameters $\Theta$ without and with $x$ in the training data cook80:

$\mathcal{I}_{\rm
true}(x,z)=L(z|\Theta:x\not\in\mathcal{D})-L(z|\Theta:x\in\mathcal{D}).$

Explicit calculation of $\mathcal{I}_{\rm true}(x,z)$, by removing every $x$
and retraining, is infeasible for large datasets and several approximation
techniques have been proposed. For example, feldman_theory; feldman_practical
propose to train multiple models on randomly selected data subsets while
tracking, for each $x$, to which subsets it belonged; this way, one can obtain
an unbiased estimator $\mathcal{I}_{\rm mem}(x,z)$ of $\mathcal{I}_{\rm
true}(x,z)$ which however requires a substantial amount of model re-trainings
(e.g. up to thousands to satisfy theoretical guarantees feldman_theory).

koh2017undestanding advocated the use of IFs in equation 1 that approximate
the loss change after an infinitesimal up-weighting of $x$ in $\mathcal{D}$.
For models used in practice, $H$ cannot be materialized in memory, let alone
be inverted by standard linear algebra. However, for a fixed vector $v$, the
Hessian-vector product (HVP), $Hv$, can be computed in $O(b\cdot p)$-time and
$O(p)$-memory pearlmutter, where $b$ is the number of training examples used
to approximate $H$. HVP is commonly implemented as the reverse-mode
differentiation Jacobian-vector product (JVP), followed by a forward-mode JVP
in modern autodiff toolkits griewank.

Repeated HVP calls are the workhorse of the iterative procedure LISSA
lissa_paper, used by koh2017undestanding, that estimate inverse HVP as:

$H^{-1}_{r}v=v+(I-H)H^{-1}_{r-1}v,$

where $H$ is estimated on some training samples and $v$ is some gradient
vector. Even for small $r$, the procedure is both time- and memory-expensive
as the $O(p)$-memory forces one to estimate $H$ on a _single sampled training
point per iteration_. Moreover, the total $O(r\cdot b\cdot p)$ time
complexity, where $r$ is the number of iterations, will be incurred at _every_
$x$ in whose influence on $z$ we are interested.

#### Evaluating influence methods

A practical problem with influence-based explainability is the absence of
ground-truth to verify that a method produces correct results. In this paper
we use two proxies, following the assumption that high self-influence,
$\mathcal{I}_{H}(x,x)$, correspond to data outliers koh2017undestanding;
tracin: we either introduce a known synthetic data corruption and check for
its correct retrieval by a method, or filter high-influence points out and
measure some downstream task metrics fast_if; kocijan20. Using
$\mathcal{I}(x,x)$ as a retrieval score for corrupted data, we measure the
retrieval quality using the area under the curve (AUC) on precision-recall
plots and the average precision (AP).

Following tracin, we will call, for a fixed $z$, those $x$ where
$\mathcal{I}(x,z)>0$ _proponents_ of $z$, as removing them from the training
data increases the loss at $z$; and those $x$ where $\mathcal{I}(x,z)<0$,
_opponents_ of $z$ as their removal decreases the loss at $z$. Given a point
$z$, we denote the set $\mathcal{I}_{k}(z)$ of the $k$-most influential points
for $z$ consists of those $x$ resulting in the $k$-largest values in
$\\{|\mathcal{I}(x,z)|\\}$.

##  4 Scaling Influence Functions

From the discussion above, the $O(p)$-memory complexity is the major
bottleneck for efficient implementation of IFs. We start with an overview of
existing techniques, showing there commonalities. They are compatible with the
approach we propose, for example, at query time one can use $k$-nearest
neighbor ($k$-NN) for retrieving most influential examples, or one can
restrict $\Theta$ to some layers and/or assume a Hessian of a known and fixed
form.

#### Caching.

fast_if introduce an procedure for finding $\mathcal{I}_{k}(z)$ by using a
$k$-NN search over $\\{\nabla_{\Theta}L(x)\\}$ using query
$H^{-1}\nabla_{\Theta}L(z)$. As $H$ is symmetric one might thus propose to do
a $k$-NN search over $\\{H^{-1}\nabla_{\Theta}L(x)\\}_{x}$ bringing down the
query complexity to $O(p)$ as one now is only required to compute
$\nabla_{\Theta}L(z)$. However this would only shift the burden to building
the search index for $H^{-1}\nabla_{\Theta}L(x)$. For explanation purposes one
might consider $x\in D^{\prime}$ for a sufficiently representative subset
$D^{\prime}\subset\mathcal{D}$; however as discussed above this would not be
enough for some data-selection applications that require computing
$\mathcal{I}_{H}(x,x)$ on _all_ the training data.

#### Restricting parameters.

Reducing required memory is possible by naively limiting the computation to a
smaller subset of parameters of cardinality $\tilde{p}$, e.g. selecting a one
or few layer(s). Usually, the last layer is selected koh2017undestanding;
tvetkov. This has two drawbacks: 1) the choice of layers becomes a
hyperparameter and 2) the viable values of $\tilde{p}$ will depend on the
model architecture. Moreover, the results of (feldman_practical, §3.6) suggest
that using just one layer can result in different influence estimates compared
to the full model.

#### Random Projections.

For simplification one might assume $H=I$ and reduce influence estimates to
the cosine measure of gradient similarity. To account for multiple layers at
once and to get a finer-step control of $\tilde{p}$, we consider a simple
baseline, RandSelect, which randomly selects $\tilde{p}$ parameters
$\tilde{\Theta}\subset\Theta$ and computes influence using the final
checkpoint and gradients with respect to $\tilde{\Theta}$ and can be combined
with layer selection. Note that the RandSelect estimator can be equivalently
expressed as

$\mathcal{I}_{G}(x,z)=\langle
G\nabla_{\Theta}L(x),G\nabla_{\Theta}L(z)\rangle,$ (2)

where $G\in\mathbb{R}^{\tilde{p}\times p}$ is a row selection matrix of the
gradient’s components corresponding to $\tilde{\Theta}$.

We use another sketching sketching baseline, RandProj, initially proposed by
wojnowicz for generalized linear models: for a random Gaussian projection
matrix $G$, $\mathbb{E}[G^{T}G]=I$ which leads to an unbiased estimate in
equation 2. Since normally $\tilde{p}\ll p$, it allows a memory-efficient
implementation in the forward mode; one just estimates $\tilde{p}$ JVPs with
the rows of $G$. As discussed in §5 for machine translation, that this has a
lower memory footprint than RandSelect, which still requires back-propagation
albeit to a smaller set of parameters.

#### Tracing updates.

An instantiation of the $H=I$ idea is proposed in tracin, where influence
approximation works for the case when one can trace changes to the loss $L$
across _all_ gradient steps. In order to make this feasible, they propose the
TracIn estimator, defined on a subset of gradient steps:

$\mathcal{I}_{\rm
TracIn}(x,z)=\frac{1}{C}\sum_{i=1}^{C}\langle\nabla_{\Theta_{i}}L(x),\nabla_{\Theta_{i}}L(z)\rangle,$

where the $\\{\Theta_{i}\\}$ is a set of $C$ checkpoints. Note that the
complexity of TracIn is $C$ times that of using exact gradient similarity; as
discussed in tracin care needs to be taken in selecting checkpoints. Another
practical obstacle to TracIn is that, when analysing publicly released models,
usually only the final model checkpoint is provided.

#### Compatible Projections.

RandProj assumes the full-dimension Hessian, $H=I$; if we drop this
requirement, we might consider $H$ restricted to the subspace $S_{G}$ which is
the image of $G$, and work with $G\cdot H\cdot G^{T}$ instead of the larger
$H$. However, $S_{G}$ is not in general $H$-invariant which can lead to
approximation errors as when $H$ is applied to a vector $v\in S_{G}$, the
result might have non-negligible components orthogonal to $S_{G}$. We will see
an example of this later in the experiments on eigenvalue retrieval for MNIST
(Figure 1) where RandProj requires a considerably larger $\tilde{p}$ than
Arnoldi to retrieve the top-$\tilde{p}$ eigenvalues of $H$.

We propose to use the standard technique of building an approximately
$H$-invariant subspace by selecting an arbitrary (e.g. random) vector
$v\in\mathbb{R}^{p}$ and constructing the $n$-th order Krylov subspace:

$K_{n}(H;v)={\rm Span}\\{v,Hv,H^{2}v,\dots,H^{n}v\\}.$

The Arnoldi iteration arnoldi additionally builds an orthonormal basis for
$K_{n}(H;v)$, and the diagonalization of the restriction $\tilde{H}$ of $H$ to
$K_{n}(H;v)$ yields an approximation of the largest (in absolute value)
eigenvalues of $H$ and of the corresponding eigenvectors (trefethen97, Ch.
33-34). Assuming $n$ is large enough to estimate the largest $\tilde{p}$
eigenvalues, in summary we obtain a projection matrix $G$ and work with
$\tilde{H}=G\cdot H\cdot G^{T}$, which is a smaller dimensional matrix. We
will call this algorithm Arnoldi, with the pseudocode in Algorithm 1.

The common feature of RandProj and Arnoldi is that, instead of working with
the full gradient $\nabla_{\Theta}L(x)$, one takes the JVPs $\langle
g_{i},\nabla_{\Theta}L(x)\rangle$ with respect to the rows $g_{i}$ of $G$. The
implementation then becomes considerably more efficient as it can be done in
the forward-mode differentiation and on larger batches. Moreover, in the case
of Arnoldi the matrix $H$ gets replaced with a diagonal one, simplifying the
matrix inversion appearing in the definition of $\mathcal{I}_{H}$, and
dispensing with the expensive LISSA procedure.

Another way of looking at this algorithm is as a simplification of the
quadratic form that is used in the standard derivation of equation 1 as we
detail in §A. Moreover, in the case of $H$ being ill-conditioned, this
approach might avoid the error estimates resulting from the small eigenvalues
of $H$, which we prove in §A.

Algorithm 1 Arnoldi

1:procedure Arnoldi($v$, $n$)

2:$\triangleright$ Build orthonomal basis for the Krylov subspaces $K_{n}$.

3: $w_{0}\leftarrow\frac{v}{\|v\|_{2}}$

4: $A_{l,m}\leftarrow 0$ for $0\leq l\leq n$ and $0\leq m<n$

5: for $i\leftarrow 1,n$ do

6: $w_{i}\leftarrow H\cdot w_{i-1}$ $\triangleright$ HVP in fwd-over-rev mode

7: Set $A_{i,j}=\langle w_{i},w_{j}\rangle$ for $j<i$

8: $w_{i}\leftarrow w_{i}-\sum_{j<i}A_{i,j}w_{j}$ $\triangleright$
Orthogonalize

9: $A_{i+1,i}\leftarrow\|w_{i}\|_{2}$,
$w_{i}\leftarrow\frac{w_{i}}{\|w_{i}\|_{2}}$

10: return: $A,\\{w_{i}\\}$

11:procedure Distill($A,\\{w_{i}\\},\tilde{p}$)

12:$\triangleright$ Distill $A,\\{w_{i}\\}$ to its top-$\tilde{p}$
eigenvalues.

13: Discard the last row of $A$ and the last $w_{n}$

14: Obtain $A$’s eigenvalues $\\{\lambda_{i}\\}$ and eigenvectors
$\\{e_{i}\\}$

15: Set $\\{\lambda^{\prime}_{i}\\}$ to the $\tilde{p}$-largest (in absolute
value) of $\\{\lambda_{i}\\}$

16: Set $\\{e^{\prime}_{i}\\}$ to the corresponding eigenvectors

17: Set $G$ to the projection matrix onto the spans of $\\{w_{i}\\}$ and
$\\{e^{\prime}_{i}\\}$

18: return: $\\{\lambda^{\prime}_{i}\\}$, $G$

19:procedure Influence($x,z,n,\tilde{p}$)

20:$\triangleright$ Influence of $x$ on $z$ with $n$ iters & top-$\tilde{p}$
eigenvalues.

21: $v\leftarrow\mathcal{N}(0,1)$

22: $A$, $\\{w_{i}\\}$ = Arnoldi($v,n$) $\left.\begin{array}[]{@{}c@{}}\\\
{}\hfil\\\ {}\hfil\end{array}\right\\}$$\triangleright$ Executed once and
cached

23: $\\{\lambda^{\prime}_{i}\\}$, $G$ = Distill($A$, $\\{w_{i}\\}$,
$\tilde{p}$)

24: $g_{x}\leftarrow G\cdot\nabla_{\Theta}L(x)$$\triangleright$ fwd JVP for
train point $x$

25: $g_{z}\leftarrow G\cdot\nabla_{\Theta}L(z)$$\triangleright$ fwd JVP for
test point $z$

26: $g_{x}\leftarrow g_{x}/\\{\lambda^{\prime}_{i}\\}$ $\triangleright$
Multiply with diagonalized $\tilde{H}^{-1}$

27: return: $\langle g_{x},g_{z}\rangle$

##  5 Experiments

###  5.1 Small Scale Data and Model: Digit Recognition

In this subsection, to be able to compare to all baselines we pick the small
MNIST dataset mnist (60k examples) and consider two CNNs of different sizes: a
small one that permits the exact Hessian calculation, and a larger one on
which we can gauge the scalability potential.

Because the influence calculation with LISSA and TracIn is slow, following
koh2017undestanding, we take two $10\%$ subsamples of the original data for
training and evaluation, and randomly relabel $20\%$ of training examples to
create a corrupted dataset to evaluate mislabeled example retrieval with
influence estimates. Unlike koh2017undestanding; tracin we introduce the noise
_before_ training the models; by design, a perfect model on correctly labeled
data would achieve only $80\%$ accuracy on our evaluation set.

#### Small network.

We re-implemented the small convolutional network with smooth non-linearities
from koh2017undestanding, and trained it following their recipe that is
designed to make the assumptions behind the influence function method cook88
satisfied: First, in order to ensure convergence, the network is trained for
more epochs than one would normally do, with a large batch size of 512 images.
Second, the $\ell_{2}$-regularization of $5\cdot 10^{-3}$ is introduced to
make $H$ positive definite. With only 3k parameters, is a useful benchmark
where it possible to compute $H$ explicitly. The accuracy of the trained
network on our corrupted evaluation set is 73.8% using the corrupted labels
and 92.3% using the true labels.

Figure 1: Estimation error (log-scale) on top-$\tilde{p}$ eigenvalues obtained
by the Distill procedure using optimal transport distance with the exact
values. Arnoldi was run for $n=200$ iterations. The horizontal line is the
standard deviation of the exact $H$’s eigenvalues.

In Figure 1 we compare the accuracy between the top-$\tilde{p}$ eigenvalues
estimations obtained by Arnoldi and RandProj. This illustrates the point made
above that if the image subspace $S_{G}$ associated with the projection $G$ is
not $H$-invariant, then eigenvalue estimates can be poor.

Figure 2: AUC and AP on retrieval of mislabeled examples as a function of
projections number $\tilde{p}$ on corrupted MNIST data.

In Figure 2 we plot the retrieval quality of mislabeled examples by Arnoldi
and RandProj as a function of the number of projections $\tilde{p}$. The
horizontal line is the performance achieved by using the exact Hessian. For
this network we see that Arnoldi outperforms RandProj and steadily improves
for further larger values, outperforming even the exact Hessian for a large
enough $\tilde{p}$ (which can be explained by presence of close-to-zero
eigenvalues in the exact $H$ which affects its inverse).

#### Larger network.

To consider a more realistic and larger network we use the CNN from the FLAX
library111https://github.com/google/flax/tree/master/examples/mnist with 800k
parameters, still small by industry standards, but for which we already cannot
compute the $H$ explicitly. We train it for 10 epochs on GPU V100 without
regularization and we achieve 75.4% on the corrupted test set and 94.8% on the
true labels test set. This network is more realistic in size and in training
procedure than the one in koh2017undestanding.

Table 1 reports results on retrieval of mislabeled examples with the total
scoring time $T$ as there is a trade-off between gains in AP or AUC vs. $T$.
As we computing exact $H$ was not possible, our baseline for self-influence
scoring is LISSA, which is about $10^{4}$ times slower than Arnoldi with
$\tilde{p}=10$, that we ran for $n=200$ iterations (took 353 seconds using a
batch size of $512$ to estimate HVPs).

We find that both Arnoldi and RandProj have a good trade-off between retrieval
accuracy and speed, while RandSelect, despite being the fastest, suffers in
retrieval quality. Note that here RandProj performs slightly better than
Arnoldi; we initially hypothesized that this might indicate an insufficient
accuracy of the $H$ estimation: To verify, we re-ran the Arnoldi with the HVPs
estimated on the _full_ dataset and obtained almost identical results,
indicating that, on the one hand, Arnoldi accurately estimates eigenvalues
with only 512 examples per HVP and, on the other hand, for this network and
task gradient similarity methods might be more appropriate (cf. LISSA for
$r=100$ does not move the needle either). Finally, TracIn on 10 checkpoints
had the best retrieval quality, however, while its runtime on this model and
dataset is acceptable, it becomes a problem for the larger models we consider
later.

Method | $\tilde{p}$ |  $T$, secs | AUC | AP
---|---|---|---|---
LISSA, $r=10$ | - | 4900 | 98.9 | 95.0
LISSA, $r=100$ (10% $\Theta$) | - | 3300 | 98.8 | 94.8
TracIn [1] | - | 5 | 98.7 | 94.0
TracIn [10] | - | 42 | 99.7 | 98.7
RandProj | 10 | 0.2 | 97.2 | 87.7
RandProj | 100 | 1.9 | 98.6 | 93.9
RandSelect | 10 | 0.1 | 54.9 | 31.2
RandSelect | 100 | 1.8 | 91.8 | 72.6
Arnoldi | 10 | 0.2 | 95.0 | 84.0
Arnoldi | 100 | 1.9 | 98.2 | 92.9
Table 1: Retrieval of mislabeled MNIST examples using self-influence. For
TracIn the number of checkpoints is in brackets. All methods use full models
(except the LISSA run on 10% of parameters $\Theta$). For RandProj std
deviation of estimates is $0.1\%$ on AUC and $0.7\%$ on AP over 20 runs.

###  5.2 Scaling with Data Size: Machine Translation

To test scalability over the data size dimension, we investigate the use of
IFs for machine translation focusing on data selection over millions of
examples. We verify the hypothesis that the “cleanest” data is the one with
the lowest self-influence koh2017undestanding; tracin. We evaluate retrieval
of mislabeled examples on the WMT17 dataset (6M examples) with artificially
introduced erroneous examples, and on the large task of cleaning noisy
Paracrawl (100M examples). We experimented on TPUv2 (4 cores). To improve TPU
utilization, and effectively increasing the number of tokens in each batch,
pack sentences shazeer2018mesh with a max sentence length of 256. Arnoldi used
batch size of 512 for HVPs; performing $n=200$ iterations took 139 minutes.

#### Retrieving mislabeled parallel data.

We experiment with the Transformer Base model vaswani2017all, implemented in
FLAX222https://github.com/google/flax/tree/main/examples/wmt, on the clean
WMT17 dataset for the German-English direction. We follow the original setup
from vaswani2017all and train it for 100k steps on TPUv2 (16 cores). As is
standard in machine translation, the model is neither over-trained to full
convergence nor we employ the $\ell_{2}$-regularization, so a priori is not
guaranteed if IFs that relies on Hessian approximations would fair better than
using the gradient heuristics, like RandProj or TracIn.

We used a vocabulary of 32k SentencePiece kudo tokens with src-tgt shared
embeddings, so that our model consists of approximately 60M parameters. On the
test set _newstest16_ we obtained BLEU 36.0 after 100k training steps.

For the synthetic noisy dataset, we uniformly sampled 4096 examples from the
training data and, for 256 examples of those, randomly shuffle the target
sides, and repeat the above procedure 5 times obtaining 5 data folds. We then
apply different methods to compute self-influence scores and evaluate the
quality of these scores with AUC and AP, averaging over the 5 data folds.

From Table 2 we first observe that RandSelect performs the worst in terms of
retrieval quality and the memory footprint of RandSelect scales poorly: while
we managed to run Arnoldi with the batch size of 512 to compute self-
influence, for RandSelect we had to reduce it to 64. In terms of retrieval
quality, Arnoldi also outperforms RandProj and we observe that here AP is a
more sensitive measure than AUC.

Finally, we consider the question of the quality of influence estimates
obtained for subsets of layers. For large models it is common to reduce $p$ by
looking at the last few layers tracin; fast_if; han-etal-2020-explaining.
However, feldman_practical observed for their estimator $\mathcal{I}_{\rm
mem}$ a degradation of the self-influence estimates computed using only the
last layer of ResNet50, conjecturing that memorization of difficult examples
has already happened by the time the computation reaches the last layer. We
corroborate their findings here for Transformers: applying RandProj and
Arnoldi on only the last three decoder layers, we observe a significant
degradation in the retrieval quality for all algorithms.

Layers | Method | $\tilde{p}$ | AUC | AP
---|---|---|---|---
all layers | RandSelect | 10 | 67.0 | 12.2
RandSelect | 100 | 79.3 | 19.7
RandProj | 10 | 85.6 | 31.3
RandProj | 20 | 85.2 | 28.0
Arnoldi | 10 | 92.0 | 47.8
Arnoldi | 20 | 93.8 | 54.4
last 3 decoder layers | RandSelect | 100 | 80.2 | 20.1
RandSelect | 1000 | 81.3 | 22.2
RandProj | 10 | 80.6 | 23.5
RandProj | 20 | 83.0 | 25.8
Arnoldi | 10 | 82.0 | 28.1
Arnoldi | 20 | 83.7 | 28.5
Table 2: Retrieving synthetic mislabeled examples on WMT17. The standard
deviation of AUC and AP estimates is resp. 0.9 and 1.0.

#### Filtering noisy training corpus.

To simulate a realistic data cleaning setup, we take the noisy Paracrawl
corpus from the WMT18 Parallel Corpus Filtering
Task333http://statmt.org/wmt18/parallel-corpus-filtering.html. This noisy
dataset consists of about 1B words and 100M German-English sentence pairs with
different kinds of noise that naturally occur in Web-crawled datasets:
sentences in languages others than English or German; pairs where both source
and target are in English or German; pairs where the target is either not a
translation of the source or only a partial translation; pairs where the
target is a copy (with possibly minor modifications) of the source; and non-
informative pairs, e.g. short sentences consisting of numbers.

We took a model trained on clean WMT17 data to bootstrap the self-influence
calculation and used _newstest2016_ for evaluation. The methods that scale to
this data size are Arnoldi, RandProj and RandSelect, but as the latter
underperformed on the retrieval of synthetically mislabeled data and has heavy
memory consumption, we focused on the former two. We chose $\tilde{p}=10$ as
it is faster than $\tilde{p}=20$, which did not substantially increase the
scores in Table 2.

As filtering baselines we consider training on the full uncleaned data and
some of the pre-filtering strategies from the AFRL, Alibaba and Microsoft
submissions to the shared task afrl_submission; alibaba_submission;
microsoft_submission. These include removing short parallel pairs or where the
target is a (near) copy of the source, and a language classifier to select
only true German-English pairs (details in §C.1). Note that we did not aim at
beating state-of-the-art cleaning pipelines, which usually employ a cascade of
filtering stages, but at investigating whether a simple application of IFs can
select better data to train on.

In Table 3 we report results after training on 10%, 5% and 1% of the data with
the lowest self-influence (i.e. the cleanest data by assumption). We followed
vaswani2017all and reported BLEU scores both at 10k steps and at the final
200k steps as the gap between data selection strategies might reduce over the
course of training, possibly as gradient updates from cleaner data might be
favored over time. Both Arnoldi and RandProj select cleaner data at the bottom
of the 5% and 10% self-influence scores. Also Arnoldi outperforms RandProj
gaining almost 4 BLEU points at 10k steps, and more than 8 points over the
pre-filtering baseline at 200k steps. At 1%, we see a degradation in the
performance at 200k steps and, inspecting the training loss, we found that it
decreased by more than 50% going from 5% to 1% data threshold. We conjecture
that the selected examples at this strict threshold are “too simplistic” to
provide useful translation patterns, in line with similar findings of
(feldman_practical, §3.3) on the marginal utility of data with low
memorization values on ImageNet.

Self-influence scoring speed was 2.2M examples per hour on a TPUv2 (16 cores)
using batch size 2048 and $\tilde{p}=10$.

Method | % selected | BLEU@10k | BLEU@200k
---|---|---|---
None | 100 | 9.9 | 17.8
Pre-cleaning | 14 | 11.7 | 22.6
RandProj | 1 | 7.7 | 8.7
Arnoldi | 1 | 17.8 | 19.6
RandProj | 5 | 18.7 | 27.9
Arnoldi | 5 | 24.0 | 30.3
RandProj | 10 | 21.3 | 28.6
Arnoldi | 10 | 25.0 | 30.8
Table 3: Data selection on the noisy Paracrawl corpus (100M parallel
sentences) with evaluation on _newstest16_.

###  5.3 Scaling with Model Size: Computer Vision

Here we empirically verify if Arnoldi scales well with the number of
parameters for five state-of-the-art computer vision models of increasing
sizes, and also run the mislabeled data retrieval experiment for the largest
Vision Transformer with self-influence scoring.

#### Time performance.

We considered ResNet50, Transformer Base and Vision Transformers (ViT): the
FLAX
implementation444https://github.com/google/flax/tree/main/examples/imagenet of
ResNet50 has about 25M parameters555Even though the model parameter count is
about 50M, half of the parameters are batch statistics, so we set $p$ to 25M.,
Transformer Base has 60M parameters, and for ViTs we used the JaX
implementation666https://github.com/google-research/vision_transformer and
took checkpoints trained on the mixture of ImageNet and ImageNet21k, that have
between 86M (B32) and 300M (L32) parameters. Additionally, to cover
intermediate sizes between the ViT B32 and L32 we took a subset of the layers,
starting from the top, to compute influence w.r.t. 50% of the parameters of
the ViT L32, amounting to 150M of weights. For all models we used one TPUv2
with 4 cores, $n=200$ and batch size 512.

Figure 3 plots the time taken by the self-influence calculation on the full
set of parameters. As expected, we observe a linear trend in terms of model
size, with the largest-size model (ViT L32) taking 15 hours to process the ??
dataset, which can be judged acceptable for this model- and data-scale.

Since memory consumption also scales linearly with $p$, to avoid exhausting
the TPU memory, we offloaded the results of each iteration to the host RAM. A
further optimization that we leave for future work is to improve the memory
footprint by exploring procedures using restarts, which consists in not
choosing the starting vector $v$ randomly or in caching intermediate
estimates. One approach might consist in doing $x$ iterations to estimate the
eigenvectors of the top $x$-eigenvalues, save them to disk and restart the
Arnoldi procedure using only the top eigenvector as $v$. Care must be taken to
ensure that the restarts preserve, at least approximately, the orthogonality
of the Arnoldi projectors, which might require some modifications to the
algorithm.

Figure 3: Time (min) for Arnoldi with 200 iterations on a full set of parameters. Layers | Method | $\tilde{p}$ | AUC | AP
---|---|---|---|---
top 10% | RandProj | 10 | 92.9 | 65.1
| Arnoldi | 10 | 92.6 | 62.9
| RandProj | 20 | 93.3 | 69.1
| Arnoldi | 20 | 92.9 | 64.3
| RandProj | 50 | 93.5 | 70.4
| Arnoldi | 50 | 93.3 | 65.8
top 20% | Arnoldi | 10 | 90.2 | 47.6
| RandProj | 10 | 91.6 | 60.3
| RandProj | 20 | 91.8 | 60.4
| Arnoldi | 20 | 91.2 | 53.9
| RandProj | 50 | 92.1 | 62.2
| Arnoldi | 50 | 91.3 | 54.9
bottom 10% | RandProj | 10 | 88.4 | 44.5
| Arnoldi | 10 | 88.4 | 43.1
| RandProj | 20 | 88.7 | 44.1
| Arnoldi | 20 | 88.4 | 43.1
| RandProj | 50 | 88.8 | 44.8
| Arnoldi | 50 | 88.4 | 43.1
bottom 20% |  |  |  |
Table 4: Retrieving synthetic mislabeled examples with ViT L32 on CIFAR10. For
RandProj the standard deviation of AUC is 0.1 and 0.5 of AP.

#### Retrieving mislabeled data.

Recently, the local loss landscapes of vanilla ViTs have been reported to be
extremely sharp vit_landscape. Hence, in order to better satisfy IF’s
assumptions, we took their ViT L32 checkpoint (300M parameters) that was
trained with the landscape-smoothing SAM loss sam. We further fine-tuned it
for 10k steps without regularization on clean CIFAR10 and obtained 98.6 test
accuracy. Despite SAM training, we found that the final parameter point is a
saddle point (talk about lambdas), so we restricted the Influence procedure
only to $\lambda_{i}>0$. To be able to cover more settings, here we ran
Arnoldi and RandProj on a subset of layers, accumulating them from either top
or bottom of the network until we have 10% and 20% of the total parameter
count. As in the previous experiments we used $n=200$ and 512 examples per
batch.

For the synthetic noisy dataset, we uniformly sampled 10% of CIFAR10 and
randomly flipped their labels. The retrieval results of mislabeled examples
with self-influence are in Table 7. Similarly to results on MNIST, the gap
between RandProj and Arnoldi is small and perhaps indicates that for the two
vision models accounting for local curvature is superfluous for this
particular self-influence benchmark. As demonstrated by koh2017undestanding,
this may not be the case in general, and for other IF-based applications our
contribution enables a verification of whether for a given task and model
requires Hessians.

For completeness, another potential reasons for the lack of difference between
RandProj and Arnoldi, could be the local non-convexity of the public ViT
models (we found that ..talk about distribution of $\lambda$) and/or the IF’s
increased fragility for large model sizes basu. The latter was recently called
out for a different task of natural language inference and the Transformer
RoBERTa model by kocijan20, who observed a performance decrease after
retraining on either high- or low-influence (w.r.t. to a validation set)
examples. We leave the question of whether model size alone or combined with
non-convexity explain the near matching performance of Arnoldi-based IFs and
RandProj for future work.

#### Memorization vs. Generalization Trade-Offs.

After having scored scored all ImageNet data for self-influence with Arnoldi
($\tilde{p}=10$) for the ResNet50 model, we found that high self-influence
examples appear (to a human) harder to discern or are possibly mislabeled (see
§D.3 for retrieved examples). This, however, is a qualitative evaluation, so
we further investigated the effect of removing data with low or high self-
influence.

feldman_practical considered the effect of removing examples with a high value
of $\mathcal{I}_{\rm mem}$ and found that this lowers test accuracy. With
ImageNet being rather clean, it is expected that removing data would have a
negative effect on accuracy too. However, while the examples with high
$\mathcal{I}_{H}(x,x)$ (or $\mathcal{I}_{\rm mem}$) may be require to be
“memorized”, the examples with low self-influence might help with
_generalization_ , i.e. give the model a solid classification basis for
typical images.

To test the trade-off between memorization and generalization we remove the
same percentage of data either starting from the examples with high or low
self-influence and retrain ResNet50. Results are reported in Figure 8, where
the horizontal line gives the accuracy on training on the full data. We find
that removing examples with low self-influence hurts performance more than
removing those with high self-influence suggesting that in this setting
_generalization_ has more incremental value over _memorization_.

As our estimator for self-influence is less expensive than $\mathcal{I}_{\rm
mem}$ we hope that this can spur further research 1) on investigating the
generalization-memorization trade-off in other applications, and 2) on
experimenting with training schedules to decide in which order to expose the
easier/harder data to the learning algorithm bengio.

Figure 4: Test accuracy of ResNet50 when progressively removing the most or
the least self-influential data.

##  6 Discussion

As we showed, depending on task’s nature, convergence status and local
convexity, IFs can be either superior or match the random projection approach,
when measured on the specific benchmark of retrieval of synthetically
mislabeled with self-influence scores. Whether this holds for other influence-
based tasks, like understanding learned patterns han-etal-2020-explaining,
debugging data biases brunet2019understanding, or estimating training data
quality wang2018data, requires further investigation. Importantly, we provided
an efficient tool to enable such analyses for industry-sized models and
datasets within acceptable timeframes on standard hardware.

  * •

we peoposed a speed up method for IFs

  * •

we demonstrated that simpler approach of RP, depending on the condiditons and
conveergence properties of the model can deliver comparable results for the
same compuyattional time.

  * •

the value of the method is that allows to compute IF with Hessians; so one can
test if the technique works well in a given setting and then scale it up (at
inference the method has same complexity as random projection; and people are
free to test which one works better)

  * •

in Koh&Linag they actually demonstrate this for MNIST, but it was the
consequence if these specific training setup that is tuned towards IFs
(convexification and smooth non-linearities, that are advantegouse compared to
ReLU basu)

  * •

BTW in the dilemma between IF or Gradients probably a role is played by the
NTK that governs the long term dynamics of the training (explained in the
paper of SAM for Vit); and if one applies Arnoldi to NTK one might look at the
eigenvalues and predict which method might work better + undrestand the
training dynamics… It seems NTK also governs the scaling law of models, like
how much perplexity goes down with model capacity in LM

Figure 5: General illustration of our approach.

##  Appendix A Approximation of Influence Functions

In this section we discuss the derivation of influence functions and the
effect of restricting the Hessian to the top-$\tilde{p}$ eigenvalues on the
estimates. We consider a point $x$ to be removed from the training data
$\mathcal{D}$ of cardinality $N$. We let $L(x|\Theta)$ denote the loss at $x$
under the parameters $\Theta$ and $L(\mathcal{D}|\Theta)$ the total loss:

$L(\mathcal{D}|\Theta)=\frac{1}{N}\sum_{x\in\mathcal{D}}L(x|\Theta).$

In this section we make the dependence of the Hessian $H$ on the learned
parameters $\Theta_{0}$ explicit by writing $H=H_{\Theta_{0}}$. Let
$\Theta_{0}$ be the parameters at convergence and assume that
$\nabla_{\Theta}L(\mathcal{D}|\Theta_{0})=0$. Then up to terms of order
$o(1/N^{2})$, the effect of retraining on $\mathcal{D}\setminus\\{x\\}$ is
approximated by shifting the parameters by $\theta_{*}$ which minimizes the
quadratic form

$Q(\theta)=\frac{1}{2}\langle\theta,H_{\Theta_{0}}\theta\rangle-\frac{1}{N}\langle\nabla_{\Theta}L(x|\Theta_{0}),\theta\rangle.$

In particular, up to a constant factor, the influence of $x$ on $z$ is
approximated by

$\mathcal{I}_{H}(x,z)=\langle\nabla_{\Theta_{0}}L(x),H_{\Theta_{0}}^{-1}\nabla_{\Theta_{0}}L(z)\rangle.$
(3)

We follow the argument in koh2017understanding and seek to model retraining as
minimization of:

$f(\theta)=L(\mathcal{D}|\Theta_{0}+\theta)-\frac{1}{N}L(x|\Theta_{0}+\theta);$

we then assume that $\|\theta\|_{2}$ is $O(1/N)$, do a Taylor expansion and
drop terms of order $O(1/N^{2})$ obtaining:

$\begin{split}f(\theta)&\approx
L(\mathcal{D}|\Theta_{0})-\frac{1}{N}L(x|\Theta_{0})-\frac{1}{N}\langle\nabla_{\Theta}L(x|\Theta_{0}),\theta\rangle\\\
&+\frac{1}{2}\langle\theta,H_{\Theta_{0}}\theta\rangle,\end{split}$

which is $Q(\theta)$ up to a constant. The minimizer of $Q$ is then

$\theta_{*}=\frac{1}{N}H_{\Theta_{0}}^{-1}\nabla_{\Theta}L(x|\Theta_{0}),$

and the first order Taylor expansion of
$L(z|\Theta_{0}+\theta)-L(z|\Theta_{0})$ yields equation 3 up to the
multiplicative factor $1/N$. Let us now order the eigenvalues of
$H_{\Theta_{0}}$ in non-decreasing absolute value:
$|\lambda_{1}|\geq|\lambda_{2}|\geq\cdots\geq|\lambda_{k}|\geq\cdots$ and
denote by $e_{1},e_{2},\cdots,e_{k},\cdots,$ the corresponding eigenvectors.
In (spectrum_guys, Sec. 4 and E) it is empirically observed (and proven in the
quadratic case) that during training dynamics the gradient updates will tend
to align with the subspace of $H_{\Theta_{0}}$ corresponding to the dominant
eigenvalues. Here we provide two different arguments in the same direction.
First, we upper bound the error of approximating $Q$ using such a subspace; we
then discuss the effect of noise depending on the size of the eigenvalues when
applying the inverse Hessian to a vector. Note that here we are under the
idealized conditions of the influence functions approximations
koh2017understanding where the loss is well-approximated by a quadratic form.

If we restrict $H_{\Theta_{0}}$ to the subspace spanned by the top-$k$
eigenvalues we then obtain a new quadratic form $Q_{k}$. Intuitively, as $k$
increases $Q_{k}$ better approximates $Q$; moreover, we expect that errors in
the estimation of $Q(\theta)$ in directions of the eigenvectors corresponding
to smaller eigenvalues should matter less. The form $Q_{k}$ approximates $Q$
by an error bounded by:

$0\leq
Q(\theta)-Q_{k}(\theta)\leq\frac{1}{2}|\lambda_{k+1}|\|\theta\|_{2}^{2}.$

If minimizing $Q$ introduces an error $\varepsilon$ in the direction of
$e_{k+1}$ obtaining an estimate $\theta^{\prime}$ for $\theta_{*}$, then

$Q(\theta^{\prime})-Q(\theta_{*})=\frac{\varepsilon^{2}}{2}\lambda_{k+1}.$

If we decompose $H_{\Theta_{0}}$ using the eigenvectors we get:

$\langle\theta,H_{\Theta_{0}}\theta\rangle=\sum_{j=1}^{d}\lambda_{j}^{2}(\langle\theta,e_{k}\rangle)^{2}.$

However, when we build $Q_{k}$ we only consider terms up to $j=k$ so

$Q(\theta)-Q_{k}(\theta)=\frac{1}{2}\sum_{j=k+1}^{d}\lambda_{j}^{2}(\langle\theta,e_{k}\rangle)^{2}\leq\frac{1}{2}|\lambda_{k+1}|\|\theta\|_{2}^{2}.$

For the second part we have $\theta^{\prime}=\theta_{*}+\varepsilon e_{k+1}$;
using the symmetry of $H_{\Theta_{0}}^{-1}$ we obtain the following expansion:

$\begin{split}Q(\theta_{*}+\varepsilon
e_{k+1})&=Q(\theta_{*})-\frac{1}{N}\langle\nabla_{\Theta}L(x|\Theta_{0}),\varepsilon
e_{k+1}\rangle\\\
&+\frac{1}{2N}\langle\nabla_{\Theta}L(x|\Theta_{0}),\varepsilon
e_{k+1}\rangle\\\ &+\frac{1}{2N}\langle
H_{\Theta_{0}}^{-1}\nabla_{\Theta}L(x|\Theta_{0}),\varepsilon
H_{\Theta_{0}}e_{k+1}\rangle\\\ &+\frac{1}{2}\langle\varepsilon
e_{k+1},\varepsilon
H_{\Theta_{0}}e_{k+1}\rangle=\frac{\varepsilon^{2}}{2}\lambda_{k+1}.\end{split}$

Below we look at the same phenomenon from a theoretical perspective by showing
that the variance of estimating influence increases if one looks at the small
eigenvalues of $H_{\Theta_{0}}$. To formalize, assume that we want to compute

$y=H_{\Theta_{0}}^{-1}u$

and that $u$ can be estimated exactly. We also assume that $H_{\Theta_{0}}$’s
estimation is noisy resulting in $H_{\Theta_{0}}+\delta H$; and that the
expected value of $\delta H$ is $0$ and that the $\delta H$ is isotropic (e.g.
it does not preferentially align with some $e_{k}$ or co-vary with
$\lambda_{k}$). We then show that for the estimator

$\hat{y}=(H_{\Theta_{0}}+\delta H)^{-1}u$

the variance in the direction of $e_{k}$ is proportional to
$|\lambda_{k}|^{-2}$; this formalizes the intuition that the small eigenvalues
increase the noise in the estimates. The variance of $\hat{y}$ in the
direction of $e_{k}$ is:

${\rm Var}(\langle\hat{y},e_{k}\rangle)\approx\frac{1}{|\lambda_{k}|^{2}}{\rm
Var}(\langle\delta He_{k},y\rangle).$

The estimator $\hat{y}$ solves another problem than $y$:

$(H_{\Theta_{0}}+\delta H)\hat{y}=u=H_{\Theta_{0}}y;$

if we write $\hat{y}=y+\delta y$ and ignore the term $\delta H\cdot\delta y$
we obtain:

$\delta y=-H_{\Theta_{0}}^{-1}\delta H\cdot y,$

from which

$\langle\delta y,e_{k}\rangle=-\frac{1}{\lambda_{k}}\langle e_{k},\delta
H\cdot y\rangle,$

from which the result follows using that $\delta H$ is symmetric. Note that
from the above equation we can also deduce, having ignored the term $\delta
H\cdot\delta y$, that $\mathbb{E}[\delta y]\approx 0$, so that $\hat{y}$ is
approximately an unbiased estimator of $y$ too.

###  A.1 Arnoldi iteration for inverse Hessian

Note that in the ideal situation, in which Arnoldi correctly locates the
top-$k$ eigenvalues and eigenvectors, one is minimizing $Q_{k}$ instead of
$Q$. On the other hand, one might try to apply Arnoldi directly to
$H_{\Theta_{0}}^{-1}$ obtaining an approximation in operator norm using the
subspace corresponding to the top-$k$ eigenvalues of $H_{\Theta_{0}}^{-1}$,
which correspond to the $k$ eigenvalues of $H_{\Theta_{0}}$ with smallest
absolute value. However, this approach also requires estimating inverse HVPs
iteratively, e.g. using LISSA. For example, if LISSA is employed with $r$
iterations for each iteration of Arnoldi, this approach is $r$ times slower.
We also did not find this approach competitive: for the larger CNN network
considered in §LABEL:sec:mnist we tested it using $r=50$ and, while for
$\tilde{p}=10$ we got a slightly better retrieval quality of 97.9/91.9
(AUC/AP), with $\tilde{p}=100$ the retrieval quality was not better than
Arnoldi’s 97.9/92.8.

##  Appendix B Corrupted MNIST

###  B.1 Opponents and Proponents

Following tracin, we will call, for a fixed $z$, those $x$ where
$\mathcal{I}_{H}(x,z)>0$ _proponents_ of $z$, as removing them from the
training data increases the loss at $z$; and those $x$ where
$\mathcal{I}_{H}(x,z)<0$, _opponents_ of $z$ as their removal decreases the
loss at $z$.

We use the CNN network with 800k parameters from §LABEL:sec:mnist and
$\tilde{p}=10$ Arnoldi projectors to find top opponents and proponents of test
images. Note that, to highlight the fact that IFs without normalization tend
to retrieve examples with bigger gradients, we compute proponents and
opponents both with and without normalizing all gradients to a unit norm.
Scaling influence scores by (transformed) gradient norm has already been used
to compensate for IF’s propensity to prefer high-loss examples relatif, while
not using normalization may have lead to negative conclusions about IF
usefulness kocijan20.

Overall, we find that results are easily interpretable by a human. Let us
first consider the example in Figure 6 for a correctly labeled digit 5. Except
for one case, proponents are correctly labeled 5s and using gradient
normalization retrieves at the top 3, examples of 5s which are stylistically
similar to the original image. On the other hand, without gradient
normalization, a strong proponent can also be a fake 5, because the gradients
can be big. In this case we have a 3 labeled as 5 as the 5th proponent.
Opponents are all instances of 5s that were incorrectly labeled.

Now consider digit 4 mislabeled as 9 in Figure 7. All the proponents are 4s
incorrectly labeled as 9. Only without gradient normalization the top-5th
proponent is a 4 labeled as an 8, but one might also argue that it looks close
by a 9 (if one would add a small closing stroke at the top). Opponents without
normalization are instances of 4s correctly labeled as 4; while opponents
without normalization are 9s labeled as 4; this is expected as without
normalization instances with bigger gradients will be preferred.

Method | $\tilde{p}$ | AUC | AP | AUC | AP
---|---|---|---|---|---
|  | w/o $||\Theta||_{2}^{2}$ | with $||\Theta||_{2}^{2}$
LISSA, $r=10$ | - | 76.6 | 43.6 | 96.6 | 87.3
TracIn [1] | - | 63.1 | 39.9 | 99.3 | 97.9
TracIn [10] | - | 92.3 | 72.1 | 99.7 | 99.0
RandProj | 10 | 76.4 | 43.5 | 91.5 | 72.8
RandProj | 100 | 76.6 | 43.6 | 95.1 | 83.4
RandSelect | 10 | 56.4 | 28.9 | 73.3 | 50.8
RandSelect | 100 | 63.0 | 36.2 | 97.1 | 81.5
Arnoldi | 10 | 74.7 | 39.5 | 86.7 | 71.3
Arnoldi | 100 | 75.5 | 42.3 | 92.3 | 80.2

Table 5: Retrieval of mislabeled MNIST examples using self-influence for the
longer trained large CNN model, with and without $\ell_{2}$-regularization.
For TracIn, the number of checkpoints is in brackets (one last or all). All
methods use full models. Scoring time $T$ is omitted since it exactly matches
the numbers in Table 1.

###  B.2 Longer trained larger network

To investigate how longer training effects the methods’ performance on the CNN
network with 800k parameters from §LABEL:sec:mnist, we trained it for 100
epochs instead of 10, both with and without $\ell_{2}$-regularization (denoted
as $||\Theta||_{2}^{2}$ in Table 5). Without regularization, CNN accuracy on
the test set is 69.47% which points to the model over-fitting and leads to
much lower AUC/AP for all the methods; regularization prevents over-fitting
and lifts the accuracy to 74.3%. Despite different training protocols, we
observe the same ranking of methods as in Table 1 in §LABEL:sec:mnist. As
before, TracIn on 10 checkpoints has the best retrieval accuracy for this CNN,
but it is much slower than other methods except for LISSA, and does not scale
to even larger models and datasets. The poor performance of TracIn on the last
checkpoint without regularization, highlights the danger of replacing
influence with gradient similarity for models at risk of over-fitting. The
projection-based Arnoldi and RandProj however, given enough projectors, fair
better in this setup.

Figure 6: Proponents and opponents of correctly labeled test point. Proponents
are colored in blue and opponents in red while the test point is in gray at
the center. For each point we report the label in the corrupted MNIST / the
label in the original MNIST. Figure 7: Proponents and opponents of an
incorrectly labeled test point. Proponents are colored in blue and opponents
in red while the test point is in gray at the center. For each point we report
the label in the corrupted MNIST / the label in the original MNIST.

##  Appendix C Machine Translation

###  C.1 Prefiltering Baseline

For machine translation we implemented a prefiltering baseline inspired by the
AFRL, Alibaba and Microsoft submissions afrl_submission; alibaba_submission;
microsoft_submission to the WMT18 corpus filtering task:

  * •

AFRL: remove pairs where the ratio of the number of English to German words is
above 3 or below 1/3. This is likely to eliminate misaligned pairs. We also
filtered out pairs where at least one side contains a word consisting of more
than 30 tokens as a heuristic to remove long URLs.

  * •

Alibaba: remove pairs where the edit distance between the two segments is less
than 2 or the relative edit distance (i.e. normalized by the average of the
segments’ lengths) is less than 0.1. This removes segments where the target is
a minor modification of the source.

  * •

Microsoft: use a language classifier to remove segments where either the
target is not English or the source is not German. As the Microsoft submission
did not release their classifier, we used the one from zhang-etal-2018-fast.

###  C.2 Experimental Details

We used the Flax
library777https://github.com/google/flax/tree/main/examples/wmt and the
configuration for Transformer Base. Specifically, we used a shared
SentencePiece kudo2018sentencepiece vocabulary of 32k tokens, hidden dimension
of 512, MLP dimension 2048, 8 attention heads and 6 layers in the encoder and
the decoder. Note that we share weights between the last layer and the
embeddings, and use bfloat16 precision. The dropout rate was 0.1 both for
attention and MLPs.

To improve TPU utilization, and effectively increasing the number of tokens in
each batch, we packed sentences shazeer2018mesh with a max sentence length
256; this results in about 56k non-padding tokens in each batch. We used Adam
with the defaults of the Flax library. For the learning schedule we increase
linearly the learning rate to 0.002 in the first 1k steps and then use square-
root decay. For BLEU evaluation we used
SacreBLEU888https://github.com/mjpost/sacrebleu; configuration:
case:mixed+eff:no+tok:13a+smooth:exp+version:2.0.0.

###  C.3 Exemplars

In Table 6 we report some exemplars of data classified as having lower or
higher self-influence by Arnoldi on the noisy Paracrawl. In general, up to the
1% quantile the data consists of clean but very short segments; between 1% and
10% the data becomes more interesting with longer translated segments, that
may not always be exact translations though. The exemplar in the 90%-100%
shows an incorrect pair of two English sentences which, being highly-self
influential, requires memorization from the model.

To better understand the cleaner portion of the data we looked at the Spearman
correlation between length of the longest sentence (German or English) and the
quantile rank. For the data in the 0-10% quantile we observe a highly
significant correlation of about 0.5 with a $pval<10^{-6}$, justifying popular
short-segment removing heuristics. On the other hand, this correlation
disappears as the data gets less clean; for example, in the range 70%-100% the
Spearman correlation is negative and of just -0.19.

Quantiles | Parallel Exemplar
---|---
[0%, 1%] |  DE: Statistik Schweiz EN: Statistics Switzerland
[1%, 5%] |  DE: 1. Darf ich dieses Buch kaufen? EN: 1. May I buy this book ?
[5%, 10%] |  DE: Die bis zu 15.000 Bogen/h schnelle, gegenüber vielen anderen Modellen in dieser Formatklasse besonders platz- und energiesparende Maschine wird mehrmals täglich bei dem Druck und Inline-Veredelung von hochwertigen Postern live präsentiert EN: The press is engineered for production speeds up to 15,000 sheets per hour and boasts not only a significantly smaller footprint, but also greatly reduced energy consumption compared to many other presses in this format class.
[90%, 100%] |  DE: View Public Profile EN: The time now is 01:18 pm .

Table 6: Exemplars of Paracrawl data from low to high self-influence as found
by Arnoldi. Cleaner, low influence, data is not always useful, as it can
consist, e.g., of very short segments. Mislabeled data has higher high self-
influencebecause such needs to be memorized verbatim, as the model cannot
“interpolate” the label from similar examples.

##  Appendix D Computer Vision

###  D.1 Experimental Details for ViT

Since memory consumption also scales linearly with $p$, to avoid exhausting
the TPU memory, we offloaded the results of each iteration to the host RAM. A
further optimization that we leave for future work is to improve the memory
footprint by exploring procedures using restarts, which consists in not
choosing the starting vector $v$ randomly or in caching intermediate
estimates. One approach might consist in doing $x$ iterations to estimate the
eigenvectors of the top $x$-eigenvalues, save them to disk and restart the
Arnoldi procedure using only the top eigenvector as $v$. Care must be taken to
ensure that the restarts preserve, at least approximately, the orthogonality
of the Arnoldi projectors, which might require modifications to Algorithm 1.

###  D.2 Mislabeled Examples Retrieval for ViT

For the synthetic noisy dataset, we uniformly sampled 10% of CIFAR10 and
randomly flipped their labels. The results of retrieval with ViT on CIFAR10
are in Table 7. We ran Arnoldi with effective batch size of 8192 on a TPUv2
with $c=4$ cores using a $\frac{256}{c}$-step gradient accumulation.

Parameters | Method | $\tilde{p}$ | AUC | AP
---|---|---|---|---
top 10% | Arnoldi | 10 | 94.2 | 64.4
RandProj | 10 | 93.9 | 62.3
Arnoldi | 20 | 93.9 | 61.3
RandProj | 20 | 94.0 | 62.4
top 20% | Arnoldi | 10 | 94.0 | 62.5
RandProj | 10 | 93.8 | 61.7
Arnoldi | 20 | 93.6 | 59.4
RandProj | 20 | 93.9 | 61.9
100% | Arnoldi | 10 | 93.1 | 57.0
RandProj | 10 | 93.2 | 59.0
Arnoldi | 20 | 93.3 | 57.4
RandProj | 20 | 93.7 | 59.2

Table 7: Retrieving synthetic mislabeled examples on CIFAR-10. The standard
deviation of AUC and AP estimates is resp. 0.1 and 0.7 over 5 runs.

###  D.3 Mislabeled Examples Retrieval and Exemplars for ResNet50

In Figure 9 we provide exemplars from ImageNet scored by self-influence using
RestNet50. We used the top-10 projectors extracted by Arnoldi. The top row
shows random samples from the top 90%-100% quantiles of self-influence scores,
the two middle rows are from the 40%-60% quantile, and the bottom one
represent the lower 0%-10% range. As can be seen, the top row contains either
mislabeled images or ambiguous images with cluttered backgrounds containing
more things than just the labeled object; in the mid-row some of the objects
are in multiple counts and/or still have a rich background; in the last row,
as a rule, the labeled object is prominently featured, occupying most of the
image.

In Figures 10 and 11 we demonstrate the top-5 proponents and opponents of
randomly selected images from the ImageNet train set. For a similar
experiment, the protocol in tracin did not use the gradients with respect to
the parameters (even when considering the last layer only), but to the logits.
This results in the gradients being simplified to one hot vector predictions
minus probabilities in place of gradients, effectively resulting in a pre-
filtering looking for proponents in the same class and opponents in the rest
of the top predicted labels. We also used such a pre-filtering, but used the
actual projectors with respect to the model parameters, which makes our
experiment more challenging. Additionally, we show retrieved images with
normalized gradients used in the definition of influence to illustrate IF’s
sensitivity to the norm of the gradient (e.g. on high loss images) and that
normalization mitigates this.

###  D.4 Memorization vs. Generalization Trade-Offs

In §D.3 we found that high self-influence examples appear (to a human) harder
to discern or are possibly mislabeled. This, however, was a qualitative
evaluation, so we further investigated the effect of removing data with
low/high self-influence. feldman_practical considered the effect of removing
examples with a high value of $\mathcal{I}_{\rm mem}$ and found that this
lowers test accuracy. With ImageNet being rather clean, it is expected that
removing data would have a negative effect on accuracy too. However, while the
examples with high $\mathcal{I}_{H}(x,x)$ (or $\mathcal{I}_{\rm mem}$) may
require to be “memorized”, the examples with low self-influence might help
with _generalization_ , i.e. give the model a solid classification basis for
typical images.

To test the trade-off between memorization and generalization we remove the
same percentage of data either starting from the examples with high or low
self-influence and retrain ResNet50. Results are reported in Figure 8, where
the horizontal line gives the accuracy on training on the full data. We find
that removing examples with low self-influence hurts performance more than
removing those with high self-influence suggesting that in this setting
_generalization_ has more incremental value over _memorization_.

Figure 8: Test accuracy of ResNet50 when progressively removing the most or
the least self-influential data.

As our estimator for self-influence is less expensive than $\mathcal{I}_{\rm
mem}$ we hope that this can spur further research 1) on investigating the
generalization-memorization trade-off in other applications, and 2) on
experimenting with training schedules to decide in which order to expose
easier or harder data to a learning algorithm kreutzer21bandits.

Figure 9: Exemplars of ImageNet pictures scored by self-influence using
ResNet50, with the corresponding quantile in brackets. Figure 10: Exemplar of
ImageNet picture accompanied by its top 5 proponents and opponents with and
without normalisation. We have pre-filtered projection based on the top 10
labels predicted by the model. Normalization of the gradients filters out the
most ”different” examples, for example, the top left image with children which
had a large norm, was removed from the proponents after the normalization.
Figure 11: Another exemplar of ImageNet picture accompanied by it top 5
proponents and opponents with and without normalisation. The figure
demonstrates the effect of normalization on the influence scores. In the first
column we can see a lot of complicated images, even though they all contain
strawberies, these examples are outliers since they have external objects
present or the strawberries are of unusual shape. These examples are useful
for model learning, therefore the gradients is high, after normalization,
however, the proponent images are less ”unusual”. We can also see in the
second column that the image we are explaining is the highest proponent of
itself, which meets our expectations.