The Memory-Perturbation Equation: Understanding Model's Sensitivity to Data
Authors: Peter Nickl
Lu Xu
Dharmesh Tailor
Thomas Möllenhoff
Mohammad Emtiyaz Khan
Venue: NeurIPS 2023 poster (2023)
Keywords: model interpretability
model understanding
bayesian learning
robustness
adaptive learning

Abstract: Understanding model’s sensitivity to its training data is crucial but can also be challenging and costly, especially during training. To simplify such issues, we present the Memory-Perturbation Equation (MPE) which relates model's sensitivity to perturbation in its training data. Derived using Bayesian principles, the MPE unifies existing sensitivity measures, generalizes them to a wide-variety of models and algorithms, and unravels useful properties regarding sensitivities. Our empirical results show that sensitivity estimates obtained during training can be used to faithfully predict generalization on unseen test data. The proposed equation is expected to be useful for future research on robust and adaptive learning.

The Memory Perturbation Equation: Understanding Model's Sensitivity to Data
Peter NickI peter wwinniiiiiiiiioo jp
Lu Xu* lu. xu.xu..e su..swriken... jp
Dharmesh Tailor* d.v. v. tailorQuva. nl
Thomas Möllenhoff thomas horemma..ollllmofffekkkee...
Mohammad Emtiyaz Khan emtiyaz. khan@riken, jp
Abstract
Understanding model's sensitivity to its training data is crucial but can also be challenging and costly, especially during training. To simplify such issues, we present the Memory-Perturbation Equation (MPE) which relates model's sensitiv- ity perturbation in its training data. Derived using Bayesian principles, the MPE unifies existing sensitivity measures, generalizes them to a wide-variety of models and algorithms, and unravels useful properties regarding sensitivities. Our empir- ical results show that sensitivity estimates obtained during training can be used faithfully predict generalization on unseen test data. The proposed equation is expected to be useful for future research on robust and adaptive learning.
Introduction
Understanding model's sensitivity to training data is important to handle issues related to quality, pri- vacy, and security. For example, we can use understand (i) the effect of errors and biases the data; (ii) model's dependence private information to avoid data leakage; (iii) model's weakness to malicious manipulations. Despite their importance, sensitivity properties of machine learning (ML) models are not well understood in general. Sensitivity is often studied through empirical investiga- tions, conclusions drawn this way do not always generalize across models or algorithms. Such studies are also costly, sometimes requiring thousands of GPUs [38] which can quickly become infeasible if we need to repeat them every time model is updated.
A cheaper solution is to use local perturbation methods 21 for instance, influence measures that
study sensitivity of trained model to data removal Fig. I(a) g 77. Such methods too fall short of providing clear understanding of sensitivity properties for generic cases. For instance, influence measures are useful study trained models but are not suited to analyze training trajectories [14 54). Another challenge is in handling non non-differentiable loss functions or discrete parameter spaces where natural choice of perturbation mechanisms may not always be clear [32]. The measures also do not directly reveal the causes of sensitivities for generic ML models and algorithms.
In this paper, we simplify these issues by proposing new method to unify, generalize, and under- stand perturbation methods for sensitivity analysis. We present the Memory-Perturbon (MPE) unifying equation understand sensitivity properties generic ML algorithms. The equation builds upon the Bayesian learning rule (BLR) (28) which unifies many popular algorithms
Equation
* 'Equal contribution. Part of this work carried out when Dharmesh Tailor RIKEN AIP.
1 'RIKEN Center for AI Project, Tokyo, Japan. I University of Amsterdam, Amsterdam, Netherlands.
8 Cooresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Training without the I'th example
Truth
1.8
Estimate
1.2
LOO-CV
Test NLL
Training on full dataset
0.6
Iterations
100
200
Current
Epochs
(a) Estimating the effect of an example removal
Predicting test NLLL during training, CIFARIO
Our main goal is estimate the sensitivity of the training trajectory when examples perturbed or simply removed; see Panel (a). We present the MPE to estimate the sensitivity without any retraining and use them to faithfully predict the test performance from training data alone; see Panel (b). The test negative log-likelihood (gray line) for ResNet-20 on CIFARIO shows similar trends the leave-one-out (LOO) score computed on the training data (black line).
Figure 1:
from various fields as specific instances of natural-grudient descent to solve Bayesian learning problem. The MPE uses natural-gradients to understand sensitivity of all such algorithms. We use the MPE to show several new results regarding sensitivity of generic MI. algorithms:
1.
We show that sensitivity to a group of examples can be estimated by simply adding their natural-gradients; see [Eq Larger natural-gradients imply higher sensitivity and just few such examples can often account for most of the sensitivity. Such examples can be used to characterize the model's memory and memory-perturbaaiin refers the fact that the model can forget its essential knowledge when those examples are perturbed heavily.
2. We derive Influence Function 8 31 as a special case of the MPE when natural-gradien with respect to Gaussian posterior are used. More importantly, we derive new measures that, unlike influence functions, can be applied during training for all algorithms covered under the BLR (such as those used in deep learning and optimization). See (Table 1.
3. Measures derived using Gaussian posteriors share a common property: sensitivity to an example depends the product of its prediction error and variance (Eq. 12p. That is, most sensitive data lies where the model makes the most mistakes and is also least confident. In many cases, such estimates are extremely cheap to compute.
4. We show that sensitivity of the training data can be used accurately predict model gen- eralization, even during training (Fig. 1(b)). This agrees with similar studies which also show effectiveness of sensitivity in predicting generalization (22 12
2 Understanding a Model's Sensitivity to Its Training Data
Understanding a model's sensitivity to its training data is important but is often done by a costly process of retraining the model multiple times. For example, consider model with a parameter vector 0 E R. trained on data D = {D,, D2.... Dx by using an algorithm A, that generates a sequence (0.) for iteration that converges minimizer 0,. Formally, we write
0, + A. (0.1,,,, where L())
+()))
and we use the loss (0)) for D; and regularizer R(0). Because 0, are all functions of D or its subsets, we can analyze their sensitivity by simply 'perturbing" the data. For example, we can remove subset M D to get a perturbed dataset, denoted by D.M and retrain the model to get new iterates 0. converging to minimizer M.. If the deviation 0)
0, is large for most I, we may deem the model to be highly sensitive to the examples M. This simple method for sensitive analysis but requires a costly brute-force retraining (38 which is often infeasible for long training trajectories, big models, and large datasets. More importantly, conclusions drawn from retraining are often empirical and may not hold across models algorithms.

---

A cheaper alternative is to use local perturbation methods [21], for instance, influence measures that estimate the sensitivity without retraining (illustrated Fig. (a) by the dashed red arrow). The simplest result of this kind is for linear regression which dates back to the 70s 77 The method makes use of the stationarity condition to derive deviations in 0. due to small perturbations to data. For linear regression, the deviations can be obtained in closed-form. Consider input-output pairs (x,; 31) and the loss (0) = 1 fi()))² for f())) = x; and regularizer R(0) = ò 0|00| 12/2 We can obtain closed- form expressions of the deviation due to the removal of the i' 4'th example as shown below (a proof is included in App. A).
0 - 0. = (H x;e;,
f((0.)) - -((0))-f((0.)) = =u
(2)
where we denote H = H. x defined using the Hessian H. = V2 We also denote the prediction error of 0. by e; = x, 0. yi. and prediction variance of 0: by v. - x (H-))-
The expression shows that the influence is bi- bi-linearly related to both prediction error and variance, that is, when examples with high error and variance are removed, the model is expected to change a lot. These ideas are generalized using infinitesimal perturbation (2T] For example, influence func- tions [8] 32 31 use a perturbation model 0 arg ming (()) - (0), with a scalar perturbation 6 E RR. By using a quadratic approximation, get the following influence function,
00
= (O.))
(3)
dc, c==0
This works for a generic differentiable loss function and is closely related to Eq. 2] We can choose other perturbation models, but they often exhibit bi-linear relationships; see App. A for details. Despite their generality, there remain many open challenges with the local perturbation methods:
1. Influence functions are valid only at a stationary point O- where the gradient is assumed to be O, and extending them to iterates O, generated by generic algorithmic-steps Ae is non- trivial 14] This is even more important for deep learning where we may never reach such a stationary point, for example, due to stochastic training or early stopping [33 53
2. Applying influence functions
non-differentiable loss or discrete parameter spaces is difficult. This is because the choice of perturbation model is not always obvious (32).
3. Finally, despite their generality, these measures do not directly reveal the causes of high influence. Does the bi-linear relationship in Eq. hhold more generally? If yes, under what conditions? Answers to such questions are currently unknown.
Studies to fix these issues are rare in ML, rather it is more common simply use heuristics measures. Many such measures have been proposed in the recent years, for example, those using derivatives with respect to inputs (23 2 variations of Cook's 's distance (17]. prediction error and/or gradients 3
[13]. These works, although useful, do not directly address the issues. Many of these measures are derived without any
42 40
backtracking training trajectories [16]. or simply by retraining
direct connections to perturbation methods. They also appear to be unaware of bi-linear relation- ships such as those in Eq. 2] Our goal here is to address the issues by unifying and generalizing perturbation methods of sensitivity analysis.
3 The Pertry-Porttubattin Equation (MPE)
We propose the memory-perturbation equation (MPE) to unify, generalize, and understand sensitiv- ity methods in machine learning. We derive the equation by using property of conjugate Bayesian models which enables us to derive a closed-form expression for the sensitivity. In a Bayesian set- ting. data examples can be removed by simply dividing their likelihoods from the posterior [52]. For example, consider a model with prior pu p(0) and likelihood OU = pDD,()) giving rise to a posterior q. = p(0 D) x Poβ1Ω2 ... .NN. To remove Pj. say for all M C D. we simply divide q. by those Pj. This is further simplified if we assume conjugate exponential-famin Pz. Then, the division between two distributions equivalent to subtraction between their natural parameters. This property yields a closed-form expression for the exact deviation, as stated below.
form for Po and
3

---

Theorem Assuming conjugate exponentiat-family model, the posterior qet (with natural pa- can be written in terms of q. (with natural parameter )a). as shown below:
rameter A_ M)
e(A,,T(O))
g.
qu
elA.M T(O)
AM=
Σ
}j. (4)
II
e T(O))
JEM
where all exponential families defined by using inner-prodie (x, T())) with natural parameters À and sufficient statistics T(0). The natural parameter of p3 is denoted by Xz-
The deviation A.M X, is obtained by simply adding X, for all j E M. Further explanations and examples are given in App. B] along with some elementary facts about exponential families. We use this result to derive an equation that enables us to estimate the sensitivity of generic algorithms.
Our derivation builds on the Bayesian learning rule (BLR) (28) which unifies many algorithms by ex- pressing their iterations inference conjugate Bayesian models [26). This is done by reformulat- ing Eq. Tin a Bayesian setting to find an exponential-famin approximation q- R p(0 x e (()), At every iteration the BLR updates the natural parameter X of an exponential-fant famill q. which can equivalently be expressed as the posterior of a conjugate model (shown on the right),
N 11-
A f (1-p)> P
Σ
qt x (q-11) 1 (po) II
( (A- 1). T())
(5)
1=0
Prior
Likelibood
the natural gradient with respect to defined using the Fisher Information Matrix F(A:) of qt. and > 0 is the learning rate. For simplicity, we denote (0) = R(0) = Pog Po. and assume po to be conjugate. The conjugate model on the right uses a prior and likelihood both of which, by construction, belong to the same exponential-famin as q-- By choosing an appropriate form for q: and making necessary approximations to gj, the BLR can recover many popular algorithms as special cases. For instance, using a Gaussian q,, we can recover stochastic gradient descent (SGD), Newton's method, RMSprop. Adam, etc. For such cases, the conjugate model at the right is often a linear model (25). These details, along with a summary of the BLR, are included in App. C Our main idea to study the sensitivity of all the algorithms covered under the BLR by using the conjugate model in Eq. 5
where g (A) F(A) (AE
Let q:' M be the posterior obtained with the BLR but without the data in M. We can estimate its natural parameter A. in a similar fashion as [Eq. 4, that is, by dividing by the likelihood approximation the current Ac. This gives the following estimate of the deviation obtained by simply adding the natural-gradients for all examples in M.
JM A P Σ (A,)
JEM
where X is estimate of the true X X.M We call this the memory-perturbatee equation (MPH) due to a unique property of the equation: the deviation is estimated by simple addition and charac- terized solely by the examples in M. Due the additive nature of the estimate, examples with larger natural-gradients contribute more to it and so we expect most of the sensitivity to be explained by just few examples with largest natural gradients. This is similar to the representer theorem where
just a few support vectors are sufficient to characterize the decision boundary (29 47 10]. Here, such examples can be seen as characterizing the model's memory because perturbing them can make the model forget its essential knowledge. The phrase memory cemoury-ertuubattonn signifies this.
The equation can be easily adopted to handle arbitrary perturbation. For instance, consider pertur- bation (())= - ΣjEM (0). To estimate its effect, we divide qe by the likelihood approximations raised to c, giving the following variant,
0x,0
EM
x EM
A = Σ (A,), JEM
= (A.),
Vj E,
(7)
Ōc;
10=0
where we denote all ej in M by EM- Setting 6 in the left reduces to Eqq. which corresponds to removal. The example demonstrates how to adopt the MPE to handle arbitrary perturbations.

---

3.1 Unifying the existing sensitivity measures special cases of the MPE
The MPE is a unifying equation from which many existing sensitivity measures can be derived as special cases. We will show three such results. The first result shows that, for conjugate models, the MPE recovers the exact deviations given in Thm. I Such models include textbook examples [6], such as, mixture models, linear state-space models, and PCA. Below is formal statement.
Theorem 2 For conjugate MPE in Eq. Gevaluated at X of the exact posterior q. when we set E,(0) = - logg; and p 1.
cattneettialfammilyy models, [g.. 4 is obtuined
special case of the
The result holds because, for conjugate models, one-step of the BLR is equivalent to Bayes' rule and therefore 8, (A.) -2 (see [24 Sec. 5.1]). A proof is given in App. D along with illustrative example on the Beta-Bernon Bernuuli model. We note that a recent work in [49 also takes inspiration from Bayesian models, but their sensitivity measures lack the property discussed above. See also [[5] for a different approach to sensitivity analysis of variational Bayes with a focus on the posterior mean. The result above also justifies setting p 1, choice we will often resort to.
Our second result is to show that the MPE recovers the influence function by Cook 7
Theorem For linear regression, Eg. is obtained as a special case of the MPE in Eg. evaluated at X, of the exact posterior 9- N [0 H, H,')
The proof in App. E relies on two facts: first, the natural parameter is X, (H.O., H.,,, and second, the natural gradients for a Gaussian with mean m can be written as follows,
(A) = (g, H.m. HH,).
(8)
where g. = Fy (0) and H. = (2) This is due to 28 Eqs. 10-11], but proof
given in Fg.. 27 of App- CJ The theorem then directly follows by plugging (x.) in Fg.. 6 This derivation is much shorter than the classical techniques which often require inversion lemmas (see App. A.I). The estimated deviations are exact, which is not surprise because linear regression is a conjugate Gaussian model. However, it is interesting (and satisfying) that the deviation in 0, naturally emerges from the deviation in X..
Our final result is to recover influence functions for deep learning, specifically Eq. To do so, we use Gaussian posterior approximation q. = _e ') obtained by using the so-called Laplace's 's method 33 50 33). The Laplace posterior can be seen a special case of the BLR solution when the natural gradient is approximated with the delta method (28 Table 1]. Remarkably, using the same approximation in the MPF, we recover Eq.
Theorem
The influence function in Eg. 3 is obtained as a special case of the MPE in Eg.
evaluated at X, of the posterior q. N H. when we approximate g. (A) of Eq. 8 with the delta method by substituting Egg (0) ~ (O.) and Eg. [() ~ (.).
A proof is in App. FJ We note that Eq. can be justified as a Newton-step over the perturbed data but in the opposite direction [32 31). In similar fashion, [Bq.. 6]and | can be seen as natural- graddiinn steps in the opposite direction. Using the natural- -atural-gradient descent, as we have shown, can recover a variety of existing perturbation methods as special cases.
3.2 Generalizing the perturbation method to estimate sensitivity during training
Influence measures discussed so far assume that the model already trained and that the loss is differentiable. We will now present generalizations to obtain new measures that can be applied during training and do not require differentiability of the loss. We will focus on Gaussian q but the derivation can be extended to other posterior forms. The main idea is to specialize [Bqs. 6 and 7 to the algorithms covered under the BLR, giving rise to new measures that estimate sensitivity by simply taking step over the perturbed data but in the opposite direction.
We first discuss sensitivity of an iteration t of the BLR yielding a Gaussian d = -O(0 m, m, S,
The natural parameter is the pair X (S.m 2/2 S.). Using Eq. 8...8innBB 6 we get
s m
MM AM
S.m, =
Σ E g (E)
F.g. (0)) m., S. S. = P Σ
Bgg (V2 e (0)
JEM
JEM
(9)
5

---

Algorithm
Update
Sensitivity
Newton's 's method
0, + 0--1 H VC(0.-1)
(0))))
Online Newton (ON)
28
0. + 01-1 pS; VL(0,-1)
S, (0,))
ON (diagonal+minibacch) (28
0, + 01-1 psi VL(0,-1)
5, Vl((O,)
iBLR (dingonal-minibatch))
35
m; f- m ps: VL(00-1)
S;" (E,(O.)
RMSprop/Adam 30
([(1)11) 0, - 01- ps; 3
5, (e,(0,)
SGD
0. 0,-1 P0---VLC00 (
(l.
Table I: A list of algorithms and their sensitivity measures derived using Eg. 10 The second column gives the update, most of which use pre-conditioners that are either matrices (H, S,) vector (8t); see the full update equations in |Eqs. 37
App. C The third column shows the associated 34 [T]
sensitivity measure to perturbation in the i'th example which can be interpreted as a step for the example but in the opposite direction. We denote the element -iise multiplication between vectors by "." and the minibatch gradients by V. For iBLR, 0, is either m, or a sample from q:.
Plugging S, from the second equation into the first one, we can recover the following expressions.
m M m, m,
p(s)
k.
-EEge
Egg Σ (0)
Om,
Egg [L.
(10)
deg
JEM
c.=0
For the second equation, we omit the proof but is similar App.
resulting in preconditioning
with S,. For computational ease, we will approximate S. s S, even in the first equation. We will also approximate the expectation at a sample 0, ~ or simply at the mean 0, m,- Ultimately, the suggestion is to use S, - (O.) as the sensitivity measure, or variations of it, for example, by using a Monte-Carlo average over multiple samples.
Based on this, list of algorithms and their corresponding measures is given in Table 1 All of the algorithms can be derived as special instances of the BLR by making specific approximations (see (App. C.3). The measures are obtained by applying the exact same approximations Eq. 10
For example, Newton's method is obtained when m, 0,, S, = H and expectations are approximated by using the delta method at θg (similarly to Thm. 4). With these, we get
(VE R V(,)),,
(11)
which is the measure shown in the first row of the table. In similar fashion, we can derive measures for other algorithms that use a slightly different approximations leading to a different preconditioner. The exact strategy update the preconditioners is given in Eqs. 31 to 34 of App. C.3 For all, the sensitivity measure is simply an update step for the i'th example but in the opposite direction.
Table shows interplay between the training algorithm and sensitivity measures. For instance, it suggests that the measure H (O.) ) is justifiable for Newton's method but might be inappro- priate otherwise. In general, it is more appropriate to use the algorithm's 's preconditioner (if they use one). The quality of preconditioner (and therefore the measure) is tied to the quality of the posterior approximation. For example, R.Mpprpp's 's preconditioner is not good estimator of the posterior covariance when minibatch size is large [27] Thm. 1]. therefore we should not expect it to work well for large minibatches. In contrast, the ON method (28] explicitly builds good estimate of S, during training and we expect it to give better (and more faithful) sensitivity estimates.
For SGD, our approach suggests using the gradient. This goes well with many existing approaches 44 [4 51 3 but also gives a straightforward way to modify them when the training algorithm is changed. For instance, the TracIn approach (42 builds sensitivity estimates during SGD training by tracing (O,) (0,) for many examples and j. When the algorithm is switched, say to the S, (l,) Such modification is speculated in 42 Sec 3.2] and the MPE provides a way to accomplish exactly that. is also possible to mix and match algorithms with different measures but caution is required. For example, to use the measure in Eq. 11 say within a first-order method, the algorithm must be modified to build a well-conditioned estimate of the Hessian. This can be tricky and can make the sensitivity measure fragile (5).
ON method, we simply need to trace T,
Extensions to non-differentabble loss functions and discontinuous parameter spaces is straightfor- ward. For example, when using Gaussian posterior, the measures in Eq. 10 can be modified to

---

handle non con-differentiable loss function by simply replacing Egg. (0) with Vn [e), which simple application of the Bonnet theorem 44 (see Appp GD. The resulting approach more principled than [32 which uses an ad-hoc smoothing of the non-differentiable loss: the smoothing our approach is automatically done by using the posterior distribution. Handling of discontinuous parameter spaces follows in a similar fashion. For example, binary variables can be handled by measuring the sensitivity through the parameter of the Bernoulli distribution (see App. D).
3.3 Understanding the causes of high sensitivity estimates for the Gaussian case
The MPE can be used to understand the causes of high sensitivity-estinate We will demonstrate this for Gaussian g but similar analysis can be done for other distributions. We find that sensitivity measures derived using Gaussian posteriors generally have two causes of high sensitivity.
log p(y (o: where p(y:(u) is an exponential famill distribution with expectation parameter fs, fi (0) is the model output for the i'th example, and (-)) is an activation function, for example, the softmax function. For such loss functions, the gradient takes simple form: V4, = V f. the deviations in model outputs by using a first-order Taylor approximation.
To see this, consider a loss (0)
vil [6] Eq. 4. 1.12.. Using this, we can approximate
f((0)))- f(()))) f((O,) ~ (f,)
0,) = (o,) H. (o(f((0)) wil
(12)
Deviation in the output
Mix. prediction variance
Biit prediction error
where we used 0 0 ~ H V (O,) which based on the measure in the first row of Table I
Similarly to Eq. 2 the deviation in the model output is equal to the product of the prediction error
and (linearized) prediction variance of (0,) 25 20 The change in the model output is expected to be high, whenever examples with high prediction error and variance are removed.
We can write many such variants with a similar bi-linear relationship. For example, Eq. 12 can be extended to get deviations in predictions as follows:
a (ff(())))) ((((())) o' (f..0.)
0.) x o' (f(((O)))
(13)
Eq. 12 estimates the deviation at one example and at a location 0,, but we could also write them for q-- For example, to
a group of examples and evaluate them at the mean m, or at any sample remove group M of size M, we can write the deviation of the model-output vector f(0) E R
f(m) f(m) (f(,,) (T, ((( y),
(14)
where is the vector of labels and we used the sensitivity measure in Eq. 10 An example for sparse Gaussian process is in App. H The measure for SGD Table can also be used which gives f((O)') - (0,)) z [0) Fee which is similar to the scores used in 40 The list in [Table I suggests that such scores can be improved by using H, or S,, essentially, replacing the gradient norm by an estimate of the prediction variance. Additional benefit can be obtained by further employing samples from qe instead of using a point estimate O, or m;; see an example in App.. H]
It is also clear that all of the deviations above can be obtained cheaply during training by using already computed quantities. The estimation does not add significant computational overhead and can be used to efficiently predict the generalization performance during training. For example, using we can approximate the leave-one-out (LOO) cross- valsidaaio (CV) error as follows,
Eq. 12,
N
N
LOO Σ (000)
~ log (( + Uxeet)). (15)
The approximation eliminates the need to train N models to perform CV, rather just uses en and Va which are extremely cheap to compute within algorithms such as ON, RMSprop, and SGD. Leave-group (LGO) estimates can also be built, for example, by using Eq. 14] which enables us to understand the effect of leaving out a big chunk of training data, for example, an entire class for classification. The LOO and LGO estimates are closely related to marginal likelihood and sharpness,
both of which are useful to predict generalization performance 22 12 19. Estimates similar to Eq. 15 have been proposed previously [43 4 but none of them do so during training.
7

---

1.0
Estimated Deviation
05
0.5
0.5 True Deviation
0:25 True Deviation
95%
True Deviation
88%
0.2%
2%
1% 1% 1%
5% 4% 2%
1% 1%
1%
0.3
6% 5% 2% 3%
Low Sensitivity
High Sensitivity
Low Sensitivity
High Sensitivity "Bag" "Shoe"
Low Sensitivity
High Sensitivity "Dog" "Bird"
33"
$7
"3"
"Bag" "Shoe" *
"Dog" "Bird"
3
7
3
1
3
7
3
7
3
7
7
7.
(a) MLP on MNIST
(b) LeNet on FMNIST
(c) CNN on CIFAR-10
Figure 2: The estimated deviation for an example removal correlates well with the true deviations in predictions. Each marker represents an example. For each panel, the histogram at the bottom shows that the majority examples have low sensitivity and most of the large sensitivities are attributed to small fraction of data. We show a few images of high and low sensitivity examples from two randomly chosen classes, where we observe the nigh-sensitivity examples to be more interesting (possibly mislabeled or just ambiguous), while low- oow-eenitivvity examples appear more predictable.
4 Experiments
We show experimental results to demonstrate the usefulness of the MPE to understand the sen- sitivity of deep-learning models. We show the following: (1) we verify that the estimated devi- ations (sensitivities) for data removal correlate with the truth; (2) predict the effect of class removal on generalization error; (3) we estimate the cross-validation curve for hyperparameter tun- ing: (4) we predict generalization during training; and (5) we study evolution of sensitivities during training. All details of the experimental setup are included in (App. and the code is available at httpa:// www.c//.mmaa.eee.ce approx-
Estimated deviations correlate with the truth: Fig. 2 shows a good correlation between the true deviations a (f)))))) a (O:())) and their estimates o (O.))u,,
shown in [q. 13 We show results for three datasets, each using different architecture but all trained using SGD. To estimate the Hessian H. and compute via- (f( H. (..(.), we use Kronecker-factored (K-FAC) approximation implemented in the laplace I and ASDL [39 packages. Each marker represents data example. The estimate roughly maintains the ranking of examples according to their sensitivity. Below each panel, a histogram of true deviations is included to show that the majority of examples have extremely low sensitivity and most of the large sensitivities are attributed to a small fraction of data. The high-sensitivity examples often include interesting cases (possibly mislabeled or simply ambiguous), some of which are visualized in each panel along with some low-sensitivity examples to show the contrast. High-sensitivity examples characterize the model's memory because perturbing them leads a large change in the model. Similar trends are observed for removal of groups of examples in Fig. 6 of [fppApp 1.2
Predicting the effect of class removal on generalization: Fig. 3(a) shows that the leave-group-out estimates can be used to faithfully predict the test performance even when whole class removed. The x-axis shows the test negative log-likelihood (NLL) on a held-out test set, while the y-axis shows the following leave-one-class-ott (LOCO) loss on the set of left-out class.
LOCOc(0.) Σ (((0)0)
Σ (o Us vi.e)))).
8

---

Class "Bag"
Low Sensitivity
High Sensitivity
Leave-one- -ae----cssouulee out Estimation
1.02
MLP LeNet
Shirt
0.82
Estimated Deviation
Pullover
0.62
Coat
Top
Dress
0.42
50'th
Sandal
25'th
0.22
Bag
Ankle-boot
10'th
Sneaker
1st epoch
Trouser
0.02
Test Neg. Log-Likelihood (NLL)
Low Sensitivity
Examples
High Sensitivity
(a) Predicting the effect of class removal
(h) Evolution of sensitivities during training
Figure 3: Panel (a) shows, in the x-axis, the test NLL of trained models with class removed. In the y-axis, we show the respective leave-one-class-our (LOCO) estimates. Each marker correspond to specific class removed (text indicates class names). Results for models FMNIST shown. Both show good correlation between the test NLL and LOCO estimates; see the dashed lines. Panel (b) shows the evolution of estimated sensitivities during training of LeNet5 on FMNIST. As training progresses, the model becomes more and more sensitive to a small fraction of data.
0.2
0.5
Test NLL
LOO-CV
0.3
10a
10
10
10
10
10a
10a
6
(a) MLP MNIST
(b) LeNet5 on FMNIST
(c) CNN CIFAR-10
Figure 4: The test NLL (gray) almost perfectly matches the estimated LOO-CV error of Eq. 15 (black). The x-axis shows different values of parameter of an Legreuularization 8l| /
The estimate uses an approximation: f:(0'9) f..0) & V.. H. jEC Ve, R Us. Uia
which is similar to Eq. 12 but uses additional approximation Ejec (O,) & (0.) to reduce computation due to matrix-vector multiplications (we rely on the same K-FAC approximation used in the previous experiment). Results might improve when this approximation is relaxed. We show results for two models: MLP and LeNet. Each marker corresponds to a specific class whose names are indicated with the text. The dashed lines indicate the general trends, showing good correlation between the truth and estimate. The classes Shirt, Pullover are the most sensitive, while the classes Bag, Trousers are least sensitive. A similar result for MNIST is in Fig. 1T(d) of Appp 1.3]
Predicting generalization for hyperparameter tuning:
We consider the tuning of the parameter for the L2-regularizer of form 6| /2, Fig. 4 shows an almost perfect match between the test NLL and the estimated LOO-CV error of Eq. 15 Additional figures with the test errors visualized on top are included in Fig. 7 of App. 1.4 where we again see close match to the LOO-CV curves.
Predicting generalization during training: As discussed earlier, existing influence measures are not designed to analyze sensitivity during training and care needs to be taken when using ad-hoc strategies. We first show results for our proposed measure in Eq. which gives reliable sensitivity estimates during training. We use the improved-BIi BBLR method [35] which estimates the mean m, and a vector preconditioner s; during training. We can derive an estimate for the LOO error at the mean following derivation similar to Eqs. 14]and] 15]
N
LOO(m:) Rs
log (( + vuea))
(16)

---

0.8
0.8
0.8
8
8
Test NLL
0.4
0.4
LOO-CV
0.4
25
50
75
100
100
25
50
75
100
Epochs
Epochs
Epochs
(a) iBLR & LOO of Eq. 16
(b) SGD & diagonal-GGN-LOO
(c) SGD & K-FAC-LOO
Figure 5: We compare faithfulness of L.O0 estimates during training to predict the test NLL.. The first panel shows results for iBLR where good match is obtained by using the LOQ estimate of Eq. 16 which uses diagonal preconditioner. The next two panels show results for SGD where we use the LOO estimate of Eqq. 13 but with different Hessian approximations. Panel (b) uses a diagonal-GGN which does not work very well. Results are improved when K-FAC used, but they are still not as good as the iBLR, despite using a non-diagonal Hessian approximation.
where e4e
V (m and ese (m;(mm)) y/-
The first panel in Fig. 5 shows a good match between the above IOO estimate and test NLL. For comparison, in the next two panels, we show results for SGD training by using two ad-hoc measures obtained by plugging different Hessian approximations in Eq.. IT] The first panel approximates H. with a diagonal Generalized Gauss-Newton (GGN) matrix, while the second panel uses K-FAC approximation. We see that Slagonal-GGN-LL LOO improves this, it is still not good the iBLR result despite using non-diagonal Hessian approximation. Not to mention, the two measures require an additional pass through the data to compute the Hessian approximation, and also need careful setting of damping parameter.
does not work well at all and, while K-FAC-
A similar result for iBLR is shown in ig. I(b) where we use the larger ResNet-20 on CIFARIO, and more such results are included in Fig. 8 of App. I.3] We also find that both diagonal-GGN- I.0 or K-FAC-LOO further deteriorate when the model overfits; see sie 9 Results for the Adam optimizer are included in Fig. TO, where we again see that using ad hoc measures may not always work. Overall, these results show the difficulty of estimating sensitivity during training and suggest to take caution when using measures that are not naturally suited to analyze the training algorithm.
Evolution of sensitivities during training: Fig. 3(b) shows the evolution of sensitivities of ex- amples as the training progresses. We use the iBLR algorithm and approximate the deviation as (f((m)))) (m:)) o' (f.)m))) where va and egt are obtained similarly to Eq. 16 The x-axis corresponds to examples sorted from least sensitive to most sensitive examples at con- vergence. The y-axis shows the histogram sensitivity estimates. We observe that, as the training progresses, the distribution concentrates around small fraction of the data. At the top, we visu- alize a few examples with high and low sensitivity estimates, where the high-sensitivity examples included interesting cases (similarly to/Fig. 2). The result suggests that the model concentrates more and more on a small fraction high-sensitivity examples, and therefore such examples can be used to characterize the model's memory. Additional experiments of this kind are included in Fig. of
App. 1.6 along with other experiment details.
Discussion
We present the memory-perturbatie equation by building upon the BLR framework. The equation suggests to take step in the direction of the natural gradient of the perturbed examples. Using the MPE framework, lems, and unravel useful properties regarding sensitivity. We also show that sensitivity estimation can be done cheaply and use this predict generalization performance. An interesting avenue for future research is to apply the method to larger models and real-world problems. We also need to understand how our generalization measure compares to other methods, such as those considered in (22. We would also like to understand the effect of various posterior approximations. Another interesting direction is apply the method non non-Gaussian cases, for example, to study ensemble methods in deep learning with mixture models.
unify existing influence measures, generalize them wide variety of prob-
10

---

Acknowledgements
This work supported by the Bayes duality project, JST CREST Grant Number JPMJCR2112.
References
[1] Vincent Adam, Paul Chang, Mohammad Emtiyaz Khan, and Amo Solin. Dual Parameteri- zation of Sparse Variational Gaussian Processes. Advances in Neural Information Processing Systems, 2021. 20
[2] Chirag Agarwal, Daniel D'Souza, and Sara Hooker. Estimating Example Difficulty using Variance of Gradients. In Proceedings of the IEEE Conference Computer Vision and Pattern
Recognition, 2022. 3
[3] Devansh Arpit, Stanistaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj. Asja Fischer, Aaron Courville, Yoshua Bengio, and Si- mon Lacoste-Julien. A Closer Look at Memorization in Deep Networks. In International Conference on Machine Learning, 2017. 3
[4] Gregor Bachmann, Thomas Hofmann, and Aurélien Lucchi. Generalization Through The Lens of Seave-One-Oue Error. In International Conference Learning Representations, 2022.
[5] Samyadeep Basu, Phil Pope, and Soheil Feizi. Influence Functions in Deep Learning Are Fragile. In International Conference on Learning Representations, 2021.
[6] Christopher M. Bishop. Pattern Recognition and Machine Learming. Springer, 2006.
[7] R Dennis Cook.
Detection of Influential Observation in Linear Regression. Technomelries,
1977.
5
[8] Dennis Cook and Sanford Weisberg. Characterizations of an Empirical Influence Function for Detecting Influential Cases in Regression. Technometrics, 1980. 3
[9] Dennis Cook and Sanford Weisberg. Residuals and Influence in Regression. Chapman and Hall, 1982. 14
[10] Corinna Cortes and Vladimir Vapnik. Support- Vector Networks. Machine learning. 1995.
[11] Erik Daxberger, Agustinus Kristiadi, Alexander Immer, Runa Eschenhagen, Matthias Bauer, and Philipp Hennig. Laplace Redux-Effortles: Bayesian Deep Learning. Advances in Neural Information Processing Systems, 2021.
[12] Gintare Karolina Dziugaite and Daniel M Roy. Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters Than Training Data. In Proceedings the Conference on Uncertainty in Artificial Intelligence, 2017.
[13] Vitaly Feldman and Chiyuan Zhang. What Neural Networks Memorize and Why: Discover- ing the Long Tail via Influence Estimation. In Advances in Neural Information Processing Systems, 2020.
[14] Wing Fung and CW Kwan. Note on Local Influence Based on Normal Curvature. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 1997. 1
[15] Ryan Giordano, Tamara Broderick, and Michael Jordan. Covariances, robustness and varia- tional Bayes. Journal of Machine Learning Research, 19(51), 2018.
5
[16] Satoshi Hara, Atsushi Nitanda, and Takanori Machara. Data Cleansing for Models Trained with SGD. Advances in Neural Information Processing Systems, 2019.
[17] Hrayr Harutyunyan, Alessandro Achille, Giovanni Paolini, Orchid Majumder, Avinash Ravichandran, Rahul Bhotika, and Stefano Soatto. Estimating Informativeness of Samples with Smooth Unique Information. International Conference on Learning Representations,
2021.6 g

---

[18] James Hensman, Nicolo Fusi, and Neil D Lawrence. Gaussian Processes for Big Data. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2013, 20
[19] Alexander Immer, Matthias Bauer, Vincent Fortuin, Gunnar Rätsch, and Mohammad Emtiyaz Khan. Scalable Marginal Likelihood Estimation for Model Selection in Deep Learning. In International Conference on Machine Learning, 2021.
[20] Alexander Immer, Maciej Korzepa, and Matthias Bauer. Improving Predictions of Bayesian Neural Nets via Local Linearization. International Conference on Artificial Intelligence and Statistics, 2021. 7
[21] Louis A Jaeckel. The Infinitesimal Jackknife. Technical report, Bell Lab., 1972.
[22] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fan- tastic Generalization Measures and Where To Find Them. International Conference on Learning Representations, 2020.
T0
[23] Angelos Katharopoulos and Francois Fleuret. Not All Samples Are Created Equal: Deep Learning with Importance Sampling. In International Conference on Machine Learning, 2018.
[24] Mohammad Emtiyaz Khan. Variational Bayes Made Easy, Fifth Symposium on Advances in Approximate Bayesian Inference, 2023. 5
[25] Mohammad Emtiyaz Khan, Alexander Immer, Ehsan Abedi, and Maciej Korzepa. Approxi- mate Inference Turns Deep Networks into Gaussian Processes. Advances in Neural Informa- tion Processing Systems, 2019.
17
[26] Mohammad Emtiyaz Khan and Wu Lin. Conjugate-Computaiie Variational Inference: Con- verting Variational Inference in Conjuonee Models to Inferences in Conjugate Models. In International Conference Artificial Intelligence and Statistics, 2017. 4 15 20
[27] Mohammad Emtiyaz Khan, Didrik Nielsen, Voot Tangkaratt, Wu Lin, Yarin Gal, and Akash Srivastava. Fast and Scalable Bayesian Deep Learning by Pright-Perturbation in Adam. In International Conference on Machine Learning. 2018
25
[28] Mohammad Emtiyaz Khan and Hävard Rue. The Bayesian Learning Rule. Journal of Machine Learning Research, 2023.
18
[29] George S Kimeldorf and Grace Wahba. A Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines. The Annals of Mathematical Statistics, 1970.
4
[30] Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In Interna-
tional Conference on Learning Representations, 2015. 6
[31] Pang Wei Koh, Kai-Siang Ang, Hubert Teo, and Percy S Liang, On the Accuracy of Influ- ence Functions for Measuring Group Effects. In Advances in Neural Information Processing Systems, 2019.
[32] Pang Wei Koh and Percy Liang. Understanding Black-Box Predictions via Influence Functions. In International Conference Machine Learning, 2017.
[33] Aran Komatsuzaki. One Epoch is All You Need. ArXiv e- e-Prints, 2019.
[34] Pierre-Simon Laplace. Mémoires de Mathématique et de Physique. Tome Sixieme, 1774.
[35] Wu Lin, Mark Schmidt, and Mohammad Emtiyaz Khan. Handling the Positive-eefinie Con- straint in the Bayesian Learning Rule. In International Conference on Machine Learning, 2020.
17
18
[36] Ilya Loshchilov and Frank Hutter. Decoupled Weight Decay Regularization. International Conference Learning Representations, 2019, 23
12

---

[37] David JC MacKay. Information Theory, Inference and Learning Algorithms. Cambridge Uni- versity Press, 2003.
[38] Roman Novak, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl- Dickstein. Sensitivity and Generalization in Neural Networks: An Empirical Study, In In- ternational Conference on Learning Representations, 2018. 2
[39] Kazuki Osawa, Satoki Ishikawa, Rio Yokota, Shigang Li, and Torsten Hoefler. ASDL: A Unified Interface for Gradient Preconditioning in PyTorch. In NeurlPS Workshop Order up! The Benefits of Higher-Order Optimization in Machine Learning, 2023. 8
[40] Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep Learning on a Data Diet: Finding Important Examples Early in Training. In Advances Neural Information Processing Systems, 2021.
6 7
[41] Daryl Pregibon. Logistic Regression Diagnostics. The Annals of Statistics, 1981. 14
[42] Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating Training Data Influence by Tracing Gradient Descent. In Advances in Neural Information Processing Systems, 2020. 6
[43] Kamiar Rahnama Rad and Arian Maleki. A Scalable Estimate of the Out-of-Sample Predic- tion Error via Approximate Leave-One-Out Cross- Validdaiii Journal of the Royal Statistical Society Series B: Statistical Methodology, 2020.
[44] Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic Backpropagation and Approximate Inference in Deep Generative Models. In International Conference on Ma- chine Learning. 2014. 17
[45] Hugh Salimbeni, Stefanos Eleftheriadis, and James Hensman. Natural Gradients in Practice: Non-Conjugate Variational Inference in Gaussian Process Models. In International Conference on Artificial Intelligence and Statistics, 2018. 20
[46] Frank Schneider, Lukas Balles, and Philipp Hennig. DeepOBS: A Deep Learning Optimizer Benchmark Suite. In International Conference on Learning Representations, 2019. 21
[47] Bernhard Schölkopf, Ralf Herbrich, and Alex J Smola. A Generalized Representer Theorem. In International Conference on Computational Learning Theory, 2001.
[48] Saurabh Singh and Shankar Krishnan. Filter Response Normalization Layer: Eliminating Batch Dependence in the Training of Deep Neural Networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2020. 21
[49] Ryutaro Tanno, Melanie F Pradier, Aditya Nori, and Yingzhen Li. Repairing Neural Networks by Leaving the Right Past Behind. Advances in Neural Information Processing Systems, 2022.
[50] Luke Tiemey and Joseph B Kadane. Accurate Approximations for Posterior Moments and Marginal Densities. Journal of the American Statistical Association, 1986. 5
[51] Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Ben- gio, and Geoffrey J. Gordon. An Empirical Study of Example Forgetting during Deep Neural Network Learning. In International Conference on Learning Representations, 2019. 3
[52] Robert Weiss. An Approach to Bayesian Sensitivity Analysis. Journal of the Royal Statistical Society Series B: Statistical Methodology, 1996.
[53] Fuzhao Xue, Yao Fu, Wangchunshu Zhou, Zangwei Zheng, and Yang You. To Repeat or Not To Repeat: Insights from Scaling LLM under Token-Crisis. ArXiv e-Prints, 2023. 3
[54] Hongtu Zhu, Joseph G. Ibrahim, Sikyum Lee, and Heping Zhang. Perturbation Selection and Influence Measures in Local Influence Analysis. The Annals of Statistics, 2007.
13

---

A Influence Function for Linear Regression
We consider N onput- pairs (x,,)) The feature matrix containing x rows is denoted
by X and the output vector of length N is denoted by y. The loss is ( = (v: - f())) for
f0( - x O. The regularizer is assumed to be R()) /| The minimizer given by
0, H X y.
(17)
We define a perturbation model as follows with & E R:
0 arg min (()) (0))
0
For 6 1, it corresponds to example removal. An arbitrary 4 simply weights the example accord- ingly. The solution has closed-form expression,
0 (H. -xxxx,
(18)
where H. - Lim1 x
+ pIp is the Hessian of (()). We first derive closed-form expressions for 0 - O., and then specialize them for different Eç.
A.1
Derivation of the leave-one-out (LO0) deviation
We denote E. H., and use the Sherman-Morriso formula write
e.E.x,X Σ.
0 = E. + 1- EXX; E.x;
x y <.1xxi)
ΣXX
EXXAX Σxx,
Σ.X y + E.E.X,
V/
GX Σ,x;
1 G.. E,x;
(19)
x 0,
0. E.E,
1/3
4:
x 0, Vi
GE
0. + 4.E,
= 02 E,
- 6,0%
6.0%
In line 3 we substitute v; = x Σ.x; and 0, = =.x y and in the last step we use e; = x, 0. yi-
We define e, / e - 11) which is the prediction error of 0/i
x 0 y/s = x
Ci 0. + E.x 1- y/ - - 0, +
1/4
Cg
91
C2
(20)
1- 14
-
Therefore, we get the following expressions for the deviation.
0 Ex
f((0')) f0.)) = vse)
These expressions can be written in the form of Eq. 2 by left miltipplliingg with Σ.¹ = -H +x,,,
(H)² + x0) 0.) = (x} 0/ 34) 0 : - 0. = (HQ') X,et.
A.2 Derivation of the infinitesimal perturbation approach
We differentiate 0% in Eq. 19 to get
00
6
E.x,
(21)
dc;
(1 -1- E22;)2
yielding the following expressions:
00% Exx,,,
(f.(
00
= =x, E. U.C.-
(22)
dc:
de;
+,=0
1,=0
The second equation in Eq. 22 follows from the chain rule. We get bi-linear relationship of the in-
fluence measure with respect to v; and prediction error e,, it also possible to evaluate Fiq. 21 6;
I representing an infinitesimal perturbation about the LOO estimate, 80 /0eile.- Σ'x,,
From this and Eq.. 22, we can interpret Eqq. as the average derivative over the interval e; E [0.
or the derivative evaluated at some 0 < (via an application of the mean value theorem) 41
14

---

B Conjugate Exponential-Family Models
Exponential-Famme distributions take the following form:
h exp [A, T(0)) - A
where À E 92 are the natural (or canonical) parameter for which the cumulant (or log partition) function A() is finite, strictly convex and differentiable over f2 The quantity T(Ø) is the sufficient statistics, (.,)) is an inner product and h()) is some function. A popular example is the Gaussian distribution, which can rearranged to take an exponential-famigy form written in terms of the precision matrix S = Σ_
(0 Σ) 12 - exp - m) 0 m)
exp 0 Sm
1 So (m' Sm log |2nS
From this, we can read-off the quantities needed to define an exponential-fomm.
À (Sm, SS), T(0) (0, )0"), A(A) 1 (m" Sm log 12*S h(0) 1. (23)
Both the natural parameter and sufficient statistics consist of two elements. The inner-produce for the first elements is simply a transpose to get the 0 Sm term, while for the second element it is trace which gives Tr(00) 5/2) - SO.
Conjugate Exponential-Faniin
Models are those where both the likelihonds and prior can be ex- pressed in terms of the same form of exponential-famil distribution with respect to For instance, in linear regression, both the likelihood and prior take Gaussian form with respect to 0,
P. = p(y x. 0) = (y x 0,1) & exp
x,yi
-100= x
Po = p(0) = (e 0. I/0) x exp
- (dI)
Note that p, is distribution over y4 but it can also be expressed in an (unnormalized) Gaussian form with respect to 0. The sufficient statistics of both p. and po correspond to those of a Gaussian distribution. Therefore, the posterior is also a Gaussian,
q. = p(0) D) x PoP112 ... PN
N
cxp
0
(OI)
0
exp
x,Yi
10 Tx e)
1=1
N
N
exp
0
X;U: 2
0I
X;X;
0
i=1
1=1
0 H,O
1 H.O
exp
H,,
The third line follows because 0. - - y, as shown Eq.
These computations can be written as parameters,
26
where we simply add the natural
P. x exp (A. I(0)) where X; = (X,V), xxxxx]
Po exp (Ao. T(O))], where Xy (0, j01)
q. exp (A., T(O)),, where A. Do- Σ x (H.O., -H..).
In the same fashion, to remove the contributions of certain likelihoods, we can simply subtract their natural parameters from X.. These are the calculations which give rise to the following equation:
(T(O), Aa)
IM go
AWM)
(T(O), ALM)
M Σ X
11 P2j
JEM XT)
JEM
15

---

C The Bayesian Learning Rule
The Bayesian learning rule (BLR) aims to find posterior approximation g R p(0 x 2(0) Often, one considers regular, minimal exponential-family g 2, for example, the class of Gaus- sian distributions. The approximation is found by optimizing generalized Bayesian objective,
q+ = arg min Ey [C(()) - -H(
PEQ
where H((g) = l- [()] is the entropy of and Q is the class of exponential family approxi- mation. The objective is equivalent to the Evidence Lower Bound (ELBO) when L()) corresponds to the negative log-joint probability of a Bayesian model; see (28, Sec 1.2].
The BLR uses natural-gradient descent find qu, where each iteration takes the following form,
- A (F(A--1)
EEg [C(0)] H(g)
(24)
Ox
A=À--1
where p > is the learning rate. The gradient computed with respect to (through q), and we scale the gradient by the Fisher Information Matrix (FIM) defined follows,
F(A)= F, [VV log g) (V logg)"] A())
The second equality shows that, for exponential- distribution, the above FIM is also the second derivative of the log- partiaiiiion function A()).
C.1
The BLR Eq. 5
The BLR in Eq. 5 is obtained by simplifying the natural-gradient using the following identity,
F(A) ((A)- V,LE,())
(25)
where / is the expectation parameter. The identity works because of the minimality of the exponential-famitt which ensures that there is one-to-one mapping between À and μ., and also that the FIM is invertible. Using this, we can show that the natural gradient of H(g) is simply equal A: see 28 App. B]. Defining (0) R(0), we get the version of the BLR shown in Eq.
N
A - - -) P
Σ E (A-1)), where (y(A
(0) -
1=0
C.2
The conjugate-model form of the BLR given in Fq.
To express the update in terms of the posterior of conjugate model, we simply take the inner product with T(0) and take the exponential to write the update as
((0)) ( (A
( (()
II ( (R, (A-
(26)
ocge
acpo
The simplification of the second term on the left to Po happens when Po a conjugate prior, that is, Po exp( (Ao; T()))) for some Ao (see example in App. B where we show that L2 regularizer leads to such a choice). In such cases, we can simplify,
(- T(0)) V,,,Elloggi T(0) (V (Ao p)) T())) (Ao. T(Ø) log Po + const.
Using this in Eq. 26 recover the conjugate model given in Eq. 5
C.3 BLR for Gaussian y and the Variational Online Newton (VON) algorithm
By choosing an appropriate form for d: and making necessary approximations to gi the BLR can recover many popular algorithms as special cases. We will now give few examples for the case of Gaussian g: -O m, Σ,) which enables derivation of various first and second-order optimization algorithms, such as, Newton's 's method, RMSprop, Adam, and SGD.
16

---

As shown in Eq. 23 for a Gausian (m Σ), the natural parameter and sufficient statistics are shown below, along with the expectation parameters μ E [TO)).
X = (Sm, - S),, T(Ø) - (0, 00
(m, mm + E),
Using these, we can write the natural gradients as gradients with respect to n. and then using chain-rule express them gradients with respect to and Σ,
mm -x )
By [c)
- 8 H B
By (A) V Eel
(27)
H
where in the last equation we define two quantities written in terms of (ly and (,) by using Price's and Bonnet's is theorem 44].
V m L Egg (V)
H, =
(28)
Plugging these into the BLR update gives us the following update,
N
S,m, < (1 -) m.
H
- 8)0-1), S. + (1-)) +
H
1--1
j=0
j=0
where 8 and H , are quantities similar to before but now evaluated the ---1- The conju- gate model can be written as follows,
x s. -5.mm T.o x (9)-1)) o- i, 1,,,- 1, 1
II j=1
The prior above is Gaussian and defined using q-1 and pg. The model uses likelihoods that Gaussian distribution with information vector i = p(Hj,--m.-1 - -1 and information matrix I, 1 مH j,r- The likelihood is allowed to be improper distribution, meaning that its integral is not one. This is not a problem as long as S, remains positive definite. A valid S, can be ensured by either using Generalized Gauss-Newton approximation the Hessian (27] or by using the improved BLR of 355. The former strategy is used in (25 to express BLR iterations as linear models and Gaussian processes. Ultimately, we want to ensure that perturbation the approximate likelihoods in qe yields valid posterior and, as long as this is the case, the conjugate model can be used safely. For instance, in Thm. 4, this issue poses no problem all.
The BLR update can be rearranged and written in a Newton-like form show below,
VON:
m. + m. pS, By... [VL())),
S, + (1==))((s1++p.. C (29)
This is called the Variational Online Newton (VON) algorithm. A full derivation is in 27 with details many of its variants in 28 The simplest variant is the Online Newton (ON) algorithm, where we use the delta method,
Py [L()) VL
E [C2(0)] V²L(m.))
(30)
Then denoting m, 0,, we get the following ON update,
ON: 0 0.-1 PS, VL(O,-1),
S +1- PV
(31)
To reduce the cost, Additionally, we can use minibatching to estimate the gradient and hessian (denoted by V and V2),
diagonal approximation S, diag(s:) where 8; is scale vector.
ON (diagonal-minibatch)::
0, +- 0,-1 ps, (((..1)).
(32)
S; +- p) 1 p diag( (())))))
where- indicates element-wis product two vectors and diag(-) extracts the diagonal of a matrix.
Several optimization algorithms can be obtained as special cases from the above variants. For ex- ample, to get Newton's method, we set p 1 in ON get
0, - 0 -
VL(0,-1).
(33)
17

---

RMSprop and Adam can be derived in similar fashion 28
In our experiments, proved version of VON (27 Eqs. 7-8] which ensures that the covariance is always positive-definite when the Hessian estimates not. We diagonal approximation S diag(o2)-1,
the improved BLR iBLR optimizer
35 We use to implement im-
momentum and minibatching as proposed in [27 35). For learning rate 31, 82 [0, 1) the iterations written follows:
0, momentum
iBLR:
B: BI (1 B1)8
h - 3 + (1 -2 +
hn-1)//(bt-1 +
(34)
m t m - ag + .m 10/ (h; 6),
a t 1/(N(h, + 6))-
Here, 8 > is the In-regularization parameter and 8,-1 Eien B (0) (V)) h Σier B (,) ()) m,-1)/a denote Monte-Carlo approximations of the expected stochastic gradient and diagonal Hessian under (=1 N m diag(o? and minibatch B. As suggested in [27 35). we used the reparametrization trick estimate the diago- nal Hessian via gradients only. In practice, we approximate the expectations using single random sample. We expect multiple samples further improve the results.
D Proof Thm. and the Beta-Bernould Model
From Eq. 27, it directly follows that
8,(A) = V T, 1- log = V ( E, ((())) = = V = X
Using this in Eq. 6 we get the deviation given in Eq. 4
We will now show an example on Beta-Bemoulli model, which is conjugate model. We assume the model be p(D, x p(0) II p(y: [0) where the prior p(0) = Beta Oo (8) and likelihoods are p(ua(0) = (er (0) with D;
This is conjugate model and the posterior is Beta distribution,
that is, it takes the same form as the prior. An expression given below,
N Σ ==1
= [Beta(Ola.,,.)) Ba), where a. = on +
B. = 30
+ N
j=1
The posterior for the perturbed dataset D' is also available in fooeddform::
N
/hº² (ota BB²),, where a. 0gg
Mi 3.- 30
N
1=1,
j
jt1
Therefore the deviations in the posterior parameters can be simply obtained as follows:
a, = -9: a 3. y/1
(35)
This result can also be straightforwardly obtained using the MPF. For the Beta distribution gx (0) = Beta(Olo, 3), have À (a 1, 1), therefore X X, (a. a., 3. 8_). For Beta
distribution, T(0) = (log 0, log(1 - 0)) and writing the likelihood in an exponential form, we get
p(y (0) Ber(y; (0) x oo 0)* 1- yi oc ui log 0+ (1=g))log(1--0
therefore X; (Vi, U: 1). Setting \ A. Àí we recover the result given in Eq. 35
E
Proof of Thm. 3
For linear regression, we have
ve,(0) xx,(xxxxx -v)),
V2E,(0) = X,X_T x
18

---

Using these in Eq. we get,
g (A.) B,g [x, 0 -y))- x; O., [x,x,] = (-x:W)i, fx,x,)
The natural parameter is X, (H.0.- HH.). In similar way, define q. and its natural parameter. Using these, we can write Eq. ass
H H H.O. -X,3/
+ H = x
Substituting the second equation into the first one, we get the first equation below,
H - (H +x,x, 00- = -X,y
0 0--0. (H 0.-3:) -H, x.e,
The last equality is exactly Since linear regression is conjugate model, an alternate derivation would be to directly use the parameterization X; of P4 (derived in App. B) and plug it in TTm. 2
F
Proof of Thm. 4
For simplicity, denote
OA,' DE,
05 F0=
1,,=0
with X as defined in Eq. 7 in the main text. For Gaussian distributions, the natural parameter comes pair x_ (H, 0 H. Its derivative with respect to E; at E; can be written as the following by using the chain rule:
ax, --
(H,00,
-HH O., -OH
Here, we use the fact that, as G -> O, we have (0 H + (0., H.) and also assumed that the limit of the product is equal to the product of the individual limits. Next, we need the expression for the natural gradient, for which we will use BefEE. 8ubut approximate the expectation by using the delta approximation E,, [0) g(O.) for any function g, shown below define:
g (A.) [e,(0.) V=L,(==0,. (e.)]
The claim is that if we set the perturbed Ø,, c.=0 = (A.) we recover Eq. 3 that is, we set
H. 0, + O = ve(0.) v² (e.)o..
-H = (0.)
Plugging the second equation into the first, the second term cancels and we recover Eq.
G Extension to Non-Differentiable Loss function
For con-differentiable cases, we can use Eq. 28 to rewrite the BLR of Eq. 29 as
m <- m pS, IC(0),
S. - (1-11)) + 2 (C(O))
(36)
where Σ = S Essentially, we take derivative outside the expectation instead of inside which valid because the expectation of non-differentiable function is still differentiable (under some regularity conditions). The same technique can be applied to Eq. 8 to get
g (A) = (Vm (z. m. (=R,(((())).
(37)
) Ey, [(). This the and proceeding in the same fashion we can write: m -m, m; extension of Eg. 10 to non-differentiable loss functions.
19

---

H Sensitivity Measures for Sparse Variational Gaussian Processes
Sparse variational GP (SVGP) methods optimize the following variational objective find Gaus- where [ 2, Φ) = Σ Bai [ogp(usls)) TKk (q(()) Il
sian posterior approximation q(u) over function values u := 2 (11, ....... ZM) is the of inducing inputs with M N:
where puu) ;= (u Kuu) is the prior with Kuu as the covariance function k(:, evaluated at 2, ((::) = [[ m, a Σa; + o is the posterior marginal of f; = f(x,) with a; := Kuuk and of := Kü a, a as the noise variance fi conditioned on The objective also used to optimize hyperparameters & and inducing input set 2.
We optimize the objective using the BLR for which the resulting update is identical to the variational online-newton (VON) algorithm. We first write the natural gradients.
Vlg lorplllooopplllll logp(ulf(t) ((ea Bra, m.)a, 1
(38)
where we define
Cst E (A) ,. log)(
Ba = E Vi log p(y)(()
We define A to be a matrix with a. as rows, and e,, Br to be vectors of Eit, Bic. Using these in the VON update, simplify follows:
S (1 p)S, + A diag(3,)A K
(39)
m | [1- (1-p)S,m A ATo e
A diag (1.)
[(1- + pA diag(B.)A
m, pA -ATee
(S -pKml) m: pATe e
(40)
S
S41m - (AT e
Ae, + Kmn m.
m. -P A T K m,
For Gaussian likelihood, the updates in Eqs. 39 and 40 coincide with the method of (18) and for non-Gaussian likelihood they are similar to the natural-gradient method by [45), but we use the specific parameterization of [26]. An alternate update rule terms of site parameters is given by (see Eqs. 22-24).
We now ready write the sensitivity measure essentially substituting the gradient in Eq. 10
S.- ' (w) log (()l..)) S, (f)l - log p(v.l fi]] S, a,eu
(41)
We can also see the bi-linear relationship by considering the deviation in the mean of the posterior marginal f((m) a. m.
f. (m fi (m,,) ~ a. (m) - m.) = a. E,a;e; Ca
(42)
where Eo = a. E,a; is the marginal variance of fi.
I Experimental Details
L.1 Neural network architectures
Below, we describe different neural networks used in our experiments,
ML.P (500, 300): This multilayer perceptron (MIP) with two hidden layers of 500 and 300 neurons and parameter count of around 546 000 (using hyperbolic-tangent activations).
20

---

MLP (32, 16): This is also an MLP with two hidden layers of 32 and 16 neurons, which accounts for around 26 000 parameters (also using hyperbolic tangent activations).
LeNet5:
This a standard convolutional neural network (CNN) architecture with three convolution layers followed by two fully-connecter layers, corresponding to around 62 000 parameters.
CNN: This network. taken from the DeepOBS suite [46). consists of three convolution layers fol- lowed by three fully-connected layers with a parameter count of 895 000.
ResNet-20: This network has around 274 000 parameters. We use filter response normalization (FRN) [48] as an alternative to batch normalization.
MLP for USPS: For the experiment on binary USPS in Fig. 6(a) we use an MLP with three hidden
layers of 30 neurons each and a total of around 10.000 parameters.
I.2 Details of "Do estimated deviations correlate with the truth?"
In Fig. we train neural network classifiers with cross-entropy loss to obtain 0.. Due to the computational demand of per-example retraining, the removed examples are randomly subsampled from the training set. We show results over 1000 examples for MNIST and FMNIST and 100 examples for CIFAR10. the multiclass setting, the expression yields a per-class sensitivity value. We obtain scalar value for each example by summing over the absolute values of the per-class sensitivities. For training both the original model 0. and the perturbed models 0 we use SGD with momentum parameter of 0.9 and cosine learning-rate scheduler. To obtain 0 we retrain a model that is warmstarted at O.. Other details regarding the training setup are given Table 2 For all models, we do not use data augmentation during training. The resulting O, for MNIST, FMNIST, and CIFARIO have training accuracies of 99.9 99.9%, 95.0%, and 99.9%, respectively. The test accuracies for these models are 98.4%, 11. and 76.7%.
Dataset
Model
B
8
E
LR"
LR
EV
LR
LR
MNIST
MLP (500, 300)
256
100
500
10-2
10
300
10
10-3
10-4
FMNIST
LeNet5
256
100
300
10-1
10-3
200
10-3
10
10-4
CIFARIO
CNN
512
250
500
10-2
10
300
10
10
Table 2: Hyperparameters for predicting true sensitivity in in(Fig. 2
B, E and LR denote batch size, training epochs and learning-rates, respectively. The superscripts and V indicate hyperparame- ters for training on all data and warmstarted leave-one-out retraining, respectively. R.Rmin is the minimum lcarning-rate rate of the cosine scheduler.
Additional group removal experiments: We also study how the deviation for removing group of examples in a set M can be estimated using a variation of Ef. for the deviation in predictions at convergence. Denoting the vector of fi( for i E M by f (8), we get
a(f ((fm(0)M))an o(fm(())) (O..)) R Σ d'(in)umee..
(43)
EEM
is the prediction covariance of size M x M where M is the number of examples M, and e (0.)
where AO.) ) is diagonal matrix containing all d'(fi.), V (M.)) (O.))
is the vector of prediction errors. The last approximation above is done to avoid building the covari- ance, where we ignore the off-diagonal entrics of (0.)).
In Fig. 6(a) we consider binary USPS dataset consisting of the classes for the digits 3 and 5. Using |M| = 16, we show the first and second approximations in [q. 43 both correlate well with the truth obtained by removing a group and retraining the model. In Fig. 6(b) we do the same on MNIST with MM 64, where we see similar trends. For the experiment on binary USPS in Fig. 6(a) we train a MLP with three hidden layers with 30 neurons each. The original model 0, is trained for 500 epochs with learning-rate of 10-3, a batch size of 32 and a L--regularizzaion parameter has 100% training accuracy and 94.8% test accuracy. For the leave-group-out retraining to obtain M we initialize the model l., use learning-rate of 10-3 and train for 1000 epochs. For the MNIST result in Fig. 6(b) we use the MLP (500, 300) model with the same hyperparameters for
5.
21

---

1.2
group individual
Estimated Deviation
0.9
0.9
0.6
0.3
0.3
individual
0.0
0.0
0.0
0.3
0.6
0.9
1.2
0.0
0.4
0.8
1.2
1.6
True Deviation
True Deviation
(a) MLP on USPS-3vs5, | = 16
(b) MLP on MNIST, | 64
Figure 6: Panel (a) and Panel (b) show that the estimated deviation for removal of groups of exam- ples correlates well with the true deviations obtained by retraining. Each marker corresponds to removed group of examples. The red circles show the second approximation [Fq. 43) In Panel (a), we additionally show (with blue squares) the first approximation of [E.. 43 We see that the second approximation is quite accurate in this case.
0. in Table For 0 M. initialize the model at 0 and cosine schedule of the learning- from 10 to 10 5 over 500 epochs. We do not use data augmentation. Similarly to the experiments on per-example removal, we use K-FAC approximation.
Dataset
Model
E
LR"
LR
LRIC
LR min
MNIST
MLP (500, 300)
500
10 10-2
10-3
10
10
MNIST
LeNet5
300
10-1
10-3
10-5
10-6
FMNIST
MLP (32, 16)
300
10-2
10-3
10-5
10-6
FMNIST
LeNet5
300
10
10-3
10
10
Table 3: Hyperparameters for the class removal experiments in Fig. 3(a) and
Fig. IIdd) B, E
and LR denote batch size, training epochs and learning-rates. The superscripts and
VC indicate
hyperparameters for training on all data and warmstarted Jeav--ne-class-ourr retraiinn respectively. Lm is the minimum learning-rate of the cosine scheduler.
1.3 Details of "Predicting the effect of class removal on generalization"
For the FMNIST experiment in Fig. 3(a) we the MLP (32, 16) and LeNet5 models. For the MNIST experiment in Fig. IIdd) we use the MLP (500, 300) and LeNet5 models. The hyperparam- eters are given in Table 3] The MLP MNIST has training accuracy of 99.9% and test accuracy of 98.4%. When using LeNet5, the training and test accuracies are 99.2% and 99.1%. On FMNIST, the LeNet5 has accuracy of 95.0% the training set, and accuracy of 91.2% the test set. On the same dataset, the MLP has a training accuracy of 89.9% and a test accuracy of 86.2%. For all models,
a regularization parameter of 100 and batch size of 256. The leave-one-class-ou training is run for 1000 epochs and the rest of the training setup is same as the previous experiment.
L.4 Details of "Estimating the leave-one-out cross-validation curves for hyperparameter tuning"
The details of the training setup are in Table 2 Fig. is the same Fig. but additionally shows the test errors. For visualization purposes, each plot uses a moving average of the plotted lines with smoothing window. Other training details similar to previous experiments. All models
22

---

0.21 Test NLL
188
60%
LOO-CV
0.5
25%
Test error
Test error
50%
0.1
1.2
40%
0.3
10
10+
10-
10
10
10
10
10
10
10
5
5
5
(a) MNIST, MLP
(b) FMNIST, LeNetS
CIFARIO. CNN
Figure 7: Leave-one-out estimation with sensitivities obtained from MPE (Train-LOO--MP))
can accurately estimate the LOO-CV curve for predicting generalization and tuning of the L2- regularization parameter MNIST, FMNIST and CIFAR-10.
trained from scratch where we use Adam for FMNIST, Adam [6 for CIFARIO, and SGD with momentum parameter of 0.9 for MNIST. We use cosine learning-rate scheduler to anneal the learning-rate. The other hyperparameters are similar to the settings the models trained on data from the leave-one-out experiments in Table 2, except for the number of epochs for CIFAR10 where we train for 150 epochs. Similarly App. I.2, we use a Cronecker-factoreee Laplace approximation for variance computation and do not employ data augmentation during training.
Dataset
Model
Number of ós
Range
Smoothing window
MNIST FMNIST
MLP (500, 300)
96
10
103
3
LeNet5
96
10
103
CIFAR1O
CNN
30
10 10a
3
Table 4: Experimental settings for Fig.
1,5 Details of "Predicting generalization during the training"
Details of the training setup: The experimental details, including test accuracies the end of training, are listed in Table 5] We use a grid search to determine the regularization parameter 6. The learning-rate rate is decayed according
cosine schedule. For diagonal-GGN-LON and K-FAC-LOO, we use the SGD optimizer with an exception on the FMNIST dataset where we use the AdamW optimizer (36). In that experiment,
weight decay factor of 5/N replacing the explicit T.2- regularization term in the loss in Eq. The regularizer R()) is set to zero. We do not use training data augmentation. For all plots, the L00-estimate is evaluated periodically during the training, which is indicated with markers.
Additional details on hyperparameters of iBLR are as follows, where he is the initialization of the Hessian:
MNIST, MLP (32, 16): ho 0.1
MNIST, Le ho 0.1
FMNIST, LeNet5: fn 0.1
CIFARIO, CNN: ho = 0.05
CIFAR10, ResNet20: ho 0.01
We set 31 = 0.9 and B3 = 0.99999 in all of those experiments. The magnitude of the prediction variance can depend on hus which therefore influence the magnitude of the sensitivities that are perturbing the function outputs in the LOO estimate of Eq. 16 We choose hy on a grid four values [0.01, 0.05, 0.1, 0.5] obtain sensitivities that result in good prediction of generalization performance.
Additional Results: In Fig. 8) we show additional results for MNIST and CIFARIO that are not included the main text. For MNIST, we evaluate both on the MLP (32, 16) model and LeNet5 architecture. For the additional CIFAR results,, the CNN. In Fig. 9 we include additional
23

---

Dataset
Model
Method
LR
Lm
B
5
Test acc.
iBLR
10-2
10-4
256
80
95.6%
MNIST
MLP (32, 16)
diag.-GGo tig--GGN-LOO
10-3
10-4
256
80
95.8%
K-FAC-LOO
10-3
10-4
256
80
95.8%
iBLR
10-
10
256
60
97.5%
MNIST
LeNet5
diag.-Gor -oggLLOG-LOO
10
10
256
60
97.4%
K-FAC-LOO
10
10
256
60
97.4%
iBLR
10
256
60
90.7%
FMNIST
LeNet5
diag. -GGN-LOO
10-2
10
256
60
91.0%
K-FAC-LOO
10 -
10-4
256
60
91.0%
iBLR
10
10
512
250
81.0%
CIFARIO
CNN
diag.-Gre -GGN-LO
10-1
512
250
75.4%
K-FAC-LOO
10-1
512
250
73.6%
CIFARIO
ResNer-20
iBLR
2 * 10
50
10
83.4%
Table 5: Experimental settings for predicting generalization during the training in Fig. I(b) Fig. and Fig. 8 B and E' denote the batch-size and training epochs, respectively. LR and L the cosine scheduler. 5 is the regularization parameter. The
the start and end learning-rates specification in brackets in the third column indicates the method for computing sensitivities. We use either iBLR or SGD with diagonal GGN (diag.GGN) or K-FAC.
SGD & DiGgonal-GGN-LLO
SGD & K-FAC-LOO
IBLR & LOO
Test NLL LOD-CV
MLP, MNIST
1.4
1.4
1.4
0.8
0.8
0.8
0.2
0.2
0.2
100
25
50
75
100
75
100
LeNet5, MNIST
1.6
1.6.
0.81
0.8
0.8
50
100
2.4
CNN, CIFAR10
1.8-
10g
1.6
1.2
0.8
75
150
225
300
75
150
225
300
6
100
200
Epochs
Epochs
Epochs
Figure 8: These plots are similar to Fig. 5 but for different model-data pairs. The three rows corre- spond to MLP on MNIST, LeNet5 on MNIST, and CNN on CIFAR 10, respectively. The trends are almost same as those discussed in the main text.
experiment where the model overfits. The K-FAC-LOO estimate deteriorates in this case, we can still use the LOO diagnostic for detecting overfitting and stopping criterion. We train

---

Test NLL
0.8 - LOO-CV
0.8
25 50
100
25
75
100
Epochs
Epechs
(a) -GO-LOO
(b) K-FAC-LOO
Figure 9: Additional results for training with Adam W where we observe overfitting. We see that K-FAC-LOO deteriorates when the model start overfit. Both the LOO measures can still be useful tools for diagnosing overfitting. Details of training setup are given in Table
LeNetS, FMNIST
(32, 16), MNIST
LoNets, MNIST
CNN,
NLL
0.5
LO0-CV
0.2
2.4
Betch size 0
0.4
0.2
0.2
1.6
0.2
0.1
3.2
0.2
0.0
0.8
25
50
75
100
25
50
75
100
25
50
75
100
25
50
75
100
0.3
2.4
Betch size 32
0.4
0.2
2.0
0.2
0.3
0.1
1.2
0.2
0.0
0.8
25
50
100
100
75
100
25
50
75
100
Epochs
Epochs
Eporhs
Eporhs
Figure 10: LOO-CV estimates with Adam using the measure suggested in Table The two rows correspond to a batch size of 8 and a batch size of 32, respectively. A smaller batchsize generally decreases the gap between the test NLL and the estimate. Details of the training setup are given in Table 7
a LeNet5 on FMNIST with AdamW and predict generalization. The trend of the estimated NL.I.
matches the trend of the test NLL in the course of training.
In Fig. 10 we include further results for sensitivity estimation with the Adam optimizer. We use the following update
r. + -,r,-1 + 31) 8: < :28: + (1 - 32) (g, g.). 0, 0. 0.-1 pri/(V/. e),
where g, is the minibatch gradient, 31 and 32 are coefficients for the rumning averages, is leamiin-rrte,, and a small damping to stabilize. We construct a diagonal matrix S, = diag( (N /s to estimate sensitivity with MPE as suggested in Table I] (N is the number of training examples). Better results are expected by building better estimates of S, as discussed 27 As described in section 3.4 of (77] smaller batch size should improve the estimate, which we also observe in the experiment.
I.6 Details of "evolution of sensitivities during training"
We use the MPE with iBLR for neural network classification on MNIST, FMNIST and CIFAR10, well MPE for logistic regression MNIST. Experiment details are in Table 8
For the experiment Fig. (1(a) we consider Bayesian logistic regression. We set 8 0.1. The Hessian is always positive-defiite due to the convex loss function therefore use the VON algo-
25

---

Dataset
Model
Method
LR
Li
B
Test acc.
diag.. AdamW
10-3
10-3
256
60
88.1%
FMNIST
LeNet5
K-FAC, AdamW
10-3
10-3
256
60
87.6%
Table Experimental settings for predicting generalization during the training in Fig. 9
Dataset
Model
LR
Limin
Test acc. (B 8)
Test acc. (B = 32)
MNIST
MLP (32, 16)
10-3
80
97.3%
97.4%
MNIST
LeNet5
10
60
99. 99.2%
99.2%
FMNIST
LeNet5
10-3
60
91.4%
91.2%
CIFARIO
CNN
10-3
50
75.2%
78.4%
Table 7: Experimental settings for Fig. 10
Sensilivity
High Sensitivity
0.014
Low Sensitivity
High Sensitivity
10
9
7
8 a
2
3
2
3
7 6
+
Estimated Deviation
4
6
6
?
0 &
8
2
2
7
5
8
3
0
2
5
9
2
3
3
9
J
7
5-
5
4
3
@
4
6
0.007
7
8
3
7
7
5th epoch
125th
50th
25th
20th
10th
Epoch
2nd
0.000
Examples
Examples
Low Sensitivity
High Sensitivily
Low Sensitivity
High Sensitivity
(a) MNIST, Bayesian logistic regr.
(b) MNIST, iBLR with MLP
Low Sensitivity
High Sensitivity
0.12
0.11
5
2
Estimated Deviation
LOCO estimation
8
0.06
250th
100th
0.05
20th
1st Epoch
MLP LeNet
0.30
0.02
Examples
2 Test NLL
Low Sensitivity
High Sensilivity
(c) CIFAR-IO, iBLR ResNet-20
(d) Class removal result MNIST
In Panel (a), show the evolution of sensitivities for Bayesian logistic regression on MNIST trained with the VON algorithm. In Panel (b) we use MLP trained with the iBLR optimizer. In Panel (c), we use a ResNet-20 trained with iBLR on CIFAR- 10. Panel (d) shows the class removal result similar to Fig. 3(a) but on MNIST
Figure 11: Additional experiments similar Fig. 3(b)
26

---

Dataset
Model
B
8
E
MNIST
MLP (500, 300)
256
30
100
FMNIST
LeNet5
256
60
100
CIFARIO
ResNet-20
512
35
300
Table 8: Experimental settings for evolution of sensitivities during training in Fig. 3(b) and Fig. 3
rithm given in Eq. 29 We use 125 updates with batch-size 200, reaching a test accuracy of around 91% using the mean m,- We linear learning-rate decay from 0.005 to 0.001 for the mean m and a learning-rate of 10-b for the precision S. The expectations are approximated using samples drawn from the posterior. We plot sensitivities at iteration t 5, 10, 25, 125. For this example, use samples from qr to compute the prediction variance and error (150 samples are used). We sort examples according their sensitivity iteration / 125 and then plot their average sensitivities in 60 groups with 100 examples in each group.
For the experiments in Fig. 3(b) Fig. 11(b) and Fig. II(e)
consider neural network models f(O:) on FMNIST, MNIST and CIFARIO. We do not use training data augmentation. For CIFARIO use a ResNet-20. The expectations in the iBLR are approximated using a single sample drawn from the posterior. For prediction, we use the mean m. The test accuracies are 91.3% for FMNIST, 98.5% for MNIST and 80.9% for CIFARIO. We use cosine learning-rate scheduler with initial learning-ran rate of 0.1 and anneal to zero over the course of training. Other experimental details are stated in Table 8 Similar to before, we use sampling evaluate sensitivity (150 samples used).
J Author Contributions Statement
Authors list: Peter Nickl (PN), Lu Xu (LX), Dharmesh Tailor (DT), Thomas Moellenhoff (TM), Mohammad Emtiyaz Khan (MEK)
All co-authors contributed to developing the main idea. MEK and DT first discussed the idea deriv- ing sensitivity measure based on the BLR. MEK derived the MPE and the results in Sec 3 and DT helped in connecting them to influence functions. PN derived the results in 3.3 and came up with the idea predict generalization error with LOO-CV. LX adapted it to class-removal PN wrote the code with help from LX. PN and LX did most of the experiments with some help from TM and reg- ular feedback from everybody. TM did the experiment on the sensitivity evolution during training with some help from PN. All authors were involved in writing and proof-reading of the paper.
K Differences Between Camera-Ready Version and Submitted Version
We made several changes to take the feedback of reviewers into account and improve the paper.
1. The writing and organization of the paper were modified to emphasize the generalization to a wide variety of models and algorithms and the applicability of MPE during training.
2. The presentation was changed in Section 3 to emphasize the focus on the conjugate model. Detailed derivations were pushed to the appendices and more focus was put on big picture ideas. Arbitrary perturbations parts were made explicit. Table 1 was added and more focus was put on training algorithms.
3. We added experiments using leave-one-out estimation to predict generalization on unseen test data during traininig. We also added results to study the evolution of sensitivities during training using MPE with iBLR.
27


Reviews:
[{"review_id": "CRcxsbfDYC", "reviewer": "Reviewer_HWf4", "summary": "The paper presents a generic method, relying on some Bayesian analogy, to perform instance-wise sensitivity analysis of learned models. A generic updating rule and derivative is presented, as well as its different variations on popular models (Neural networks and Gaussian models). One notable use of the proposed sensitivity indices is to estimate the genralisation capabilities of a given model. \n\nExperiments are performed on classical MNIST/FMNIST data sets to confirm that the behaviour of the method is the expected one. ", "questions": "* Bayesian approximation validity: In L92, I found it very strange that one can assume that there is always a proportional link between a Bayesian posterior and the exponential of a Loss function. Sure, the exponential allow to turn the additivity of the loss function into a product form mimicking Bayesian updating, but is it guaranteed that any loss function can be related to a legitimate (proper) prior/likelihood pair in a standard Bayesian framework? Similarly, except for the Gaussian case, what is the quality one can expect from an appriximation using the exponential family? This is a bit hard to figure out, as all examples given in the rest of the paper rest on the (specific) Gaussian case? A good summary of this whole question would be \"How Bayesian (in the sense of satiisfying the axioms and coherence of Bayesian approaches, as expressed by, e.g., De Finetti) actually is the BLR rule?\"\n\n* In echo to my previous question, do we have an idea of how often the premisses of Theorem 2 ($q_\\lambda=p(\\theta|\\mathcal{D})$) are true? Verifying it seems highly non-trivial to me. \n\n* Thanks to the underlying assumptions made, it makes perfect sense to consider that perturbation effects are additive and that samples have independent effects on the model. However, it would seem more reasonable to consider that, in practice, samples do have interactions between them and that the impact on the learned model are not merely additive, hence the need to include some possible dependencies/interactions between the samples. Maybe the authors could clarify a bit the situations where the additivity assumption makes sense? \n\n* While the removal of an observation is perfectly interpretable from the data perspective, I would appreciate some clarification about the $\\epsilon_i$ perturbation. From what I get, this would correspond to weighting the data  in the learning scheme, and see what happens in this case. Is this correct, or would it be more accurate to consider that the data can move within a given neighboorhood within the input space (a perturbation that would probably make more sense from a physical viewpoint, even if I am fine with the weighting interpretation). \n\n* Suggestion: I do not really see the advantage of repeating figures that can be found in some other places in Figure 1, especially as a reader will not have the necessay elements to properly interpret them at this stage. Maybe remove them to better discuss some other points?", "limitations": "See questions about some possible limitations, not especially discussed/mentioned in the paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+: a versatile method to perform sensitivity analysis\n\n+: a strong technical proposal, at least from what I can assess", "weaknesses": "See questions for more detailed comment\n\n-: link with Bayesian approach remains to some extent unclear in the general case. \n\n-: the approach mainly consider instance-wise sensitivity indices, and it is unclear whether this is sufficient in general?  \n\n(minor) -: the paper contains a number of typos, and a final read could be useful to correct them (e.g., L41 \"can estimated\", L63 \"the expressions shows\", L59, \"data as large\", L73, \"such topics as rare\", ...)\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: Bayesian approximation validity: In L92, I found it very strange that one can assume that there is always a proportional link between a Bayesian posterior and the exponential of a Loss function… is it guaranteed that any loss function can be related to a legitimate (proper) prior/likelihood pair in a standard Bayesian framework? \n\nA1: Yes, this is the so-called “generalized” Bayesian framework where any arbitrary loss can be used in place of a likelihood. A short description of this can be found in the Sec 1.2 of the BLR paper [1]. It is well-known in the Bayesian community and several papers exist on this topic; see [2-4]. We will add a short description to the paper. \n\n[1] M.E. Khan, H. Rue. The Bayesian learning rule. arXiv 2107.04562, 2023.\\\n[2] T. Zhang. Theoretical analysis of a class of randomized regularization methods. COLT, 1999.\\\n[3] PAC-Bayesian supervised classification: The thermodynamics of statistical learn-\ning. institute of mathematical statistics lecture notes—monograph series 56. IMS, 2007.\\\n[4] P. G. Bissiri, C. C. Holmes, and S. G. Walker. A general framework for updating belief\ndistributions. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2016 \n\n>Q2: Similarly, except for the Gaussian case, what is the quality one can expect from an approximation using the exponential family? This is a bit hard to figure out, as all examples given in the rest of the paper rest on the (specific) Gaussian case? …. do we have an idea of how often the premises of Theorem 2 ($q_{\\lambda} (\\theta \\lvert D$) are true? Verifying it seems highly non-trivial to me.\n\nA2: We will add a non-Gaussian example for the Beta-Bernoulli Mixture model where the posterior is exact. There are plenty of such cases where the posterior is non-Gaussian and exact. There are no issues with the “quality” of the approximations because they merely reveal the implicit approximations made in the previous non-Bayesian approaches. Our work simply figures out the exact form of the approximations to recover these other approaches from the MPE. \n \n>Q3: How Bayesian actually is the BLR rule?\n\nA3: Yes, the BLR is entirely Bayesian. We encourage the reviewer to refer to the BLR paper, where it is shown that the BLR coincides with the Bayes’ rule for well-known conjugate models and, in others, gives the closest approximation to the posterior according to the KL divergence. For Bayesian models, such as in Bayesian deep learning, this is just variational inference. We will add some text to explain this. \n\n>Q4: Thanks to the underlying assumptions made, it makes perfect sense to consider that perturbation effects are additive and that samples have independent effects on the model. However, it would seem more reasonable to consider that, in practice, samples do have interactions between them and that the impact on the learned model are not merely additive, hence the need to include some possible dependencies/interactions between the samples. Maybe the authors could clarify a bit the situations where the additivity assumption makes sense?\n\nA4: Thanks for the question. We are not sure about which “additive assumption” the reviewer is referring to. In Eq. 6 we make an additive assumption in the “natural-parameter space” but this still takes the interactions into account when estimating effects on the predictors. For example, see Eq. 19 where the covariance matrix (in the first approximation) takes care of the interaction and collinearity between the examples (similarly to the influence function). In Fig. 3a, we show that ignoring the interaction still works on some problems, but considering full covariance is better in general as suggested by Eq. 19.\n\n>Q5: While the removal of an observation is perfectly interpretable from the data perspective, I would appreciate some clarification about the perturbation. From what I get, this would correspond to weighting the data in the learning scheme, and see what happens in this case….\n\nA5: Yes, you are right! For example, we can multiply the loss function of the respective data by $\\epsilon_i$, perturb the label $y_i$, or some other perturbation of this kind.\n\n>Q6: Suggestion: I do not really see the advantage of repeating figures that can be found in some other places in Fig. 1, especially as a reader will not have the necessary elements to properly interpret them at this stage. Maybe remove them to better discuss some other points?\n\nA6: Thanks, we will think about this, and also improve the caption to make it more understandable.\n\n>Q7: the paper contains a number of typos…\n\nA7: Thanks, we have fixed them now."}, {"review_id": "MX4aWImWsi", "reviewer": "Reviewer_WQKj", "summary": "The paper studies the sensitivity of machine learning models to training data. Previously, sensitivity was often studied through empirical investigations which was costly and do not always generalize across models. In this paper, the authors present the memory perturbation equation (MPE), based on the Bayesian learning rule, as a unifying equation to understand sensitivity of generic ML algorithms to training data. The MPE has two features: Sensitivities to examples is estimated by using natural gradients of those examples alone, and examples with larger natural gradients contributes more to the sensitivity. The authors show that the MPE when specialized to Gaussian posteriors, recovers influence functions in linear models and deep learning, and examples with high prediction error and predictions variances are the most influential and the sensitivity is obtained by multiplying the two; The sensitivity can be estimated cheaply whenever natural gradients are cheap to compute; Finally, the authors show empirically that the MPE can be used to accurately estimate generalization performance on image classification tasks.", "questions": "Out of curiosity, can the proposed MPE or part of the proposed perturbation-based formulation be used to perform machine learning data valuation, i.e., to evaluate the importance of groups of data samples towards a machine learning task (e.g., https://bair.berkeley.edu/blog/2019/12/16/data-worth/)", "limitations": "The authors have adequately addressed the limitations in their discussions section. I don’t see any potential negative impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written and easy to follow for non-experts.\n- The proposed MPE formulation is well supported by theoretical foundations based on bayesian learning rule. And according to the authors, the proposed MPE has several nice and intuitive theoretical properties for Gaussian posteriors.\n- The experiments are well designed to show various aspects of the the properties of the proposed sensitivity measure, which is interesting and clear.", "weaknesses": "- I don’t see much discussions on related work or empirical comparisons to state-of-the-art methods\n- The example datasets used in the empirical evaluations seem to be mostly smaller datasets like MNIST and CIFAR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: I don’t see much discussions on related work or empirical comparisons to state-of-the-art methods\n\nA1: Thanks, we will improve this point, but could the reviewer mention some related works they would like us to add? For now, we considered influence function as state-of-the-art and we have new experiments comparing influence functions at iterations of SGD, Adam, AdamW, etc. The experiments clearly show the limitation of existing approaches that do not work well during iterations. See Fig. I in the attached 1-page pdf.\n\n>Q2: The example datasets used in the empirical evaluations seem to be mostly smaller datasets like MNIST and CIFAR.\n\nA2: We agree but this is because our focus is on “unifying existing measures”. Our experiments are essentially validating the theory. We will take experiments on the TinyImageNet dataset into consideration. In the future, we plan to work on large-scale models such as GPT-2.\n\n>Q3: “Out of curiosity, can the proposed MPE or part of the proposed perturbation-based formulation be used to perform machine learning data valuation, i.e., to evaluate the importance of groups of data samples towards a machine learning task (e.g., https://bair.berkeley.edu/blog/2019/12/16/data-worth/)”\n\nA3: Absolutely! We hope to consider such applications in the follow-up study, where we use the framework developed here for larger problems."}, {"review_id": "6SgfPDWCrV", "reviewer": "Reviewer_KnYf", "summary": "In this paper, the authors introduce the Memory Perturbation Equation (MPE), a generalization of sensitivity measures of models that uses the recently proposed Bayesian Learning Rule (BLR) as a foundation. Thanks to its Bayesian foundation, the MPE can be used for used for non-converged models and for non-differentiable loss functions.", "questions": "N/A", "limitations": "A limitation section is missing from the paper, which I think is important to have.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The biggest strength of the paper is the writing. This is an *extremely* well written paper that conveys the idea beautifully. It flows extremely well and is very easy to read and follow along. The generality of the MPE is also mind boggling. This is an extremely general method that I think will be pivotal for deep learning. Lastly, the experiments section did a great job verifying the theory of the method and giving a taste of all of the potential uses for it.", "weaknesses": "While I think the writing is fantastic, I think a small exposition on the BLR would due wonders, especially because the paper cites specific equations form the BLR paper. To make the paper more readable, a small section in the appendix with details relevant to the paper and its experiments would do wonders.\n\nWhile I understand the theory of the method, I have a slight practical disconnect between the experiments from this paper and the BLR. Since Adam naturally arises from the BLR, the posterior variances can be constructed easily and, crucially, the posterior covariance would be diagonal, sidestepping messy matrix inversions. But, from reading the appendix section, it seems like the authors are doing the opposite and are instead getting the Hessian of the loss function (in the appendix the authors write: \"Variance computation requires inversion of matrices. For large problems, we use a Kronecker factored Laplace variance approximation as implemented in the laplace package[5]\"). If this is indeed the case, then I do find this slightly concerning and is a major limitation of the method as computing Hessians are expensive and practically infeasible for modern architectures. Moreover, it doesn't fall in line of the mantra of the paper which is to leverage the BLR to get these sensitivity measure for practically free.  \n\nPlease let me know I have misunderstood what is going on.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: I think a small exposition on the BLR would due wonders, especially because the paper cites specific equations from the BLR paper. To make the paper more readable, a small section in the appendix with details relevant to the paper and its experiments would do wonders.\n\nA1: Thanks for the suggestion. We will add a section on this.\n\n>Q2: I have a slight practical disconnect between the experiments from this paper and the BLR. Since Adam naturally arises from the BLR, the posterior variances can be constructed easily and, crucially, the posterior covariance would be diagonal, sidestepping messy matrix inversions….. it seems like the authors are …..getting the Hessian of the loss function…. I do find this slightly concerning and is a major limitation of the method as computing Hessians are expensive and practically infeasible for modern architectures. Moreover, it doesn't fall in line with the mantra of the paper which is to leverage the BLR to get these sensitivity measure for practically free.\n\nA2: This is a great question and what you said is exactly the idea: the MPE suggests that better estimates of uncertainty give better estimates of sensitivity; see the 1-page PDF on the experiments, where we compare sensitivity at iterations of methods like SGD, Adam, AdamW, iBLR, etc. Previously, we did KFAC only for some experiments where trained networks were used. For iterations, we always use diagonal versions, but we will fix the writing and make the experiments more clear.\n\n>Q3: A limitation section is missing from the paper, which I think is important to have.\n\nA3: We will add a section to the paper."}, {"review_id": "YRgf60INR7", "reviewer": "Reviewer_YYDA", "summary": "This paper studies the problem of the model’s sensitivity to its training data (e.g., the counterfactual of how the model's performance will change if trained without certain data), commonly referred to as the \"data influence\" problem. This paper presents the \"memory perturbation equation (MPE)\" to study the model’s sensitivity to such perturbations and uses Bayesian learning rule (BLR) approximated using an exponential family distribution. Then, the BLR can be used to estimate the deviation caused by the removal of a group of data.\n\nThe paper shows that MPE with Gaussian posterior recovers the celebrated Influence Functions (INF) in both linear and nonlinear cases, and INF can be considered as a special case of the MPE. The work also provides a variety of empirical results on MNIST to CIFAR-10 that shows the estimated sensitivity highly correlates with the actual deviation that would be caused by removing the data and thus can be used as its predictions.", "questions": "I was wondering about the approximation error for using exponential family distributions or Gaussian priors. It would be nice if the paper can provide some discussions on this to help better understanding.\n\nWhat is the computational overhead of the proposed method, in terms of time complexity and memory demand?", "limitations": "The empirical results are relatively weak. The computational demand and its scalability are unclear. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is an interesting addition to the research line on \"data influence\" problems. The paper is well-written. The conceptual development of this paper is clear and smooth. The methodology development and its derivations are solid and the paper also provides insightful remarks supporting the narrative. The method presented in the paper is general and can be potentially applied to a variety of work. Experiment results are nicely presented, clear and interesting.", "weaknesses": "I am listing some minor issues that may be improved. \n\nIn this work, despite strong correlations to the Influence Function have been shown, the comparison to data influence methods in general isn't comprehensive. There are often works talking about recovering linear influence function or using Taylor approximation to extend to nonlinear cases. It would be nice to see how it relates to or compares to broader works, such as [1] or TracIn [2], just to name a few.\n[1] Repairing Neural Networks by Leaving the Right Past Behind. NeurIPS 2022.\n[2] Estimating training data influence by tracing gradient descent. NeurIPS 2020.\n\nThe empirical results of the proposed approach seem isn't especially strong. As we can see, the correlation between prediction and the actual counterfactual deteriorates quickly as the model becomes bigger. It seems quite well for MNIST/MLP, but less satisfactory for LeNet/FMNIST and CNN/CIFAR-10. I appreciate the honesty of authors that show these results in a straightforward manner such that the reader can directly see the real capability of these methods. Because of that, I would think the relatively weak empirical results do not pose a major compromise to the contribution of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: Despite strong correlations to the Influence Function have been shown, the comparison to data influence methods in general isn't comprehensive…. It would be nice to see how it relates to or compares to broader works, such as [1] or TracIn [2]..\n\nA1: This is a good point. The MPE unifies many such approaches (e.g., those mentioned in line 75-77) by essentially choosing an appropriate posterior form and an approximation to the natural-gradient (these same approximations are also made in the BLR). Currently, we only give detailed derivations for linear regression and neural networks, but we will expand and rewrite these parts to explain the unification of other approaches. To summarize:\n- methods that use Hessians (Koh and Liang 2017, Hara et al. 2019) are obtained by using a Gaussian with an unknown “full” covariance; also see the note in line 171. \n- deep learning optimizers are obtained by using a Gaussian with an unknown “diagonal” covariance. \n- methods that use prediction error or the gradient (see the references in line 76) can often be obtained by using a Gaussian with unknown mean but a fixed known covariance. \n\nWe will expand the paper to explain these connections in detail. We will also add the references you suggested.\n\n>Q2: The empirical results of the proposed approach seem isn't especially strong. As we can see, the correlation between prediction and the actual counterfactual deteriorates quickly as the model becomes bigger. It seems quite well for MNIST/MLP, but less satisfactory for LeNet/FMNIST and CNN/CIFAR-10. I appreciate the honesty of authors that show these results in a straightforward manner such that the reader can directly see the real capability of these methods. Because of that, I would think the relatively weak empirical results do not pose a major compromise to the contribution of this work.\n\nA2: We stress that our measures can work on bigger models as well; see Fig. IIa in the 1-page PDF where we show on ResNet-20 (270K parameters) a perfect match between true and estimated generalization error. Also, the MLP used for MNIST in Fig. 2a has 545K parameters. We have several such experiments now. \nThe reason behind the less satisfactory results in Fig. 2b and 2c is due to a suboptimal training to produce the ground-truth in the x-axis. The ground truth requires retraining with individual examples removed. We will fix this in the next version of the paper. We do not observe these problems in other experiments (e.g., when predicting generalization error as shown in Fig. IIa)\n\n>Q3: I was wondering about the approximation error for using exponential family distributions or Gaussian priors. It would be nice if the paper can provide some discussions on this to help better understand.\n\nA3: We mention this briefly in line 183 but we will expand this. As mentioned in our response to Q1, by making an appropriate exponential-family approximation we can recover different types of measures. So the quality of approximation affects the quality of the sensitivity measure. See the results shown in Fig. I of the 1-page PDF. \n\n>Q4: “What is the computational overhead of the proposed method, in terms of time complexity and memory demand?”\n\nA4: For diagonal Gaussian approximations, we get deep-learning optimizers that estimate weight-space variances for free (see Sec. 4 of the BLR paper [1]). These can be turned into sensitivity estimates with almost no additional overhead, for instance, using a few Jacobian vector products; see the results shown in Fig. I of the 1-page PDF. In general, as mentioned in line 184, the computational overhead depends on the chosen posterior approximations. \n\n[1] M.E. Khan, H. Rue. The Bayesian learning rule. arXiv 2107.04562, 2023.\n"}, {"review_id": "GJEAa4HDzL", "reviewer": "Reviewer_fdmt", "summary": "This paper proposes measuring sensitivity to data in some problems in machine learning through what they refer to as the “memory perturbation equation” (MPE), derived using the Bayesian learning rule. They argue that sensitivity properties of machine learning models are not as well understood as they could be in the literature, and therefore propose a remedy to this issue that generalizes some prior approaches. Much of the paper is about justifying the equation and showing that some prior works are special cases. There is also an experimental section that provides some empirical validation of some equations.", "questions": "Some questions/comments follow:\n\n- For the title, I don’t think “model’s” is the most suitable choice of term. I suggest using either “model” or “models’”.\n\n- “MPE” also stands for most probable explanation in Bayesian modeling, so this could be a point of confusion for some, without context.\n\n- I’m not sure how the word “memory” is suitable for what the authors intend in this work. This is what is written in Section 1: “These highly sensitive examples can be seen as those characterizing the model’s memory; the model is highly sensitive to them and perturbing them can make the model forget its essential knowledge”. Perhaps the authors could explain and justify their choice of term? It may help to connect any other work that they deem to be relevant or inspirational.\n\n- For Fig 1, what is the dataset on which a) and b) panels are based on? Are these all for FMNIST?\n\n- What is the relation between output function f_i(.) and the terms in equation 1? I don’t think this is ever specified. Is f_i the same as l_i?\n\n- Several of the equations (such as those in Section 3) are stated with pointers to prior work but without clear derivation. I understand that there are space limitations, but I had trouble following the correctness of the equations.\n\n- There is a claim in line 207 about how the proposed approach is more principled than some prior work – as someone not familiar with the field, I did not observe much justification for this claim, or perhaps just did not understand it clearly.\n\n- “Sharpness” is mentioned in line 227 but never defined. There are other such terms that don't get enough explanation.\n\n- There are typos, grammatical errors or other such issues in at least the following lines: 39, 41, 59, 61, 63, 68, 110, 113, 124, 161, 221, 236, 244, 249, 268, etc. Note that many of the early typos are due to the incorrect use of verbs for single vs. plural nouns. I suggest the authors carefully review the paper and fix these errors.\n", "limitations": "Limitations are not mentioned in enough detail.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Although I am not familiar with this general area of research, which seems to be related to influence functions in machine learning, I found the paper interesting and novel. I also found the topic to be highly relevant for NeurIPS and an important one for machine learning in general. The fact that the approach generalizes some prior approaches in a non-trivial way is powerful.", "weaknesses": "While I’m generally supportive of this paper, I had a hard time following many of the details in this paper and cannot verify aspects of the approach. This is partly because of my lack of familiarity with the subject, but also because I think the authors have not provided enough background and explanation for a reader with little know-how around related topics. Also, I think the presentation can be improved significantly – please see my detailed questions/comments for some suggestions. I will rely heavily on more knowledgeable reviewers to provide a more thorough assessment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: For the title, I don’t think “model’s” is the most suitable choice of term. I suggest using either “model” or “models’”....“MPE” also stands for most probable explanation in Bayesian modeling, so this could be a point of confusion for some, without context.\n\nA1: Thanks for the suggestions. We will try to avoid the confusion.\n\n>Q2: I’m not sure how the word “memory” is suitable for what the authors intend in this work… perhaps the authors could explain and justify their choice of term? It may help to connect any other work that they deem to be relevant or inspirational.\n\nA2: We use the word “memory” due to a connection to Bayesian methods in psychology where similar concepts are used, e.g., see “Bayesian sets” by Ghahramani and Heller, 2005, where log-ratios of posteriors are used to retrieve “relevant” examples. There is work in psychology (e.g., representativeness) to connect these ideas to human memory. We did not go into detail about this, but hope to write about this connection in a future study.\n\n>Q3: For Fig 1, what is the dataset on which a) and b) panels are based on? Are these all for FMNIST?\n\nA3: Panel b) is for MNIST and c) is for FMNIST, while Panel a) is just an illustration. We will fix the caption to clarify this.\n\n>Q4: What is the relation between output function f_i(.) and the terms in equation 1? I don’t think this is ever specified. Is f_i the same as l_i?\n\nA4: $f_i$ is the model’s output, while $\\ell_i$ is the loss function. Line 60 shows an example for linear regression and the mean-squared error loss, where $f_i = x_i^{T} \\theta$.\n\n>Q5: Several of the equations (such as those in Section 3) are stated with pointers to prior work but without clear derivation. I understand that there are space limitations, but I had trouble following the correctness of the equations.\n\nA5: For the final version, we add derivations to the appendix to make the work more self-contained.\n \n>Q6: There is a claim in line 207 about how the proposed approach is more principled than some prior work – as someone not familiar with the field, I did not observe much justification for this claim, or perhaps just did not understand it clearly.\n\nA6: We will expand this part. Essentially, the previous work uses an ad-hoc smoothing mechanism to make the loss differentiable, while in our work smoothing is naturally done with the posterior distribution (by using the expectation before taking the derivative as shown in line 206).\n\n>Q7: “Sharpness” is mentioned in line 227 but never defined. There are other such terms that don't get enough explanation.\n\nA7: By sharpness we mean the measures studied in the cited paper by Jiang et al. ([11] in the submitted draft). Sharpness of a local minimum captures the sensitivity of the empirical risk to perturbations in model parameters. We will clarify the confusion for the final version. Please let us know the other terms that cause confusion, so we can add explanations.   \n\n>Q8: Limitations are not mentioned in enough detail.\n\nA8: We will add this. The major limitation is that better sensitivity may require better variances which may not always be computationally feasible.\n"}]

Author rebuttal:
We appreciate the feedback provided by all reviewers. The main weakness seems to be that \
(1) the relevant background and related work can be improved; and\
(2) the experimental results are weak at times and not on large models. 

For issue 1, we believe it can easily be fixed and we have given relevant responses for those. For issue 2, we provided additional results in the 1-page PDF. We also include an experiment on ResNet-20 (270K parameters). The experiments support our main message that (1) better estimates of uncertainty give better estimates of sensitivity, and (2) sensitivity can be estimated well during training. We will further improve the writing and presentation of the paper to take the reviewers' suggestions into account.

Meta-review: The paper was reviewed by 5 knowledgeable reviewers, all of whom recommended acceptance of the paper. Initially raised concerns by the reviewers regarding unclarities, related work, and experimental evaluation were clearly addressed in the authors' rebuttal. Hence, in line with the reviewers' recommendations, I am recommending acceptance of the paper. The authors are encouraged to include the newly presented material in the camera-ready version of their paper and, based on the discussions with the reviewers, improve the clarity of their paper in relevant sections.
Decision: Accept (poster)