Understanding Influence Functions and Datamodels via Harmonic Analysis
Authors: Nikunj Saunshi
Arushi Gupta
Mark Braverman
Sanjeev Arora
Venue: ICLR 2023 poster (2023)
Keywords: theory
datamodels
influence functions
fourier analysis
harmonic analysis

Abstract: Influence functions estimate effect of individual data points on predictions of the model on test data and were adapted to deep learning in \cite{koh2017understanding}. They have been used for detecting data poisoning, detecting helpful and harmful examples, influence of groups of datapoints, etc. Recently, \cite{ilyas2022datamodels} introduced a linear regression method they termed {\em datamodels} to predict the effect of training points on outputs on test data. The current paper seeks to provide a better theoretical understanding of such interesting empirical phenomena. The primary tool is harmonic analysis and the idea of {\em noise stability}. Contributions include: (a) Exact characterization of the learnt datamodel in terms of Fourier coefficients. (b) An efficient method to estimate the residual error and quality of the optimum linear datamodel without having to train the datamodel. (c) New insights into when influences of groups of datapoints may or may not add up linearly.

Published as a conference paper at ICLR 2023
UNDERSTANDING INFLUENCE FUNCTIONS AND DATA- MODELS VIA HARMONIC ANALYSIS
Nikunj Saunshi, Arushi Gupta, Mark Braverman, Sanjeev Arora Department of Computer Science, Princeton University {nsaunshi, arushig, mbraverm, exora]ecs.prinnetoo..
ABSTRACT
Influence functions estimate effect of individual data points on predictions of the model on test data and were adapted to deep learning in Koh & Liang (2017).
They have been used for detecting data poisoning, detecting helpful and harmful examples, influence of groups of datapoints, etc. Recently, [lyas et al. (2022) introduced a linear regression method they termed datamodels to predict the effect of training points outputs test data. The current paper seeks to provide a better theoretical understanding of such interesting empirical phenomena. The primary tool is harmonic analysis and the idea of noise stability. Contributions include: (a) Exact characterization of the learnt datamodel in terms of Fourier co- efficients. (b) An efficient method to estimate the residual error and quality of the optimum linear datamodel without having to train the datamodel.
(c) New insights into when influences of groups of datapoints may or may not add up linearly.
INTRODUCTION
It is often of great interest quantify how the presence absence of particular training data point affects the trained model's performance on test data points. Influence functions is classical idea for this (Jaeckel 1972 Hampell 1974 Cook 1977) that has recently been adapted modern deep models and large datasets Koh & Liang 2017). Influence functions have been applied to explain predictions and produce confidence intervals (Schulam & Saria, 2019), investigate model bias (Brunet et al. | 2019 WWng et al. 2019), estimate Shapley values (Jia et al. 2019) Ghorbani & Zou, 2019). improve human trust (Zhou et al. 2019), and craft data poisoning attacks (Koh et al. 2019).
Influence actually has different formalizations. The classic calculus-based estimate (henceforth re- ferred as continuous influence) involves conceptualizing training loss as weighted sum over training datapoints, where the weighting of particular datapoint can be varied infinitesimally. Using gradient and Hessian one obtains an expression for the rate of change in test error (or other functions) of z' with respect to (infinitesimal) changes to weighting of Though the estimate is derived only for infinitesimal change to the weighting of a in the training set, in practice has been employed also reasonable estimate for the discrete notion of influence, which is the effect of completely adding/removing the data point from the training dataset (Koh & Liang (017). Infor- mally speaking, this discrete influence defined as f(S U {i)) -(S) where f is some function of the test points, S is a training dataset and i is the index of a training point. (This can be noisy, so several papers use expected influence of by taking the expectation over random choice of S of certain size; see /Section 2) Koh & Liang (0117) as well as subsequent papers have used continuous influence to estimate the effect of decidedly non-infinitesimal changes to the dataset, such chang- ing the training set by adding or deleting entire groups of datapoints (Koh et al.) 2019). Recently Bae al. (2022) show mathematical reasons why this is not well-founded, and give clearer explanation (and alternative implementation) of Koh-Liang style estimators.
Yet another idea related to influence functions is linear datamodels in Ilyas et al. (2022). By training many models on subsets of fraction of datapoints in the training set, the authors show that some interesting measures of test error (defined using logit values) behave as follows: the measure f()) is appo-appro binary vector denoting a sample of p fraction of training datapoints, with x; = 1 indicating presence of i-th training point and x; -1 denoting absence. The coefficients 0, estimated via lasso
(sparse) linear expression 6g + Σ, 0,22, where is

---

Published as a conference paper at ICLR 2023
regression. The surprise here is that f(z) which is the result of deep learning dataset z z-iss well-apprrximmted by 8, + Σ, 0,0, The authors note that the 8 's can be viewed as heuristic estimates for the discrete influence of the ith datapoint.
The current paper seeks to provide better theoretical understanding of menteemeet phenomena concerning discrete influence functions. At first sight this quest appears difficult. The calculus definition of influence functions (which as mentioned is also used in practice to estimate the discrete notions of influence) involves Hessians and gradients evaluated on the trained net, and thus one imagines that any explanation for properties of influence functions must await better mathematical understanding of datasets, net architectures, and training algorithms.
Surprisingly, we show that the explanation for many observed properties turns out to be fairly generic. Our chief technical tool is harmonic analysis, and especially theory of noise stability of functions (see O'Doonell (2014) for an excellent survey).
1.1 OUR CONCEPTUAL FRAMEWORK (DISCRETE INFLUENCE)
Training data points are numbered through N, but the model being trained on a random subset of data points, where each data point is included independently in the subset with probability p. (This is precisely the setting in linear datamodels.) For notational ease and consistency with harmonic analysis, we denote this subset by E {-1,+1Ja where +1 means the corresponding data point was included. We are interested in some quantity f(x) associated with the trained model on one more test data points. Note f is probabilistic function of x due to stochasticity in deep net training - SGD, dropout, data augmentation etc. but one can average over the stochastic choices and think of f as deterministic function f: [+1] + R. (In practice, this means we estimate f (ar) by repeating the training on 2, say, 10 to 50 times.)
This scenario close to classical study of boolean functions via harmonic analysis, except our func- tion is real-valued. Using those tools we provide the following new mathematical understanding:
1. We give reasons for existence of datamodels of llyas et al. (2022). the phenomenon that functions related to test eгror are well-approximable by linear function Uo + >, 0,z;, See Section 3.]
[Section 2 gives exact characterizations of the 0,'s for data models with/without regularization. (Earlier, Ilyas et al. (2022) noted this for a special case: 0.5, lg regularization)
3. Using our framework, we give a new algorithm to estimate the degree to which a test function f well-approximated by a linear datamodel, without having to train the datamodel per se. See Section 3.2] where our method needs only ((L/E") samples instead of O(N/E)..
We study group influence, which quantifies the effect of adding or deleting a set T of datapoints to x. [lyas al. (2022) note that this can often be well-approximated by linearly adding the indi- vidual influences of points in I. Section clariiies simple settings where linearity would fail, by factor exponentially large in [7], and also discusses potential reasons for the observed linearity.
1.2 OTHER RELATED WORK
Narasimhan et al. (015)) investigate when influence is PAC learnable. Basu et al. (202)) use second order influence functions and find they make better predictions than first order influence functions. Cohen et al. 22020) use influence functions to detect adversarial examples. Kong et al. (2021) propose an influence based re-labeling function that can relabel harmful examples to improve gen- eralization instead of just discarding them. Zhang & Zhang (202)) use Neural Tangent Kernels to understand influence functions rigorously for highly overparametrized nets.
Pruthi et al. (2020) give another notion of influence by tracing the effect of data points on the loss throughout gradient descent. [Chnn et al. (020) define multi-stage influence functions to trace influ- ence all the way back to pre-training to find which samples were most helpful during pre-training. Basu et al. (222I) find that influence functions are fragile, in the sense that the quality of influence estimates depend the architecture and training procedure. Alaa & Van Der Schaar (2020) use higher order influence functions to characterize uncertainty in a jack-knife estimate. Teso et al. (2021) introduce Cincer, which uses influence functions to identify suspicious pairs of examples for interactive label cleaning. Rahaman et al. (2019) use harmonic analysis to decompose a neural network into a piecewise linear Fourier series, thus finding that neural networks exhibit spectral bias.
2

---

Published as a conference paper at ICLR 2023
Other instance based interpretability techniques include Representer Point Selection Yeh et al.
2018 Grad-Cos (Charpiat et al. 2019), Grad-dot (Hanawa et al. 2020), MMD-Critic Kim et al. and unconditional factual explanations (Wachter al. 2017).
2016
Variants on influence functions have also been proposed. including those using Fisher kernels
(Khanna et al. 2019). tricks for faster and more scalable inference (Guo al., 2021 Schioppa
et al. 2022). and identifying relevant training samples with relative influence (Barshan et al. 2020).
Discrete influence played prominent role the surprising discovery of long tail phenomenon in
Feldman (020): [eldman & Zhang (202)): the experimental finding that in large datasets like Im-
ageNet, a significant fraction of training points are atypical, in the sense that the model does not easily learn to classify them correctly if the point is removed from the training set.
2 HARMONIC ANALYSIS, INFLUENCE FUNCTIONS AND DATAMODELS
In this section we introduce notations for the standard harmonic analysis for functions on the hyper- cube (ODDonnell 2 and establish connections between the corresponding fourier coefficients, discrete influence of data points and linear datamodels from
Ilyas et al. (0022)
2.1 PRELIMINARIES: HARMONIC ANALYSIS
In the conceptual framework of Section I.1 let [M] (1. N). Viewing f: {+1} R as a vector in R²* for any distribution D on { {=1 the set of all such functions can be treated as vector space with inner product defined as (f, as || / [E>D((<>) Harmonic analysis involves identifying special orthonormal bases for this vector space. We are interested in f's values at or near p-biased points x E {=1] where is viewed as a random variable whose each coordinate is independently set to +1 with probability p. We denote this distribution as Bp. Properties of in this setting are best studied using the orthonormal basis functions {Øs S C [N]] defined as (s(x)) = Ilies ("==), where = 2p and 0² 4p(1 - p) are the mean and variance of each coordinate of x. Orthonormality implies that E [ [z)] when S + 0 and (Øs, Φs 1s, sr. Then every f: [N] can be expressed
(x))([(x)g(()) leading to norm defined
as f = Σ SggNv] Jsés. Our discussion will often refer to Is's as "Fourier" coefficients of f, when the orthonormal basis is clear from context. This also implies Parseval's identity: Es P3 = || [I
For any vector Rd,, we denote 2; denote its i-th coordinate (with l-indexing). For matrix A E Ra A.. E R" and A.j E IRd denote its i-th row and j-th column respectively. We use to denote Euclidean norm when not specified.
2.2 INFLUENCE FUNCTIONS
We use the notion of influence of a single point from Feldman & Zhang (220);; Ilyas et al. 2022)
Influence of the i-th coordinate on f at x is defined as (f()) = f (-1) f(r ( where is sampled as p-biased training set and æ/i-41 is x with the i-th coordinate set 1.
Proposition 2.1 (Individual influence). The "leave-one-ow" influences satisfy the following:
2 Σ (sosyn(() Inf.(f) = Ex [nf[())))((==)]] - 931
[nf(((()))
(1)
Thus the 1egree-1 Fourier coefficients are directly related to average influence of individual points. Similar results can be shown for other definition of single point influence: E,, [f(z) f(x and E, [=( - (x)) are equal to p [ff,( and (1 - p) [nf respectively. The proof of this follows by observing that [=]((<=;--)) - [(] = Essi fs (Lا =ساد Φs (x). The
only term that is not zero in expectation the one for S = (1). thus proving the result. Section
deals with the influence of add or deleting larger subsets of points.
Continuous vs Discrete Influence Koh & Liang (017) utilize a continuous notion influence: train model using dataset æ E [+1]2" and then treat the i-th coordinate of x as continuous variable Ty. Compute dz. I; using gradients and Hessians of the loss at end of training.
3

---

Published as a conference paper at ICLR 2023
This is called the continuous inffuence of the i-th datapoint on f. As mentioned in Section | in several other contexts one uses the discrete influence [ which has a better connection to harmonic analysis. While experiments in Koh & Liang (2017) suggest that continuous influence closely tracks the discrete influence in linear models, Bae et al. (2022) show that this breaks in deep learning settings. For the rest of the paper will use discrete influences.
2.3 LINEAR DATAMODELS FROM A HARMONIC ANALYSIS LENS
Next we turn to the phenomenon llyas et al. 2022) that a function f(x) related to average test error" (where x is the training set) offen turns out to be approximable by linear function 0g + Σ, O,T,, where 전 E {0, 11.² is the binary version of I E [=1]A. It is important to note that this approximation (when exists) holds only in a least squares sense, meaning that the following is small: E2 (x)(() 8o- Σ, 0,5;) where the expectation is over p-biased z.
The authors suggest that 0g can be seen as an estimate of the average discrete influence of variable i. While this is intuitive, they do not give general proof (their Lemma 2 proves it for p 1/2 with l2 regularization). The following result exactly characterizes the solutions for arbitrary p and with both & and & regularization.
Theorem 2.2 (Characterizing solutions linear datamodels). Denote the quality of a linear data- model 0 E R N++ on the p-biased distribution over training sets Bp by
(s(6)-00-
N
2
R(0)= = BE-BB
- -
Σ
0
(2)
where T E 10,11 13 is the binary version for any E {=1JA. Then for 2p and
/4p(1- the following are true about the optimal datamodels with and without regularization:
(a) The unregularized minimizer 0+ -arg min R(0) satisfies
0f _ [()) 0 = Te
(1+1)
Σ9.
03
2
Furthermore the residual error is the sum of all Fourier coefficients of order 2 or higher.
R(0*) = B22= =
Σ
(4)
SCINT
(b) The minimizer with l2 regularization 0" (2,, = arg min {R(0) + Al|O |2] -1
satisfies
(A(,,)2)
2
(1
1
41 a²
Jwy
(5)
(c) The minimizer with regularization 0 (>,, arg min (R(0) + Al01.N11i3 satisfies
8* (), 2 (fo- - )/o).)=
2
sign (f(z) (Foo) -2/0) 3//o)
(6)
where 24 = =1220 is the standard ReLU operation.
This result shows that the optimal linear datamodel with various regularization schemes, for any p E (0, 1) are directly related to the first order Fourier coefficients at p. Given that the average dis- crete influences, from Eqquatin (I) are also the first order coefficients, this result directly establishes a connection between datamodels and influences. Result (c) suggests that L regularization has the effect of clipping the Fourier coefficients such that those with small magnitude
set to O, thus al) gives a simple expression for the resid-
couraging sparse datamodels. Furthermore, ual of the best linear fit which we utilize for our efficient residual estimation procedure in inSeeciion 3.2
The proof of the full result is presented in Appendix B.I however we present proof sketch of the result aa) to highlight the role of the Fourier basis and coefficients.
'The average is not over test error but over the difference hetween the correct label logits and the top logit among the rest, at the output layer of the deep
4

---

Published as a conference paper at ICLR 2023
Proof sketch for Theorem 2.2(a) a)) Since [Øs}scIN) is an orthonormal basis for the inner product
space with (,,)),
E [f())(())) we can rewrite R()) follows
z~B,
R(0)- - Bu-B,
- (((x) -00) (1())-00-
- Octii - -EEBB [((x) - 00 --0r0(s((())
= 1 - Σ 0
2
where || 1118, = (:,
18p
where 0, 7/2 0, and 0g Og + (1+1)/2 E, Due to the orthonormality of SC[]] the minimizer H will lead to projection of f onto the span of {ésh which gives 0g f(0 and thus 0, = Ft3. Furthermore the residual the norm of the projection of f onto the orthogonal subspace span (f0s (1822))22) which is precisely Σ E1112 fs-
3 NOISE STABILITY AND QUALITY OF LINEAR DATAMODELS
Theorem 2.2 characterizes that best linear datamodel from llyas al. (2022) for any the test function. The unanswered question is: Why does this error) for the actual function f? A priori, one expects fzz), the result of deep learning on x, to be a complicated function. In this section we use the idea of noise stability to provide an intuitive explanation. Furthermore we show how noise stability can be leveraged for efficient estimation of the quality of fit of linear datamodels, without having learn the datamodel (which, as noted in [[lyas al. 2022), requires training large number of nets corresponding to random training sets x).
be good surrogate (i.e. with low residual
Noise stability. Suppose x is p-biased as above. We define a p-correlated r.v. as follows: Definition 3.1 (p-correlated). For x E [=1] N we say a r.V. x' is p-correlated to x if it is sampled as follows: If x; then x x; w.p. (1 () p). If x; -1, x -; w.p.
p)p.
Note that 2 = w.p. p(1 (1 (1 p1pp so both and x' represent training datsets of expected size PN with expected intersection of (1tp(1--))Al Define the stabiiiy of I at noise rate p as hp))) = Ex, [xx)) where x, x' are p-correlated. Noise-stability plays role reminiscent of moment generating function in probability, since ortho-normality implies
h(p) E, -(=) P Σ Bip', where B, = Σ
Ps
(7)
S:|S|=i
Thus h()) is a polynomial in p where the coefficient of p² captures the & weight of coefficients corresponding to sets S of size i.
3.1 WHY SHOULD LINEAR DATAMODELS BE GOOD APPROXIMATION?
Suppose f Es Isús is the function of interest. Let B, stand for Es.ss Define the normalized noise stability as h(p) Ex.z' [fx) [x]](()²]] for [0, Intuitively, since concerns test loss, one expects that as the number of training samples grows, test behavior two correlated data sets x, x' would not be too different, since as first randomly picking their intersection and then augmenting this common core with two disjoint random datasets. Thus intuitively, normalized noise stability should be high, and perhaps close to its maximum value of 1. If it is indeed close to 1 then the next theorem (a modification of a related theorem for boolean-valuee functions in O' DDonelll (2014)) gives first-cut bound on the quality of the best linear approximation in terms of the magnitude of the residual error. (Note that linear approximation includes the case that f is constant.)
alternatively think of picking x, x'
Theorem 3.1. The quality of the best linear approximation to f can be bounded in terms of the normalized noise stability h
Es.
P3
1 1 h((p)
(Normalized residual)
(8)
Σs P3
p2
5

---

Published as a conference paper at ICLR 2023
Noise stability vs acorage margat for various test esamples If]
Esimated quality of lnear ht average margin for various test examples [f]
Estimated quality of linear fit vs noise stabiiit
Correlation: 0.9346
2.0
Quality dl Inner fit [1- BBgt
1.0
Nooe stablty figl
664
0.2
0.2
0.21
6.0
Average margin (RL])(()
Average margin (F)))(0)
Nicion stabilit 61))) an p 0.06
(a) Noise stability vs margin
(b) Quality of fit vs margin
(c) Quality of fit vs noise stability
Figure 1: Scatter plots for 1000 test examples and their margin functions (log of ratio of correct label probability and the best probability for another label), for networks trained on p-biased sets x. (a) The normalized noise stability from Theorem 3.1 is high for many points; 44% points are higher than 0.9. Also, noise stability is low for points that have margin close to 0, i.c. those that are close to the decision boundary. (b) Similarly, the estimated quality of linear fit (using Algorithm Ip is good when the model is confidently correct or wrong. (c) Noise stability for p = 0.05 correlates highly with the estimated quality of linear fit, providing credibility to Theorem 3.1
Theorem 3.1 is well-known in Harmonic analysis and is in some sense the best possible estimate all we have is the noise stability for single (and small) value of In fact we find in Figure Ic the noise stability estimate does correlate strongly with the estimated quality of linear fit (based on our procedure from Section 3.2). Figure 3 plots noise stability estimates for small values of p.
In standard machine learning settings, it is not any harder to estimate h(p) for more than one p. and this is is used in next section in a method to better estimate of the quality of linear approximation.
3.2 BETTER ESTIMATE OF QUALITY OF LINEAR APPROXIMATION
A simple way to test the quality of the best linear fit, as in Ilyas et al. 2022). is to learn datamodel using samples and evaluate it held out samples. However learning linear datamodel requires solving linear regression on N-dimensional inputs x, which could require O(N) samples in gen- eral. A sample here corresponds to training a neural net on p-biased dataset x, and training ((N) such models can be expensive. (Ilyas et al. (2022) needed to train around a million models.)
Instead, can we estimate the quality of the linear fit without having to learn the best linear datamodel? This question relates to the idea of property testing in boolean functions, and indeed our next result yields a better estimate by using noise stability multiple points. The idea is to leverage Eqquatin (7) where the Fourier coefficients of sets of various sizes show up in the noise stability function h(p)
Σi Bip' as the non-negative coefficients of the polynomial in Since the residual of the best linear datamodel, from [Theorem 2.2 is the total mass of Fourier coefficients of sizes at least 2, i.e. B2g = =' B,, we can hope to learn this by fitting a polynomial on estimates of hp)) at multiple p Algorithm precisely leverages by first estimating the degree 0 and 1 coefficients (B, and B,) using noise stability estimates at a few p's, estimating 1, and finally estimating the residual using the expression B22 = B Bg - B1- The theorem below shows that this indeed leads to a good estimate of the residual with having to train way fewer (independent of N) models.
B= = B, = h(1) using
J0. p. 2pl.2) 2) be the estimated residual (see Algorithm 1) after fitting a degree 2 polynomial to noise stability estimates at 0, p. 2p, using n calls to f. If = (1/²3) and p = Ve, then with high probability we have that BBz Bzal S e.
Theorem 3.2. Let Bzg RESIDUALESTIMATTION
The proof of this is presented in Appendix B.2 This improves upon prior results residual estima- tion for linear thresholds from Matulef et al. (2010) that do a degree-1 approximation to h(p) with 1/e* samples, more than 1/c² samples needed with d approximation instead. In fact, hypothesize using a degree d > 2 likely improves upon the dependence on e; we leave that for fu- ture work. This result provides way to estimate the quality of the best linear datamodel without

---

Published as a conference paper at ICLR 2023
Algorithm Efficient algorithm for residual estimation
1: procedure RESIDCALESTTMMATIONN]
[pI..... pkl. d)
2: f f: function, n: evaluation budget, d: degree of approximation +/
y E R² A E [xx((+1)
3:
4:
for i [_,..., k.....kja do
5:
yi < "
((--1),
Estimate (ps))
6:
A,; [1. Pi. P
7:
end for
8:
Solve & minzeR | -y12 s.t. 220
Requires solving a convex program
9:
Bo, B1 $1,
10:
B - NOISESTABILITY(U, (((001))))
> Estimate h(1) - E; B;; see Equation (7)
11:
B22 + B - Bo B1
12: return Bz2
B22 is the residual from Theorem 2.2
13:
end procedure
14:
15: procedure NOISESTABILITYC.. n,
16:
hp 0
17:
for j E 7/2. do
Bp
19:
x' ~ RHOCORR(Z,, p)
b x' is p-correlated to z; see Definition 3.1 > Two evaluations of per needed
ho + hp 2/2f(2)((z)
21:
end for
22: return hp
Returns an unbiased estimate for h(p); see Lemma B.
23:
end procedure
having to use O(N/2) samples (in the worse case) for linear regression The guarantee does not even depend on N, although it has worse dependence of that can likely be improved upon.
Experiments. We run our residual estimation algorithm for 1000 examples (see Appendix C for details) and Figure 2 summarizes our findings. The histogram of the estimated normalized residuals (8) Figure 2a indicates that good linear fit exists for majority of the points, echoing the findings from llyas et al. (2022). Figures 2b and 2c study the effects of choices like degree d and p. Furthermore we find in Figure an interesting connection between the predicted quality of linear fit (1- normalized residual) and the average margin of the test point: linear fit is best when models trained on p-biased datasets are confidently right or wrong on average. The fit is much worse for examples that are closer the decision boundary (smaller margin); exploration of this finding is an interesting future direction. Figurey 3 and provide visualizations of the learned polynomial fits the degree and list of p's varied.
UNDERSTANDING GROUP INFLUENCE AND ABILITY FOR COUNTERFACTUAL REASONING
Both influence functions well linear datamodels display some ability to do counterfactual reasoning: to predict the effect of small changes to the training set on the model's behavior on test data. Specifically, they allow reasonable estimation of the difference between model trained with & and one trained with x r-)-- the training set containing J after deleting the points in I. Averaged over æ, this can be thought of as average group influence of deleting 7. We study this effect through the lens of Fourier coefficients in the upcoming section.
4.1 EXPRESSION FOR GROUP INFLUENCE
Let I be a subset of variables and let x E 11 denote random p- p-biased variable with distribution B, Then the expectation of f(z) (-)-)) can be thought of the average
II the datamodel is sparse, lasso learn it with OSSlog N/e²) samples, where S is the sparsity.

---

Published as a conference paper at ICLR 2023
Histogram of estimated residuals 47.00 of residuals are below
Residuals estimated with degree d 2 & Correlation: 0.9995
Residuals estimated using (G: 2p,
For - 1u6 & l.I. Correlation: 0.7971
Exiintted Moust using 0,00
Estmuned B fur d.
1,00
0.77
00.70
Deneit
90.04
100
9:28
0.2
0:23
0.50
Estimated normal zed residial Dea/D
Estinoted
D for 2
Est Eotimated Dea/D using 0.1
(a) Histogram of residuals
(b) Effect of degree
(c) Effect list of p's
Figure 2: (a) Histogram of estimated normlized residual (B2g/ B), for 1000 test examples, using Algorithm with degree d and list [0. 0.1, 0.2, 1] for p's. Almost half of the test examples have normalized residuals below 0.1. (b) Estimations using d = 2 and d = 3, for various test points, are highly correlated to each other, suggesting a small effect degree of approximation in this case. (c) Estimates using [0, p. 2p. 1] in Algorithm 1 for p 0.05 and
0.1; Spearman correlation R 0.8. The choice of p does have some effect, suggesting that there is still some noise in the estimate. Note that Theorem 3.2 requires the right scale of for the estimate to be accuracy.
influence of deleting I. An interesting empirical phenomenon in Koh et al. (2099) is that the group influence often well-correlatd with the sum of individual influences in i.e. Σ, (ff;( In fact this is what makes empirical study of group influence feasible in various settings, because influential subsets can be found without having to spend time exponential in | to search among all subsets of this size. The claim in Nyas al. (2022) is that linear data models exhibit the same phenomenon: the sum of coefficients of coordinates in I approximates the effect of training on 1- We give the mathematics of such "counterfactual reasoning" as well as its potential limits.
Theorem 4.1. [Group inftuence] The following are true about group inftuence of deletion.
11/2
(f) = B [f(x) - f(x1[=-1)]= Σ
E (-1)1")
Fr.
1-
1
GET
PET,N/22
11/122
Σ Inf(())
Σ
(-1)1")
Fr.
1-p
iET
PCLIPI22
where 8* is the optimal datamodel
(Equation (3) and Inf, is individual influence (Equation (1)
Thus we see the that average group influence of deletion is equal to the sum of individual influence, plus residual term. Proof for the above theorem for this is presented in Appendix B.3
This residual term can in turn be upper bounded by (1 -p p)1111112
(see Lemma B.2 which blows up exponentially in T]. However the findings in Figure F. from Ilyas et al. (2022) suggest that the effect of number of points deleted is linear (or sub-linear), and far from exponential growth. In the next section we provide simple example where the exponential blow-up is unavoidable, and also provide some hypothesis and hints as why this exponential blow is observed in practice.
/B= /
4.2 THRESHOLD FUNCTION AND EXPONENTIAL GROUP INFL.ENCEE
We exhibit the above exponential dependence on set size using natural function inspired by em- pirics around the long tail phenomenon (Feldman 2020 Feldman & Zhang 2020), which suggests that successful classification on a specific test point depends on having seeing certain number of "closely related" points during training. We model this as a sigmoidal function that depends on special set A of coordinates (i.e., training points) and assigns probability close to I when many more than 3 fraction of the coordinates A are +1.
For any vector 2 E {+1]d, d let avg(>) = L/a - (1+z)) denote the fraction of I's in 2 and A = (zi) denotes the subset of coordinates indexed by Å C [d].
Similar results can be shown for the average group influence of adding set of points T.
8

---

Published as a conference paper at ICLR 2023
Example (Sigmoid). Consider a function f(x) S (a(avg(IA) B)) for subset A S [N] of size M, where S(u) = (1 + --=ee""-- is the sigmoid function. The function f could represent the probability of the correct label for a test point when trained on the training set x E [+1]].
For this function, we show below that for a large enough p. the group influence of y-fraction subset of A is exponential in the size of the set.
Lemma 4.2. Consider the function from Example i with 3 0.5 and a - De; so f(x 1 (avg(arA) > 0.5). If x is p-biased with p > 0.5, then for any constant fraction subset A' C A, its group influence is exponentially larger than sum of individual influences.
Inf 2 (2(1 p)) --)))-11+++1 1A'1++
Σ YEA
AA
Thus in the above example when p > 0.5, the group influence can be exponentially larger than what is captured by individual influences. Proof of this lemma is presented in (Appendix B.3
Margin v/s probability. The function I from Lemma 4.2 has property that it saturates to quickly, once p is large enough, the individual influence of deleting 1 point can be extremely small, but the group influence of deleting sufficiently many of the influential points can switch the probability to close to [lyas et al. (2022) however do not fit datamodel to the probability and instead fit it to the "margin", which is the log of the ratio of probabilities of the correct label to the highest probability assigned to another label. Presumably this choice was dictated by better empirical results, and now we see that it may play an important role in the observed linearity of group influence. Specifically, their margin does not saturate and can get arbitrarily large as the probability of the correct label approaches 1. This can be seen by considering slightly different (but related) notion of margin, defined as f = log (f /(1 f)), where the denominator is the total probability assigned to other labels instead of the max among other labels. For this case, the following result shows that group influence is now adequately represented by the individual influences.
Corollary 4.3. For function f from Example 1 the group inftuence of any set A' C [N] on the margin function I satisfies the following:
Inf = p Σ (nf(f)
(10)
SEA'
This result follows directly by observing that the margin function is simply the inverse of the sigmoid function, and so its expression is f(x) = (avv((I the Fourier coefficients of sets of size 2 or larger will be zero for a linear function, the result follows from Theorem 4. where the residual term becomes O.
B) which is just linear function. Since all
5 CONCLUSION
This paper has shown how harmonic analysis can shed new light on interesting phenomena around influence functions. Our ideas use a fairly black box view of deep nets, which helps bypass the cur- rent incomplete mathematical understanding of deep learning. Our new algorithm of Section 3.2 has the scemingly paradoxical property of being able to estimate exactly the quality of fit of datamodels without actually having to train (at great expense) the datamodels. We hope this will motivate other algorithms in this space.
One limitation of harmonic analysis is that an arbitrary f far) could in effect behave very differently for on p-biased distributions at = 0.5 versus p = 0.6. But in deep learning, the trained net probably does not change much upon increasing the training set by 20%. Mathematically capturing this stability over (not to be confused with noise stability of [Equation (7) via a mix of theory and experiments promises
be very fruitful. It may also lead generalization theory that accounts for the empirically observed long-tail phenomenon. Finally, harmonic analysis is often the tool of choice for studying phase transition phenomena in random systems, and perhaps could prove useful for studying emergent phenomena in deep learning with increasing model sizes.
new and more fine-grained
"The result can potentially be shown for more general o., B.P

---

Published as a conference paper at ICLR 2023
REFERENCES
Ahmed Alaa and Mihacla Van Der Schaar. Discriminative jackknife: Quantifying uncertainty in deep learning via higher-order influence functions. International Conference on Machine Learning. pp. 165-174. PMLR, 2020.
Juhan Bae, Nathan Hoyen Ng. Alston Lo, Marzyeh Ghassemi, and Roger Baker Grosse. influence functions are the answer, then what is the question? In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
Elnaz Barshan, Marc-Etienne Brunet, and Gintare Karolina Dziugaite. Relatif: Identifying explana- tory training samples via relative influence. International Conference Artificial Intelligence and Statistics, pp. 1899 1909. PMLR, 2020.
Samyadeep Basu, Xuchen You, and Soheil Feizi. On second-order group influence functions for black-box predictions, In International Conference on Machine Learning, pp. 715-724. PMLR, 2020.
Samyadeep Basu, Phil Pope, and Soheil Feizi Influence functions in deep learning are fragile. In International Conference Learning Representations, 2021.
Mare--Eiennne Brunet, Colleen Alkalay-Houlihan, Ashton Anderson, and Richard Zemel. Under- standing the origins of bias in word embeddings. In International conference machine learn- ing. pp. 803-811. PMLR, 2019.
Guillaume Charpiat, Nicolas Girard, Loris Felardos, and Yuliya Tarabalka. Input similarity from the neural network perspective. Advances in Neural Information Processing Systems, 32, 2019.
Hongge Chen, Si Si, Yang Li, Ciprian Chelba, Sanjiv Kumar, Duane Boning, and Cho-Jui Hsieh. Multi-stage influence function. Advances Neural Information Processing Systems, 33:12732- 12742, 2020.
Gilad Cohen, Guillermo Sapiro, and Raja Giryes. Detecting adversarial samples using influence functions and nearest neighbors. In 2020 JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 14441-14450. IEEE, 2020.
R Dennis Cook. Detection of influential observation in linear regression. Technometrics, 19(1): 15-18, 1977.
Vitaly Feldman. Does learning require memorization? a short tale about a long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 954-959, 2020.
Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 33:2881- 2891, 2020.
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In International Conference on Machine Learning, pp. 2242-2251. PMLR, 2019.
Han Guo, Nazneen Rajani, Peter Hase, Mohit Bansal, and Caiming Xiong. Fastif: Scalable influence functions for efficient model interpretation and debugging. In Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, pp. 10333 10350, 2021.
Frank R Hampel. The influence curve and role in robust estimation. Journal of the american statistical association, 69(346):383-393, 1974.
Kazuaki Hanawa, Sho Yokoi. Satoshi Hara, and Kentaro Inui. Evaluation of similarity-baser expla- nations. arXiv preprint arXiv:2006.04528, 2020.
Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclere, and Aleksander Madry. Data- models: Predicting predictions from training data. arXiv preprint arXiv:2202. 00622, 2022.
Louis A Jaeckel. The infinitesimal jackknife. Bell Telephone Laboratories, 1972.
10

---

Published as a conference paper at ICLR 2023
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang. Dawn Song, and Costas J Spanos. Towards efficient data valuation based on the shapley value. In The 22nd International Conference Artificial Intelligence and Statistics, pp- 1167-1176. PMLR, 2019.
Rajiv Khanna, Been Kim, Joydeep Ghosh, and Sanmi Koyejo. Interpreting black box predictions using fisher kernels. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 13382-3390. PMLR, 2019.
Been Kim, Rajiv Khanna, and Oluwasanmi Koyejo. Examples are not enough, learn to criticize! criticism for interpretability. Advances in neural information processing systems. 29, 2016.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pp. 1885-1894, PMLR, 2017.
Pang Wei W Koh, Kai-Siang Ang, Hubert Teo, and Percy S Liang. On the accuracy of influence functions for measuring group effects. Advances in neural information processing systems, 32, 2019.
Shuming Kong, Yanyan Shen, and Linpeng Huang. Resolving training biases via influence-based data relabeling. In International Conference on Learning Representations, 2021.
Guillaume Leclere, Andrew Ilyas, Logan Engstrom, Sung Min Park, Hadi Salman, and Aleksander Madry. ffev. / com/ wtffcc/ffcc/ 2022. commit XXXXXXX.
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, and Rocco A Servedio. Testing halfspaces. SIAM Journal on Computing, 2010.
Harikrishna Narasimhan, David C Parkes, and Yaron Singer. Learnability of influence in networks. Advances in Neural Information Processing Systems, 28, 2015.
Ryan O'Donnell Analysis of boolean functions. Cambridge University Press, 2014.
Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating training data influence by tracing gradient descent. Advances in Neural Information Processing Systems, 33: 19920-19930, 2020.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In International Confer- ence on Machine Learning, pp. 5301-5310. PMLR, 2019.
Andrea Schioppa, Polina Zablotskaia, David Vilar, and Artem Sokolov. Scaling up influence func- tions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 8179- 8186, 2022.
Peter Schulam and Suchi Saria. Can you trust this prediction? auditing pointwise reliability after learning. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1022- 1031. PMLR, 2019.
Stefano Teso Andrea Bontempelli, Fausto Giunchiglia, and Andrea Passerini. Interactive label cleaning with example-based explanations. Advances in Neural Information Processing Systems, 34:12966-12977. 2021.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harv. JL. & Tech., 31:841, 2017.
Hao Wang, Berk Ustun, and Flavio Calmon. Repairing without retraining: Avoiding disparate impact with counterfactual distributions. In International Conference Machine Learning, pp- 6618-6627. PMLR, 2019.
Chih-Kuan Yeh. Joon Kim, Ian En-Hsu Yen, and Pradeep K Ravikumar. Representer point selection for explaining deep neural networks. Advances in neural information processing systems, 31, 2018.
11

---

Published as a conference paper at ICLR 2023
Rui Zhang and Shihua Zhang. Rethinking influence functions of neural networks in the over- parameterized regime. AAAI, 2022.
Jianlong Zhou, Zhidong Li, Huaiwen Hu, Kun Yu, Fang Chen, Zelin Li, and Yang Wang. Effects of influence user trust in predictive decision making. In Extended Abstracts of the 2019 CHI Conference on Human Factors in Computing Systems, pp. 1-6, 2019.
12

---

Published as a conference paper at ICLR 2023
A ADDITIONAL BACKGROUND
A.1 HARMONIC ANALYSIS AND BOOLEAN FUNCTIONS
We provide some more details for the classical Harmonic analysis on the boolean hypereube. Please refer to O D'Donnell (2014) for an extensive discourse on this topic. The set of all func- tions f: { + R can be trivially viewed as vector space, since is it closed under linear combinations. Further for any distribution 'D over the hypercube {+1}%, the set of real val- ued functions can be viewed as an inner product space, where the inner product defined as ( = En-D(s(r)g(t) dimensional vector f E R² for every function f. where f (VD(x),(x)
An alternative way to view this inner product is to define 2
2E(+1IN' Un- der this parameterization, the aforementioned inner product between I and y be viewed as the standard dot product between f and 9: i.e. f 9 Ene(+I)x /() ELE(LI) (1x)s())g((r) Eg-D (()=(((()g(())) = (J.g)D. This inner product leads to the norm defined as ll.fll VEn-Dlf(x)..
(xx)
Harmonic analysis involves identifying special orthonormal bases for this vector space. Studying the behavior of function f for points that have roughly p-fraction of the coordinates is possible by considering the distribution of p-hiased points E {+1] where I is viewed as a random variable whose each coordinate independently set to +1 with probability p. We denote this distribution as B, Properties of functions on the hypercube in this setting are best studied by decomposing it using an orthonormal basis functions for the inner product space defined by (,.) turns out that the functions {Øs 5 [N]] defined as (xx) = Ihes (===)) form the necessary orthonormal basis, where μ = 2p - and o² = 4p(1 - p) are the mean and variance each coordinate x. For orthonormality, require that (Øs, (s B, ss=s'. To why this is true, note that
(0s, 1s Ex
24
II
1
(11)
0
LiES
XES'
2
34 1
F2 11
E,,
(12)
LieSnS
0
rESAS'
0
2
II
Ex:
2j μ
Ex,
2j 1i-H
(13)
#ESNS!
0
iESAS'
0
II iESAS'
Ez.
0: - 14
(14)
where the SAS' denotes the symmetric difference between the sets. The second to last equality follows from the independece of z;'s Bp. while the last equality follows from the definition of mean μ and variance o². Thus if S S", SA.S" = & and this inner product is while if S * S', |SAS|| > 0 and this product is 0 by definition of p. Hence Øs's indeed form an orthonormal basis.
Given an orthonormal basis, every function f: [N] + R be expressed linear combination of this basis, i.c. f = EsciN] fsos. The coefficients are often refered to fs' 's as "Fourier" coefficients of f. when the orthonormal basis is clear from context. The orthonormality of Φs's 's also implies Parseval's identity: Es PS = |[ | B since the l norm measured using any orthonormal basis should be the same.
A.2 LINEAR DATAMODELS
We provide some more background on linear datamodels from [lyas et al. (022) in the context of this paper; please refer to the original paper for more details. Consider training set that is a subset of [N], denoted by x E [=1]N. The goal of datamodels to be able to predict the outcome of training neural network, using fixed training algorithm,
particular training set. Consider a function f(x) that denotes that results of training on x, where f can denote any function of the resultant network, e.g. test loss loss particular test example, margin for test example,
13

---

Published as a conference paper at ICLR 2023
norm of parameters etc. Since the training algorithm involves randomness from various sources (initialization,, SGD), f can be viewed as an average over this randomness for a given training set æ.
In general, f could be very complicated function of the training set for instance it could strongly depend on the presence or absence of particular subsets of datapoints. Furthermore due to the black- box nature of trained networks,
would not expect there be simple description of the function f. Rather surprisingly, lyas et al.] 2022) found that for the function f that denotes the margin for single test example, f can average be approximated by linear function of the indicator of the training set v, i.e. / (x) x 0 x for x ~ By. One implication of this result is that the effect of adding or deleting a single point E [N] independent
the rest of the training set and only depends on the size of the training set. A more important consequence is that @ can be estimated by training evaluating f on many x's which would require training net for these x's and then fitting linear function Ô on those samples. This can be used to not only estimate the individual influence &, of datapoints, but also gives a way to predict on new I by using the estimate êT æ rather than actually training a net on æ. Details on how is learned using Lasso regression (to encourage sparsity) can be found in [lyas et al. (2022). Using Harmonic analysis, that the outcome of Einear/Ridge/Lasse regression will provably be equal to the individual discrete influence each point
show in Theorem 2.2
B OMITTED PROOFS
B. PROOFS FOR SECTION 2
We recall Theorem 2.2
Theorem 2.2 (Characterizing solutions to linear datamodels). Denote the quality of a linear data- model 0 E R-++ on the p-biased distribution over training sets Bp by
R(0)= = Bx-B, (frc)) 0o
N
27
Σ 0,
(2)
i=1
where & E {0, 13N is the binary version for any x E {=1]".
Then for μr = 2p and o =
/4p(I-ph p), the following are true about the optimal datamodels with and without regularization:
(a) The unregularized minimizer 0* = arg min R(0) satisfies
(1 (u+1) 1)
0 = Jup 0g --=io
Σ9.
0z.
(3)
2
Furthermore the residual error is the sum of all Fourier coefficients of order 2 or higher.
R(O*) B22
Σ
SC(N
(b) The minimizer with & regularization 8' (* argmin (R(A) + A||0IN 12] satisfies
41 -1 1+
0* ('(2,)2;; = 0 gz
for
(5)
(c) The minimizer with regularization 8" (* (1,,
arg min (R(0) + Al10 satisfies
8* (*, -
-//) )N)))
sign (f() (1ooz) - -3/0)
(6)
where 2+ 21220 is the standard ReLU operation.
14

---

Published as a conference paper at ICLR 2023
Proof. For all three parts, will study the problem in the Fourier basis corresponding the dis- tribution Bp and the proof works for every E (0, 1). Since [ØS]Sg[N] is an orthonormal basis for the inner product space with (f,g)B,
E
(x)) we can rewrite R(0) as follows
B~Bp
R(0)= BB
(1())
((x) - 0u 00-
Σ OgTs
2
( E ER [(x) ((()) 0u -0- -iddds(o))) 2
(15)
(6t) ʃ 00 -o
0:0100
where |1911, = (0.9)5, - EE-W, [0(x)}
(16)
B5
σ 0,, 0o = 90 +
(n
and 0, = 2
0,
(17)
2
The first equality (i) follows by observing that æ; = 2T, - 1 and that @1s) (x) (1) (a. (m-11/o. Step (ft)
follows by applying the definition of [gl||, to the function f 0 Σ, (:0
We can further simplify Equation (16) as follows:
R0) ʃ -0 -0,by0
0,040
00-00 0o
Σ
[ - -0.) Øs Σ
Soos
(18)
B8
S:|S|=1
S:|S|22
-01 (00
(0, - T10)
Σ
1
(19)
8:1122
where (i) uses orthonormality of { and Parseval's theorem (O'Donnell 2014). With this expression for R(0), we are now ready to prove the main results.
sgIN]
Proof for a From Equation (19) is evident that the minimizer for the unregularized objective
will satisfy 0j Jo and 0; [44 for [N]. Plugging this into Equation (17) yields the desired
expressions for . Furthermore, the residual for this optimal 6" is Es: f3.
Proof for b) The & regularized objective can be written as follows:
N
R(0) + IN 112 R())
0 R(0)
(20)
where (i) follows from Equation (17) Combining this with Equation (19) we observe that min-
imization w.r.t. 8: can be done independently of each other. Thus 0: = arg ming, (6.-fto) +
# = -1+ ) Fiy.- Plugging this into Equation (17) gives the desired expression for 0*. Proof for (c) The & regularized objective can be written follows:
N
2x
R(0) + A110 R(O)
Σ 10.1 -0 R(0)
00.1
(21)
2 + Again the minimization w.r.t. 0: can be done independently: 0 = arg ming (a))
2A 0, = (f() - -//o))),, - (-fi 1/o) Plugging this into Equation (17) gives the desired
expression for 6*
B.2 PROOFS FOR SECTION 3
We recall Theorem 3.1
Theorem 3.1. The quality of the best linear approximation to f can be bounded in terms of the normalized noise stability h
Es.
P3
1 1 h(())
(Normalized residual)
<
(8)
Σs P3
p2
15

---

Published as a conference paper at ICLR 2023
Proof. We first note that h(p) h(p)/h(1) since [z) is the noise stability when x' which happens at p = 1. Let B₁ =s: f3.
From Equation (7) we get
h(p) Es SI ExpB. Ba
Bo + B1 + p² Ex22 Bk
Es
Σn Bb
Br
Σx Bk
Let B = Esss = Ek jk and Bz2= = S122 ==== 3 Ps. Then we get,
00:==sssppp
h(p) - (B-B29 ) + +2² =1 -1 (1 p²)
Bz2
B22
1 h(p) 1- p²
B
B
B
This completes the proof.
Lemma B.I. For function and p [0.1] and evaluation budget nt let hi(p) NOISESTABILITY p) be the noise stability estimate from Algorithm 1 If [f(())) < C for every x, then with probability least 1/ the error in the estimate be upper bounded by
(ule)) - m(o) 8(n) o (Vo (C<llo(L//n//n)
(22)
Proof. The proof follows from a straightforward application of Hoeffding's inequality. Note that h()) = 2 ( is sum of 7/2 i.i.d. variables that are all in the range [-C², C*).
Additionally since E[h(p)] = h(p). Hoeffding 's inequality gives
P ((((e) h(p) 2 26) 2e E..
(23)
Setting 8 = C 220loogg (2g((/n)/m makes this probability at most v), thus completing the proof.
We now prove Theorem 3.2 Recall the statement:
[0. p. 2p). be the estimated residual (see Algorithm 1) after fitting a degree polynomial to noise stability estimates at 0, p. 2p, using n calls to f. 1f = (1)ee)) and p = Ve, then with high probability we have that B2z Bz2 e.
Theorem 3.2. Let Bz2 RESIDUALESTIMATTIN
Proof. Using standard concentration inequalities, Lemma B.1 shows that the estimations are close
enough to the true values with high probability, i.e. = h(ps) h(ps) + 5, where 1ó, < where å = 8(n/k)
V//n from Lemma B.1 Let & be the solution to Algorithm 1 and let
z' [B be the "true" coefficients up to degree d. Since minimizes | 1- and x is also a valid solution, we have
| y/1² S ||Ax* y11²
(24)
Furthermore, we note the following about A=#
(Ax") = > B,pl = h((p))
EBBp' E [h(pt)
Bsd Pt d+1 h(p))]
(25)
j=0
i2d
We can upper bound ||Az* y/1² by observing that
((Az)): yil < |6:1 + Bza Pi d+1
< + Bya Pi d+1
(26)
||--- y|l² < l (5 + Byd Ps 12
(27)
Using these, we measure the closeness of & to x² as follows:
A - A& 2 < 2 (|l AI - y + || A - y1l < A||A2² - y/1²
(28)
where the first inequality follows from triangle inequality and Cauchy- Sauchy-Schwarz inequality, and the last inequality follows from Equation (24)
16

---

Published as a conference paper at ICLR 2023
A naive upper bound for ||2 ||| is Amin (A) -1))-
Az Aall- However this turns out to be quite
a large and suboptimal upper bound. Since Algorithm only returns &1 and &2, corresponding to estimates of Bn and B1, we only need upper bound [2; 2 for i E [2].
We now analyze the special case of k = 3, = 2, p 0, P2 = P:P3 = 2p. Here we have
111
0
A
1
Let A x" 2. Firstly note that (AA): A and A S || To 4p²
2p
upper bound 22 we note that
0
A
A p A3
AA = A2
+
p
1 +
(29)
A3
2p/
4p²
|||||| = 11pA2 2 + Bull > min |1 Bwll = r (1 B B ml| 2 A21 (30)
where the last inequality follows from numeric calculation of the norm, and the last inequality follows from the fact that the minimum & can be obtained by finding the residual after projecting onto B. Thus |1| Bol = A < AA and [22 Bi Ail [0.)3/))39p))
Combining Equations (27)
28 and (30) we get that
8 D+BD000 =0 =066 Bzap²
1 - Bol and م2 - B1l 5
(31)
Picking the optimal value of p ((5/Bys)1/3)
(n-11/0 and using the fact that
0
B h(1) 21 22 we get
B22 h11 By B1 B22 0 (0(21/3 1/3 - (( (B23) 1/3
(32)
Thus to achieve an approximation, we need p = 0 (v) and n = Ω (B23/e*), which completes the proof.
B.3 PROOFS FOR SECTION 4
We recall Theorem 4.1
Theorem 4.1. [Group influence] The following are true about group influence of deletion.
11//2
(f) = Ex-H, [f(z) - f(z) >
E
(-1)12)
P
Fr
=
1-
iEI
11//2
=p> (nf((f)
E (-1)1"
p
Fr.
1-p)
iET
PCI,PI22
where 0* is the optimal datamodel (Equation (3) and Inf, is an individual influence (Equation (1)
Proof. Recall that the function f can decomposed into the Fourier basis as f(x) = ESENN fsØs(x) Escin fs lies (mi-u), where 2p 1 and /4p(1 p). Thus
setting σ, to 11 will have the following effect:
f(111--1)= = Σ fs
-11-4
[sni
Φsy1(z) Σ is SCIN]
-2p
[sh/]
(5))(2)
2 -
SCIN]
(33)
17

---

Published as a conference paper at ICLR 2023
( p
|8nr|/2
= E fs(-1)1snn
1-p Φs(((1)
(34)
SCIN
(
1/1/2
Σ (2(2) E(-1)er
P
fsur
(35)
1-p
S
where step (i) we collect all terms that share the same Øsy by relabeling $ < S and I' <
Sn.. This proves the first part of the result.
For the second part we first note that [, fa. Secondly, the only term that remains in [x] 1)] is the constant term (i.e. coefficient of the basis function (x)). From Equation (35)
only the terms with remain. So,
1/1/2
Ex [[(x)) - [(])--1)) = Jo
(1-))
p
Fr
(36)
T-p
P
Pgr
121/2
p
[1]
Σ
(-1)12)
1-P
P
Fr
(37)
IET
1111/2
(0)
E
(-1)
p
fp
(38)
1-p
IE!
1'S,/122
121/2
(i))
0
Σ (-1)1-)
P
(39)
1-p
IEI
122
111/2
(M))
Σ
(ff
E (-1))")
P
Fr
(40)
1-p
SET
P'C,//22
where (i) follows by separating out the size 0 and size 1 1"s, (ii) follows from Theorem 2.2 and (iit) follows from Proposition 2.1
We now show an upper bound on the residual term from the previous result in terms of the residual of linear datamodels.
Lemma B.2. The residual term of group influence minus sum of individual influences from Theo-
rem 4.1 can be upper bounded as follows:
111/2
Σ (-1)
(1-2)
P
Fr << <1-1)))1112 B22
/22
(41)
PETIFI22
where Bzz is the residual of the best linear datamodel as defined in Equation (4)
Proof. We use Sauchy-Sehwarz inequality to upper bound this residual.
1///2
2
1- p "")
Σ (-1)17)
P
Fr
Σ
p
Σ
P
T-p
PET,/ 22
MST,N122
NET,TT22
(42)
P
Σ
P
(43)
p1
PCL
1+ 1-p)
Bz2 (1 -111
(44)
This completes the proof.
18

---

Published as a conference paper at ICLR 2023
We now prove the exponential blow up in group influence from Lemma 4.2 (restated below).
5 f from Example 7 with 3 0.5 and a + oo; so f(x) = {avg(zA) > 0.53. If x is p-biased with p > 0.5, then for any constant fraction subset A' S A, its group influence is exponentially larger than sum of individual influences.
Lemma 4.2. Consider the function
(2(1 p)) -111++
Infx.()
En VEA
(9)
1A
Proof. Let M = |A| and suppose |A'| = >| for small constant 7. We study [ff using its definition and for a general | (0, 1). The function of interest is f(x) 1 (avg(za) > B. Let
B(n, q) denote the binomial r.v. that is sum of n independent Bernoulli's 's with parameter We first note that we can rewrite the expected value of f as follows:
Ex [f(z)] = Pr (B(M, > BM)
(45)
This is because the only times ((x) is 1 is when at least 3 fraction of indices A are 1, which is precisely capture by the Binomial distribution tail probability. Similarly, we can argue that
Ex (= = Pr (B(M(1- - > BM)
(46)
The group influence can be calculated follows:
Inf = E., [f(x)] - E. [f(=)
(47)
Pr(B(M,,)) > BM) - Pr(B(M(( - 7). BM)
(48)
= Pr((BMM(1- - -))p) S 3M) - -Pr(B(M,)) BM)
(49)
(M(1 (M(1-1)) 100M(1
")) M(1
Σ
p) (11--888
(50)
B'
Br #....
M
Σ
p M(1 (1 - 2(1-0")))
(51)
3
B' Ms 11
Define ca(7) = (M(1->)) BM (1- (1-))M(1----
The the above expression reduces to
Inf In)
Σ
(cx( Car (0))
(52)
B'E( S
Note that individual influences (J) corresponds sets of size |A'| i.e. 7 = 1/M. So.
Inf;( =
Σ
(c/ar) c, (0))
(53)
g M
We study the quantity (g(>) in more detail. In particular, we use Stirling's 's approximation for bino-
mial coefficients loga (gx) nH (q). where (g) = -qlog2 q - (1 -4) logg (1 - 9) is the entropy
function. This gives a cleaner expression for (og)(c((7)).
(M(1- (M((1>1))
71) + BM (p) + (1- 3 3- - -)) l0g2(1 (1))2111) pp)
1og2(ca(7)) = logg
(54)
3M
3
(M(1-7))
+ MB (og + M(1 - 3 - 7) logg (1 -1p)
(55)
For a small y, we use linear approximation for (cx(()) at y = 0. The derivate is
d log, (ca(T)) 1- M (108s 1ogg2 3 (1-3) H logg - p)) ((
(56)
dy
where g(3) is decreasing function of B. This gives us the approximation for c²(7)
log2 (ca(>)) ~ log, (0) + (3)
(57)
'The result can potentially be shown for more general o., 8.P
19

---

Published as a conference paper at ICLR 2023
co(r) c²
(58)
We note that for 8 & 0.5 and > 1/2. g(5)) > 0 and so ca is an increasing function in 7.
For ratio of group to individual influence from Equations (52) and (53) we consider the following expression for / I 3 = 0.5:
cg. (1) - cg)(0)
2 c3 (3)
2 2(7-4/w)9(0)) 2 2 2-7--1//)00000
(59)
C3 (2/M) Cø. (0)
cØ c/. (+/M)
--7 (-1-oo((1-) (2 -p) p)) -
(60)
= (2 - p)) |4||+1
(61)
Plugging this back into Equations (52)
and (53)
we see that the terms for each 3 in the summation
upper bounded by Equation (61) This gives
Inf (f) 2 (2(1 p)) p)) 114 (f)
(62)
Considering the total individual influences instead of just influence for just point completes the proof.
C EXPERIMENTAL SETUP
Experiments are conducted on the CIFAR-10 data to test the estimation procedure and the quality of the linear fit in Figures I and We use the FFCV library Leclere et al. (2022) to train models on CIFAR-10. 10; each model takes 30s to train on our GPUs. We first pick subset of 10k images from the CIFAR-10 training dataset. Our models trained are then trained on sets of size 5000 (corresponding to p = 0.5), which achieve an average of ~ 71% accuracy on the CIFAR-10 test set. For the noise stability estimates from Algorithm x') each for p 0.05, 0.1, and 0.2. We train 12,000 models for each setting p, where there 600 distinct sets 600 distinct p-correlated sets x' chosen and the remaining 10x runs due to running 10 random seeds per training set. We use the default ResNet based architecture in FFCV with batch size of 512, initial learning rate of 0.5, 24 epochs, weight decay of 5e-4 and SGD with momentum as the optimizer.
we sample 600 pairs of p-correlated datasets
For the experiment with residual estimation, use the of p's be [0, 1.0.1,,.2,, 1] for most experiments, 00, 0.05, 0.1, 0.05,0.1,
for Figure 2c and 0.1, 0.2] for Figure 4 Furthermore we use
degree d 2 in Algorithm for most experiments and d 3 for comparison in Figure 2b Although the theoretical analysis in [Theorem 3.2 does not use م we find experimenaally that adding o = gives more robust estimations. This is evident from the polynomial fits obtained for 20 randomly selected test examples in Figures 3 Jandd 4 where the fits from [0, 0.1, 0.2, 1] are clearly better than those from [0, 0.1, 0.2). The theory can also be extended for this case, with a slightly modified analysis.
for the polynomial fitting,
20

---

Published as a conference paper at ICLR 2023
13 L00 18877
140
21
38 10)
138 1// 102/-6017
28 18.188--888 -1001-000
12-
16-230
211
C8 68) 107
138 840 LN0
547 ERE CRLY
Figure 3: Noise stability estimates plotted for 20 randomly sampled test examples. For each example (corresponding to a plot), we plot the estimated h(()) in blue dots and the best degree {1, 2,3) (black. red and blue curves respectively) polynomial fits obtained from Algorithm for the list of p's being [0, 0.1, 0.2, 1]. The test examples are rearranged such that the first 4 rows contain points with min, h(()) > 0.7 and the y-axis range is set to [0.6, 1] for clarity of presentation. The y-axis range for the last row is set to [0, 1]. The estimated residual from Algorithm ] precisely equal to one minus the sum of the constant and degree-1 coefficients.
21

---

Published as a conference paper at ICLR 2023
Mal
8.00
20
4.5
030
150
100
035
8.0
130
200
135
13 E00
077
37
2.01 400
300 645
510 600
1.3
200 10-88---4000
170
1.0
830
6.00
130
EUPT
C40 880
32
126
6.7
Figure Noise stability estimates plotted for 20 randomly sampled test examples. For each example (corresponding to a plot), we plot the estimated h((p) in blue dots and the best degree {1, 2,3) (black. red and blue curves respectively) polynomial fits obtained from Algorithm for the list of p's being [0, 0.1, 0.2]. The test examples are rearranged such that the first rows contain points with min, h(()) > 0.7 and the y-axis range is set to [0.6, 1] for clarity of presentation. The y-axis range for the last row minus the sum of the constant and degree-1 coefficients.
[0, 1]. The estimated residual from Algorithm precisely equal one
22


Reviews:
[{"review_id": "xmLaAdeMJZw", "reviewer": "Reviewer_rQ2x", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on a very interesting and important research topic, predicting the predictions from training data. Built on the datamodels proposed in [1], this paper seeks to provide a better theoretical understanding of why a linear regression method can predict the effect of training data. More importantly, this paper designs a new algorithm for estimating the approximated linear datamodel with much less training cost. This paper provides an exciting view to the counter-factual explanations of training data.\n\n[1]Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. Datamodels: Predicting predictions from training data, ICML 2022", "summary_of_the_review": "This paper is generally well-written and novel, and the authors focus on an interesting research problem. I'd like to accept this paper and appreciate if the author can revise the paper more clearly.", "strength_and_weaknesses": "Strength:\n1. The research problem, analyzing the influence of data points, is very interesting and important for explainable AI.\n2. The paper provides a theoretical analysis of the linear datamodel, and explained why the effects of number of points deleted is observed in practice as linear rather than exponential.\n3. Experimental results verified the proposed method\n\nWeaknesses:\n1. This paper is not friendly to most beginners, and the main idea is hard to follow. The authors also need to explain more detailedly how the residual estimation can predict the performance.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "_kLP_UdQBX", "reviewer": "Reviewer_ECUW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides some mathematical understanding on influence functions and datamodels via harmonic analysis including\n1. reasons for existence of datamodels.\n2. exact characterizations of \\theta_i for datamodels without/with abbitrary regularization.\n3. providing a new algorithm to estimate the degree whether a linear datamodel is well-approximated without having to train the datamodel per se.\n4. studing group influence which quantifies the effect of adding or deleting a set.", "summary_of_the_review": "This paper introduces harmonic analysis into the discussion of influence functions and datamodels and gain some novel results. But the main theorem proofs based on the intuition. Generally, I think harmonic analysis is a useful and relatively novel tool for machine learning.", "strength_and_weaknesses": "Strength:\n1. This paper introduces harmonic analysis into the discussion of influence functions and datamodels, which is a novel idea.\n2. This paper gives a new algorithm to estimate the degree whether a linear datamodel is well-approximated without having to train the datamodel per se.\n\nWeakness:\n1. To my knowledge, all the analysis in this paper is based on a fixed test point, which means that we need to repeat the algorithm proposed in this paper with $m$ times when we need to estimate $m$ test points.\n2. In Section 3.1, the author claimed that normalized noise stability should be high, and perhaps close to its maximum value of $1$ when the number of training samples grows, intuitively. Then Theorem 3.2. gives a bound on the best linear approximation in terms of the magnitude of the residual error because $1- \\overline{h} (\\rho)$ is close to $0$. But if I understand correctly, $\\overline{h} (\\rho)$ is close to $1$ when $\\rho$ is close to $1$ intuitively. The bound given in Theorem 3.2 is meaningless at this point. In consequence, I think this intuition lacks theoretical or experimental evidence. I am willing to raise my score if the author can explain this question theoretically or experimentally.\n3. It becomes worthless to estimate the quality of the best linear datamodel when it becomes a question whether datamodel is a good approximation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "S_cL9YKa2E", "reviewer": "Reviewer_cauj", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper revealed the connection of influence function and the linear datamodel using harmonic analysis.\nLinear datamodel is a model fitted with an $N$-dimensional binary vector as its input and with the outcome (or loss) of a model trained on a subset of $N$ training points indicated by the binary vector as its regression target.\nA recent study observed that the influence function (more formally, discrete influence function) can be approximated by this linear datamodel.\nThis paper provides a unified view of this observation why such an approximation is possible.\nLet $f$ be a training algorithm that maps the $N$ dimensional binary vector to the target.\nFor the analysis, the authors considered expanding $f$ using an orthonormal basis in $N$ dimensional space.\nThis expansion allows us to view $f$ as a function on the $N$ dimensional grid rather than the training algorithm.\nWith this expansion, we can see that discrete influence function corresponds to the coefficient of the degree-1 basis. \nThis finding explains why the linear datamodel can approximate discrete influence function.\nIf the coefficients of $f$ in the higher-degree basis are small, the basis of degree-1 can well approximate $f$.\nThe authors also analyzed a case when this approximation is possible by introducing the notion of noise stability.\nThe authors also provided an efficient algorithm for estimating the approximation error.\n", "summary_of_the_review": "This paper provide the characterization of the connections between influence function and the linear data model.\nThis characterization successfully explained the finding of the linear datamodel.\nThis is an interesting problem and the finding would be novel.\nThe paper also provides some counter cases when the connection fails, and also an efficient way to estimate the fitting error so that one can assess whether the linear datamodel is valid on the dataset at hand.", "strength_and_weaknesses": "### Strength\nThe major strength of the paper is on the characterization of the connections between influence function and the linear datamodel.\nThis characterization successfully explained the finding of the linear datamodel.\nThe authors also found some counter cases when the connection fails.\nThe authors further provided an efficient way to estimate the fitting error so that one can assess whether the linear datamodel is valid on the dataset at hand.\n\n### Weakness\nI do not find any crucial weakness.\nAs a minor suggestion, I think the paper becomes much easier for the readers if there is a brief overview of the linear datamodel.\nThe linear datamodel is not that popular compared to influence function.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6svst48VQO", "reviewer": "Reviewer_TeFi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper uses theoretical tools from harmonic analysis and noise stability to explain the effectiveness of data-models introduced by Ilyas et. al (2022). In addition, the same theoretical components are used to analyze group influence and identify conditions when first-order influence (linear in terms of training data influence) can be used to characterize group influence. ", "summary_of_the_review": "Overall,  I feel that the theoretical contribution is a good initial step towards understanding data-models and finding links between influence estimation and datamodels. While the authors connect the theory to empirical findings (e.g., prediction of the fit), this section can be strengthened with more experiments on datasets beyond CIFAR-10. \n\nOverall, the paper can be a good addition to iclr as it provides some theoretical footing connecting datamodels to  influence functions.", "strength_and_weaknesses": "Strengths:\n\n\t- While the framework of datamodels empirically approximate training data influence, the original paper does not show any understanding of why it works in the first place. This paper, provides a starting point to analyse datamodels and further understand why it works. This is one of the major strengths of the paper. \n\n\t- The noise stability estimator is a good contribution to bypass the expensive process of training the datamodels (though see Weakness for a follow-up question). \n\n\nWhile I am not an expert in harmonic analysis, there are certain questions regarding the paper:\n\nWeakness / Questions:\n\n\t- While Ilyas et. Al (2022), show that datamodels can approximate group influence (via linearity), as shown in previous works [1], this linearity assumption is not always true, especially when a large number of points are deleted. In such cases, how does datamodels relate to higher-order variants of influence which seem to be a better approximation for group influence? \n\n\t- The paper has a good theoretical contribution, however I would like to see some more empirical analysis on how the noise stability estimator is a good proxy for predicting the fit. One way could be to run similar experiments on datasets beyond CIFAR-10 (e.g., Imagenet derivatives) to strengthen it's effectiveness.\n\nThe paper is difficult to read for someone who has limited background on harmonic analysis; Considering influence functions is used by a mix of empirical + theoretical researchers, it would be good to provide a small background on the topic in the Appendix or in the main paper (e.g., a brief background of the theoretical tools used in your analysis). \n\n\n[1]. https://arxiv.org/abs/1911.00418\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster