A Learning Theoretic Perspective on Local Explainability
Authors: Jeffrey Li
Vaishnavh Nagarajan
Gregory Plumb
Ameet Talwalkar
Venue: ICLR 2021 Poster (2021)
Keywords: Interpretability
Learning Theory
Local Explanations
Generalization

Abstract: In this paper, we explore connections between interpretable machine learning and learning theory through the lens of local approximation explanations. First, we tackle the traditional problem of performance generalization and bound the test-time predictive accuracy of a model using a notion of how locally explainable it is.  Second, we explore the novel problem of explanation generalization which is an important concern for a growing class of finite sample-based local approximation explanations. Finally, we validate our theoretical results empirically and show that they reflect what can be seen in practice.

Published as a conference paper at ICLR 2021
A LEARNING THEORETIC PERSPECTIVE ON LOCAL EXPLAINABILITY
Jeffrey Li"
Vaishnavh Nagarajan", Gregory Plumb Carnegie Mellon University va i shnavh@cs. cmu. edu
University of Washington jw1 21 620cs. washington, edu
Ameet Talwalkar
Camegie Mellon University & Determined AI
ABSTRACT
this paper, we explore connections between interpretable machine learning and learning theory through the lens of local upproximation explanations. First, we tackle the traditional problem of performance generalization and bound the test- time predictive accuracy of a model using notion of how locally explainable it is. Second, we explore the novel problem of explanation generalization which is an important concern for growing class of finite sample-based local approximation explanations. Finally, we validate our theoretical results empirically and show that they reflect what can be seen in practice.
INTRODUCTION
There has been growing interest in interpretable machine learning, which seeks to help people better understand their models. While interpretable machine learning encompasses wide range of problems, is a fairly uncontroversial hypothesis that there exists a trade-off between a model's complexity and general notions of interpretability. This hypothesis suggests seemingly natural connection to the field of learning theory, which has thoroughly explored relationships between a function class's 's complexity and generalization. However, formal connections between interpretabil- ity and learning theory remain relatively unstudied.
Though there several notions of conveying interpretability, one common and flexible approach is to use local approximations. Formally, local approximation explanations (which we will refer to as "local explanations") provide insight into a model's behavior as follows: for any black-box model E IF and input the explanation system produces a simple function, 9u (x') E Grocal, which approximates / in a chosen neighborhood, x' N₂. Crucially, the freedom to specify both G and N₂ grants local explanations great versatility. In this paper, we provide two connections between learning theory and how well f can be approximated locally (i.e. the fidelity local explanations).
Our first result studies the standard problem of performance generalization by relating test-time predictive accuracy to a notion local explainability. As turns out, our focus on local explanations leads us unique tools and insights from a learning theory point of view. Our second result identifies and addresses an unstudied yet important question regarding explanation generalization. This question pertains to growing class of explanation systems, such MAPLE (Plumb et al.) 2018) and RL-LIM (Yoon et al. 2019), which we call finite sample-based local explanation These methods leam their local approximations using common finite sample drawn from data distribution D (in contrast to canonical local approximation methods such as LIME (Ribeiro et al.] (2066) and, as result, run the risk of overfitting to this finite sample. In light of this, we answer the following question: for these esplanation-learminn systems, how well do the quality of local explanations generalize data not seen during training?
" Denotes equal contribution
'This terminology is not to he confused with "example-based explanations" where the explanation itself is in the form of data instances rather than function.

---

Published as a conference paper at ICLR 2021
We address these questions with two bounds, which outline now. Regarding performance gener- alization, we derive our first main result, Theorem [I error (MSE) of any f in terms of its MSE over the m samples in the training set. S { y4) )=)
which bounds the expected test mean squared
(c..)-D((f())-20) (x) O (f(a)) u.) 2 E snlly (0) + Ps (Qrea))
Test MSE
Train MSE
Interpretabiliity Torm (MNF)
Complexity Term
Regarding explanation generalization for finite sample-base iuplanation-lerrinng systems, we ap- ply similar proof technique to obtain Theorem 2, which bounds the quality of the system's expla- nations on unseen data terms of their quality on the data on which the system was trained:
m
E Ex-D, (x)((x) f(z)) N'
B (((())) -9 (x.)))) +
Test MNF
Train MNF
Complexity Temm
Before summarizing our contributions, we discuss the key terms and their relationships.
Interpretability terms: The terms involving MNF correspond to Mirrored Neighborhood Fi- delity, metric use measure local explanation quality, As discuss in Section [ this is a reasonable modification of the commonly used Neighborhood Fidelity (NF) metric (Ribeiro
(et al., 2016 Plumb al., 2018). Intuitively, we generally expect MNF be larger when the neighborhood sizes are larger since each 9r. is required to extrapolate farther.
Complexity term: This term measures the complexity of the local explanation system g in terms of (a) the complexity of the local explanation class Gooca and (b) Ps. quantity that define and refer to as the neighborhood disjointedness factor. As we discuss in Section 4 Ps is value in [1, v /ml (where m = |S)) that proportional to the level of disjointedness of the neighborhoods for points in the sample S. Intuitively, we expect Ps to be larger when the neighborhoods sizes are smaller since smaller neighborhoods will overlap less.
Notably, both our bounds capture the following key trade-off: as neighborhood widths increase, MNF increases but ps decreases. As such, our bounds non-trivial only if the neighborhoods N₂ be chosen such that MNF remains small but ps grows slower than Ö( (since Rss (Siocaa))) typically decays as O(1/ /m)).
We summarize our main contributions as follows:
(1) We make novel connection between performance generalization and local explainability, ar- riving at Theorem Given relationship between MNF and Ps: this bound roughly captures that casier-to-interpre when reasoning about is difficult (c.g. for neural networks). Further, our proof technique may be of independent theoretical interest it provides complexity of a particular class of randomized functions (see Section 4
enjoys better generalization guarantees, potentially valuable result
way to bound the Rademacher
We motivate and explore an important generalization question about expected explanation qual- ity. Specifically, we arrive at Theorem 2 bound for test MNF in terms of train MNF. This bound suggests that practitioners can better guarantee good local explanation quality (measured by MNF) using methods which encourage the neighborhood widths to be wider (see Section
(3) We verify empirically on UCI Regression datasets that our results non-trivially reflect the two types of generalization practice. First, we demonstrate that ps can indeed exhibit slower than O (mm) growth without significantly increasing the MNF terms. Also, for Theorem we show that the generalization gap indeed improves with larger neighborhoods (see Section
(4) Primarily to aid in our theoretical results, we propose MNF as a novel yet reasonable measure of local explainability. Additionally, argue that this metric presents a promising avenue for future study, as may naturally complement NF and offer a unique advantage when evaluating local explanations "realistic" on-distribution data (see Section
2

---

Published as a conference paper at ICLR 2021
2 RELATED WORK
Interpretability meets learning theory. Semenova et al. (2020) study the performance general- ization of models learned from complex classes when they can be globally well-approximated by simpler (e.g. interpretable) classes. In such cases, their theory argues that if the complex class has many models that perform about as optimally on training data, generalization from the complex class can be more closely bounded using the simpler class's s complexity. In our corresponding results, we similarly aim to avoid involving the larger class's 's complexity. However, we directly study general- ization via model's local explainability, rather than instantiate "complex" and "simple" classes for global approximations. The two are fundamentally different technical problems; standard learning theory results cannot be directly applied as they are done for single-function global approximations.
Statistical localized regression. Fan 1993; Fan & Gijbels] 1996) are canonical results which bound the squared error of a nonparametric function defined using locally fit models. These local models are both simple (e.g. linear) and similarly trained by weighting real examples with a kernel (i.e. an implied neighborhood). However, each local model is only used to make prediction at its source point and the theory requires shrinking the kernel width towards 0 as the sample size grows. We instead fit local models as explanations for trained model (i.e. which is considered the "true regression function") and more importantly, care about the fidelity of each local model over whole (non-zero) neighborhoods. Unlike localized regression, this allows us use uniform convergence to bound test error with empirical and generalization terms. While the previous results do not have empirical terms, the learning rates are exponential in the number of samples.
Learning Theory. Another line of related work also studies how to explain generalization of over- parameterized classes. As standard uniform convergence on these classes often leads vacuous bounds, a general approach that has followed from (Nagarajan & Kolter 2019; Zhang et al.) 2017] Neyshabur et al.) 2014) has been to study implications of different biases placed on learned models. We study what would happen if an overparameterized model had an unexplored type of bias, one that is inspired by local explainability. Additionally, our work's technical approach parallels an- other line of existing results which likewise try to apply uniform convergence on separate surrogate classes. This includes PAC-Bayesian bounds, a large family of techniques that come from looking at stochastic version of a model in parameter space (McAllester 1998. 2003 Langford & Caruana 2002] Langford & Shawe- Taylor 2003). In a different vein, some results in deep learning look at compressed, sparsified, or explicitly regularized surrogates of neural networks (Arora et al. 2018 Dziugaite & 2017). In our case, the surrogate class is a collection of local explanations.
3 MIRRORED NEIGHBORHOOD FIDELITY
In order to connect local explanations to generalization, recall that we study a measure of local interpretability which we call "mirrored neighborhood fidelity" (MNF). As we explain below, this quantity comes from a slight modification to an existing metric for local approximation explanations, namely, that of neighborhood fidelity (NF).
To define these quantities, we use the following notation. Let X' be an input space and D be a distribution over X x y' where y C R. Then, let F be class of functions ʃ X y. For our theoretical results, we specifically assume that ) is bounded as y = [-B, 3 B] for some B > 0 (though this does not matter for the remainder of this section). In order to provide local explanations, we need to fix nearby region around each E X. To this end, for any let N₂ correspond to some distribution denoting a local neighborhood at x (e.g. typically chosen to be a distribution centered at .r). For any distribution N, we use (x) to denote its density at z. Finally, let g be a class of local explainers g : X x X + y such that for each x E X. the local explanation g(x, X + ) belongs to class of (simple) functions (e.g. linear), Glocal- For convenience, we denote g(x,, as g. and use it to locally approximate ff in the neighborhood defined by Nz.
The accuracy of the local explanation system g is usually quantified by term called "neighbhorhood fidelity" which is defined as follows (Ribeiro et al. 2016 2018, Plumb et al. 2018 2020):
NF EZND Eg [(f(²') (=()))
To verbally interpet this, let us call x as the "source" point which gives rise to a local explanation (-) and x' the "target" points that we try to fit using g. To compute NF(, .),, we need to do the
3

---

Published as a conference paper at ICLR 2021
following: for each source point z, first compute the average enror in the fit of g=(-)) over draws of nearby target points x' ~ Ng; then, to get a more overall measure of g's quality, we globally average this error across draws of the source point
D.
Now, to define MNF, we take the same expression as for NF but swap x and x' within the innermost expectation (without modifying how each variable is distributed). In other words, we sample a target point x from D and sample source points x' from a distribution over points near a given T. Since this local distribution is over source points rather than target points, just for the sake of distinguishing, we'll refer to this as mirrored neighborhood distribution and denote it as N We define MNF more formally below, following which we explain how better understand it:
Definition 3.1. (Mirrored Neighborhood Fidelity) We define MNF F x G + R Ras
MNF(J,9) :- EEZD EE' [(((x) - 92 (x))
and with an abuse of notation, we let MNF g. : BTT [(f(x) gr (z))
Understanding MNF. helpful to parse the expression for MNF in two different ways. First, we can think of it as measuring the error in approximating every target point æ E X through a ran- domized
function Jer (-), where x' is randomly drawn from the neighborhood N A second way to parse this is in a manner similar to how we parsed NF. To do this, first we note that the expectations in MNF can be swapped around and rewritten as:
MNF gf = Er
E E [(f(=) - -())))9'(xx)))) (z))
where Dt and N suitably defined distributions (derived in Appendix A) that can be thought of modified counterparts of D and N respectively. With this rewritten expression, one read MNF like NF: for each source point (now x¹), we compute the average error in the fit of the corre- sponding local function (g (-)) over target points (z) drawn from the source's local neighborhood (NI); this error is then globally averaged over different draws of the source point (a' DD).
Why MNF? While both NF and MNF are closely related measures of local explanation quality on f- studying MNF allows us to make connections between local explainability and different notions of generalization (Sections 4 and 5). At high-level, our results don't It apply to NF because the overall distribution of the points that are "fit" to calculate NF (i.e., the target points) is not the same as the test data distribution D, instead being D perturbed by Nz. Rather, we prefer this target distribution to be D, which is the case for MNF, for us to be able to neatly bound test-time quantities via a local explainability term. Otherwise, we would have to end up introducing many cumbersome terms.
Furthermore, MNF may also be of practical interest to the interpretability community, as it poten- tially offers a unique advantage over NF when the intended usage of local explanations is centered around understanding how f works on the specific learning task it was trained on. Specifically, we present as exploratory argument that selecting the target point distribution be D rather than D perturbed by N₂ (as for NF) may better emphasize the ability of to approximate f at realistic input points. This relevant for ML (and deep learning especially) because (a) high- dimensional datasets often exhibit significant feature dependencies and adherence to lower dimensional manifolds; (b) can often be highly unpredictable and unstable when extrapolating beyond training data. Thus, when one measures NF with standard neighborhood choices that ignore feature dependencies (e.g- most commonly N₂ = [zz of)), the resulting target distribution may concentrate significantly on regions that are non-relevant to the original learning task at hand. As we illustrate in toy example, this can lead to overemphasis on fitting noisy off off-mmnif behavior, deteriorating the fit of explana- tions relative to task-relevant input regions (we defer more detailed discussion of this point and of other trade-offs between NF and MNF to Appendix A).
4 GENERALIZATION OF MODEL. PERFORMANCE VIA MNF
The generalization error of the function f is typically bounded by some notion of the representational complexity of F.. While standard results bound complexity in terms of parameter count, there is theoretical value in deriving bounds involving other novel terms. By doing so, one might understand how regularizing for those terms can affect the representation capacity, and in turn, the generalization
4

---

Published as a conference paper at ICLR 2021
error f. Especially when f's complexity may be intractable to bound on its own, introducing these terms provides a potentially useful new way to understand f's generalization.
Here specifically. complexity and the local explainability of any f. This naturally requires coming up with notion that appropriately quantifies the complexity of G. which we discuss in the first part of this section. As we shall see, G's s complexity can be expressed in terms of Goeat which is generally less complex and more amenable to standard analysis than F in practical settings where interpretability is desired. In the second part, we then relate this quantity to the generalization of f to derive our first main result.
interested in establishing a general connection between the representation
Key technical challenge: bounding the complexity of g. The overall idea behind how one could tie the notions of generalization and local explainability is fairly intuitive. For example, consider a simplified setting where we approximate f by dividing X' into K disjoint pieces, i.c. neighborhoods, and then approximating each neighborhood via simple (say, linear) model. Then, one could bound via
the generalization error of f as the sum of two quantities: first, the error in approximating the piecewise linear model, and second, a term involving the complexity of said piecewise model. is straightforward to show that this complexity term grows polynomially with the piece-count, K, and also the complexity of the simple local approximator (see Appendix C.O.T). Similarly, one could hope to bound the generalization error of f in terms of (fF(f.g) and the complexity of g. However, the key challenge here is that the class G is much more complex class than the above class of piecewise linear models. For example, a straightforward piece-count- based complexity bound would be infinitely large since there are effectively infinitely many unique pieces in g.
Our core technical contribution here is to bound the (Rademacher) complexity of G in this more flexible local explanation setting. At a high level, the resulting bound (to be stated shortly) grows inversely with "the level of overlap" between the neighborhoods (NTir I E X), quantified as:
Definition 4.1. (Neighborhood disjointedness factor) Given dataset S E (X x y)"", we define the neighborhood disjointedness factor Ps as
m Σ (P (x))
PS
Understanding the disjointedness factor. As can be interpreted as bounding the "effective num- ber" of pieces induced by the set of neighborhood distributions {Nmir x E X}. This turns out to be a quantity that lies in [1, /m] (shown formally in Appendix Fact B.I. To reason more intuitively about this quantity, it is helpful to consider its behavior in extreme scenarios. First, consider the case where Aimir is the same distribution (say N) regardless of æ; i.e., neighborhoods are completely s overlapping. Then, Ps = ex (pN (x)))((()))))))))) dd') = 1. In the other extreme, consider if neighborhoods centered on the training data are all disjoint with supports XT, X1s). Here, the integral splits into m summands as: ps= = Σm Ex P (x')dx = /m. Thus, Ps grows from 1 to ym as the level of overlap between the neighborhoods Nymir 2i ....., Niir reduces. For intuition at non-extreme 2sss
values, we show in Appendix B.2 that simple setting, p Vm!- (where ke < 1) if every neighborhood is just large enough to encompass a 1/m² fraction of the mass of D.
Rademacher complexity of G. We now use ps bound the empirical Rademacher complexity of G. Recall that the empirical Rademacher complexity of a function class H. consisting of h X - IR is defined as R&s := E, [+ suPMEи o,h(x;)]. where the a.'s are i.i.d. and drawn uniformly from {-1, 1}. Roughly, this captures the complexity of H. by measuring how well it can fit random labels. Standard results allow to then use (H) to bound the generalization error for h H.
Now, in order to define the Rademacher complexity of G (which consists of a different kind of functions whose domain is X x X' instead of A²), it is useful to think of randomized function. Specifically, at any target point æ, the output of g is random variable gæ' (x) where the randomness comes from x' ~ Nmmrr_ Then, in Lemma 4.1 we take this stochasticity into account to define and bound the complexity of G. To keep our statement general, we consider a generic loss function L IR R- + R (e.g., the squared error loss is L(y, y/) ) (μ - )))²). Indeed, whenever L satisfies a standard Lipschitz assumption, we can bound the complexity of g (composed with the loss function L) in terms of ps. the complexity of Grecats and the Lipschitzness of L:
5

---

Published as a conference paper at ICLR 2021
Lemma 4.1. (see Appendix Lemma D.1 for full, precise statement) Let L(-35)) be c-Lipschitz function w.r. yf in that for all y/, V2 E empirical Rademacher complexity of G under the loss function L is defined and bounded as:
L-B, B). [L(y../) - L(y2. y²)l I cly1-130 yy2l- Then, the
1 m
== Egg
sup GEG m.
Σ
of w'
o.
( (zx). 50 (cppsRs Inm)
where ō is uniformly distributed over
{ 1-
We note that the proof technique employed here may be of independent theoretical interest as it pro- vides novel way to bound the complexity of a (particular type of) randomized function. Although techniques like PAC-Bayes provide ways to bound the complexity of randomized functions, they only apply to functions where the randomization comes from stochasticity in the parameters, which is not the case here.
Main result. With the above key lemma in hand, we are now ready to prove our main result, which bounds the generalization error of f in terms of the complexity of G, thereby establishing connection between model generalization and local explainability.
Theorem 1. (see Appendix Theorem Jor full, precise stalement) With probability over 1 - å over the draws of S = (111))))... (Im: (mm) D for all J E F and for all g E G, we have (ignoring In 1/8 factors):
m ((..)>>(([())) y) (s(x)) vi)² + +2EE [ Nmr [([(x) - (x))
m
MNF(f.9)
4 Nmir (f(x))--att Dw (x:)) +
m).
MNF(f.9.2.)
This result decomposes the test error of f into four quantities. The first quantity corresponds to the training eиror of on the training set S. The second and the third correspond to the MNF of with respect to g. computed on test and training data respectively. The fourth and final quantity corresponds to term that bounds the complexity of G in terms of the "disjointedness factor" ps and the complexity of the local function class Greeal-
Takeaway. A key aspect of this bound is the trade-off that it captures when varying neighborhood widths. Consider shrinking the neighborhood widths to smaller and smaller values, in turn creating less and less overlap between the neighborhoods of the training examples in S. Then, on the one hand, we'd observe that the complexity term (the fourth term on the R.H.S) increases. Specifically, since (9woaa) typically scales as (m). as we go from the one extreme of full overlap to the other extreme of complete disjointedness, the complexity term inereases from ((1//m) to (1). At this upper extreme, the bound becomes trivial, as such a constant upper bound would directly follow from just the ((1) bounds assumed on V On the other hand, the widths decrease, the fidelity terms (the second and third terms) would likely decrease this is because the simple functions Groca would find increasingly easier to approximate on the shrinking neighborhoods.
This trade-off is intuitive. A function ff that is hardly amenable to being fit by local explanations would require extremely tiny neighborhoods for Goeat to locally approximate it (i.e. make the MNF terms small). For example, in an extreme case, when the neighborhoods Nmir are set be point masses at .r, it trivially easy to find (t) E Giocal with no approximation error. Thus, the complexity term would be too large in this case, implying that a hard-to-interpret / results in bad generalization. On the other hand, when f is easier interpret, then we'd we'd expect to be well-apprrximated by Grocal even with wider neighborhoods. This allows one to afford smaller values for both the complexity and MNF terms. In other words, an easy-to-interpret f enjoys better generalization guarantees.
Caveats.
Our bound has two limitations worth noting. First, for high-dimensional datasets (like image datasets), practical choices of N can lead to almost no overlap between neighborhoods, rendering the bound trivial in practice. This potentially poor similarly shared by bounds for non-maramttric local regression, whereby increasing d results in an exponential increase in the required sample size (Fan 1993 Fan & Gijbels 1996). Nevertheless,
is caveat

---

Published as a conference paper at ICLR 2021
show later in our experiments that for lower-dimensional datasets and for practical choices of N there can be sufficient neighborhood overlap to achieve values of ps that are of mm)
A second caveat that the second quantity, MNF 9). requires umlabeled test data to be computed, which may be limiting one is interested in numerically computing this bound in practice. It is however possible to get bound without this dependence, although only the test error of g rather than f (see Appendix Theorem 4). Nevertheless, we believe that the above bound has theoretical value in how it establishes a connection between the interpretability of f and its generalization.
5 GENERALIZATION OF LOCAL EXPLAINABILITY
We now turn our attention to more subtle kind of generalization that is both unstudied yet impor- tant. Typically, the way 9-' is learned at any source point x' is by fitting a finite set of points sampled near x', with the hope that this fit generalizes to unseen, neighboring target points. Naturally, we would want to ask: how well do the explanations Jz' themselves generalize in this sense?
This question is straightforward to answer in settings like for LIME (Ribeiro et al., 2016). For instance, assume that we learn Sx' by sampling set Sy of points from a Gaussian centered at x', and that we care about the fit of 9x' generalizing to the same Gaussian. Here, we can make a standard arugment based on Rademacher complexity to bound the error of ge on the Gaussian by its training error on Sgr and (....999aa We can apply the same argument individually for the explanation at each source point z', because have fresh dataset S to generate each Ja-- If one has the resources to sample more points to create larger Sz,, then these bounds will also naturally tighten.
However, consider finite sample-based local explanation settings like MAPLE (Plumb et al. 2018) and RI.-LIM (Yoon et al. (219) where the training procedure is vastly different: in these procedures, the goal is to learn local explanations Ou' in way that is sensitive to the local structure of the (unknown) underlying data distribution D. So, instead of fitting the 9x- to samples drawn from an arbitrarily defined (e.g. Gaussian) distribution, here one first draws a finite sample S from and then labels it using f. Then, across all x' E X, one reuses the same dataset S, but learns each Ir on a correspondingly reweighted version of S (typically, points in that are nearer to x' are weighted more heavily). Contrast this with the former setting, where for each x', one has access to fresh dataset (namely, Sz') to learn 9z', This distinction then makes interesting to wonder when the reuse of common dataset S could cause the explanations to generalize poorly.
Motivated by this question, we present Theorem 2 By using Lemma 4.1 we provide a bound on the "test MNF" (which corresponds to the fit of 92' on the unseen data averaged across D) in terms of the "train MNF" (which corresponds to the fit of gx. on S) and the complexity term from Lemma We must however caution the reader that this theorem does not answer the exact question posed in the above paragraph; it only addresses it indirectly as we discuss shortly.
Theorem 2. (see Appendix Theorem fuul for full, precise statement) For a fixed function J. with high probability 1 d over the draws of S D) for all g E G, we have (ignoring In 1/8 factors):
E. D.DD
[(((x) Dn (x))) N' Test MNF Le.. MNF(S.9)
B Naw (((xx) - I (x:))²]
In
Train MNF
Understanding the overall bound. We first elaborate on how this bound provides an (indirect) answer to our question about how well explanations generalize. Consider a procedure like MAPLE that learns g using the finite dataset S. For each x' X, would expect this procedure to have learned a 9x' that fits well on at least those target points x in S that are near x'. In doing so, it's reasonable expect the training procedure to have implicitly controlled the "train MNF" term. The reasoning for this is that the train MNF computes the error in the fit of 9x' on S for different values of x', and sums these up in way that errors corresponding nearby values of (z, x²) are weighted more (i.e., the weight is given by prms (z')). Now, our bound suggests that when the train MNF is minimized, this carries over to test MNF too, provided the complexity term is not large. That is, we can say that the fit of gr generalizes well to unseen, nearby target points x that lie outside of S.
7

---

Published as a conference paper at ICLR 2021
The indirectness of our result. Existing finite sample-based explainers do not explicitly minimize the train MNF term (e.g., MAPLE minimizes an error based upon NF). However, as argued above, they have implicit control over train MNF. Hence, our bound essentially treats MNF as surrogate for reasoning about the generalization of the explanations learned by an arbitrary procedure. As such, our bound does not comment how well the exact kind of fidelity metric used during training generalizes to test data. Nevertheless, we hope that this result offers a concrete first step towards quantifying the generalization of local explanations. Furthermore, we also note that one could also procedure that does explicitly minimize the train MNF term
imagine novel explanation-leariine to learn g; in such a case our bound would provide a direct answer to how well its explanations generalize. Indeed, we derive such theoretically-priicippe
algorithm in Appendix A
Takeaway. While the above bound captures a similar trade-off involving neighborhood width as Theorem [] it is worth pausing to appreciate the distinct manner in which this trade-off arises here. In particular, when the width is too small, we know that the complexity term approaches (11) and generalization is poor. Intuitively, this is because in this case, the procedure for learning In would have been trained to fit very few datapoints from S that happened to have fallen in the small neighhorhood of x'. On the other hand, when the neighborhoods are large, many datapoints from S are likely to fall in each neighborhood, thus allowing each 9a- to be trained on an effectively larger dataset. However, with large neighborhoods, it may also be hard to find functions in Greaa that fit so many points in S. Overall, one practical takeaway from this bound is that it is important to not excessively shrink the neighborhood widths if one wants explanations that generalize well for predicting how f behaves at unseen points (see Section 6
Caveats. We remark that this particular bound applies only when the dataset S is solely used to learn gi i.e., both f and the neighborhoods must be learned beforehand with separate date] This sort of framework typical when deriving theoretical results for models like random forests, where it greatly aids analysis to assume that the trees' splits and their decisions are learned from independent datasets (e.g. two halves of an original dataset) (Arlot & Genuer 2014). Now, if one interested in a bound where S is also used to simultaneously learn J' one would have to introduce a term corresponding to the complexity of F. Another caveat is that our bound only tells us how average over different values of x'. This does not tell us
well the explanations 9r' generalize anything about the generalization of the quality of Jx' for an arbitrary value of x'. That being said, just average accuracy remains central metric for performance (despite its lack of sensitivity to discrepancies across inputs), average MNF can still be a useful quantity for evaluating an explainer's overall performance.
6 EMPIRICAL RESULTS
We present two sets of empirical results to illustrate the the usefulness of our bounds. First, we demonstrate that ps grows much slower than Ovym) which, as stated before, establishes that our bounds yield meaningful convergence rates. Second, we show that Theorem [ accurately reflects the relationship between explanation generalization (Theorem 2 and the width of Nmmr used to both generate and evaluate explanations.
Setup. For both experiments, we use several regression datasets from the UCI collection (Dua & Graff, 2017) and standardize each feature to have mean 0 and variance We train neural networks as our "black-box" models with the same setup as in (Plumb et al., (020). using both their non- regularized and ExpO training procedures. The latter explicitly regularizes for NF during training. which we find also decreases MNF on all datasets. For generating explanations, we define Gloca to be linear models and optimize each In using the empirical MNF minimizer (see Appendix A) Finally, we approximate ps using provably accurate sampling-basee approach (see Appendix E
Growth-rate of ps. In Figure [ (top), we track the sample dependence of ps for various neigh- borhoods of width setting N N(x We specifically approximate the growth rate as polynomial, estimating the exponent by taking the overall slope of a log-log plot of ps over m. To cover natural range for each dataset, is varied to be between the smallest and half the largest inter-example la distances. In these plots, while small a result in a large exponent for ps and large
Pt is due to this reason that we can't plug Theorem into the right hand side of Theorem I (in which f depends on S) to replace its MNF term with train MNF term.
8

---

Published as a conference paper at ICLR 2021
Autompgs (d-7, [5]-
Housing (d-21, [S]
[5]
poynere Croath Satee
(eyyemme Crowtth 8ate
0.1
Polynoma Growth
0.3
2.
30
13
100
12.
15.0
Te covile) 2e0l
0112
Toe 1orle
1.000
0030
6435
20000
0000
25
3.0
03
10.0
32.5
15.0
37.5
heignborhood Size
Neggioorioee SiDr:
Neigh highborneddd Sizee
Approximate exponent of ps's polynomial growth rate (top) and train/test MNF (below) plotted for various neighborhood widths across several UCI datasets (see Appendix for more).
Figure 1:
cause g to intuitively saturate towards global linear model, observe that there do exist values of where both these terms are in control i.c., we observe that we can achieve a growth rate of approximately (m) without causing g to saturate and MNF metries rise sharply.
Generalization and neighborhood size. As per the setting of Theorem 2 we generate all explana- tions using data not used to learn the black-box model. Specifically, we split the original test data into two halves, using only the first half for explanation training and the second for explanation testing. We plot MNF as measured over these two subsets of examples in Figure [ the results, it is evident that generalization gap between train and test MNF exists. Further, recall that Theorem 2 predicts that this gap decreases as wider neighborhoods are used, phenomena re- flected in most of these plots. As a result, while training MNF monotonically increases with larger neighborhoods, test MNF always decreases at certain ranges of o.
(bottom). From
7 CONCLUSION AND FUTURE WORK
In this work, we have studied two novel connections between learning theory and local explanations.
We believe these results may be of use in guiding the following directions of future work: (1)
developing new local explanation algorithms inspired by our theory and the metric of MNF; (2)
resolving caveats otherwise strengthening the theory presented in this paper; and (3) exploring applications of our techniques beyond interpretability, such as the general problem of deep learning generalization or others that require reasoning about the complexity of randomized functions.
ACKNOWLEDGMENTS
This work was supported in part by DARPA FA875017C0141, the National Science Foundation grants I1S1705121 and ISS183017, an Okawa Grant, a Google Faculty Award, an Amazon Web Services Award, Morgan A.I. Research Faculty Award, and a Carnegie Bosch Institute Research Award. Vaishnavh Nagarajan was supported by grant from the Bosch Center for AI. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of DARPA, the National Science Foundation, or any other funding agency.

---

Published as a conference paper at ICLR 2021
REFERENCES
Sylvain Arlot and Robin Genuer. Analysis of purely random forests bias, 2014.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. volume 80 of Proceedings of Machine Learning Research, pp. 263, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL
ics. uci. edu/ml
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 of the Thirty-Third Conference Uncertainty in Artificial Intelligence, UAI 2016. 2017.
Jianqing Fan. Local linear regression smoothers and their minimax efficiencies. Statistics, 21, 03 1993. doi: ////4/////173440000
The Annals of
Jianqing Fan and Irène Gijbels. Local polynomial modelling and its applications. Number 66 in Monographs on statistics and applied probability series. Chapman & Hall, London [u.a.], 1996.
ISBN 0412983214.
John Langford and Rich Caruana. (Not) bounding the true error. In T. G. Dietterich, S. Becker, and Z. Ghahramani (eds.), Advances in Neural Information Processing Systems /4, pp. 809-816. MIT Press, 2002.
John Langford and John Shawe-Taylor Pac-bayes & margins. In S. Becker, S. Thrun, and Ober- mayer (eds.), Advances in Neural Information Processing Systems 15, pp. 439-446. MIT Press, 2003.
David McAllester. Simplified pac-bayesian margin bounds. In Bernhard Schölkopf and Manfred K. Warmuth (eds.), Learning Theory and Kernel Machines, pp. 203-215, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. ISBN 978-3-540-45167-9
David McAllester. Some pac-bayesian theorems. In 1 11th annual conference on Computational learning theory, 1998.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning. In Advances Neural Information Processing Systems 32, pp. 11615- 11626. Curran Associates, Inc., 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning, 2014. URL hwt.hhtsss//rrii..r////////////e
6614
Gregory Plumb, Denali Molitor, and Ameet S Talwalkar. Model agnostic supervised local expla- nations. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 2515-2524, Curran Asso- ciates, Inc., 2018.
Gregory Plumb, Maruan Al-Shedivat, Angel Alexander Cabrera, Adam Perer, Eric Xing, and Ameet Talwalkar. Regularizing black-box models for improved interpretability, 2020. URL https:
//axxiv.rrg/as///// 902. 06787
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should trust you?": Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1135-1144. ACM, 2016. 2016.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High- precision model-agnostic explanations. In AAAI Conference on Artificial Intelligence. 2018. URI kattps://www. aaai.
org/ocs/ itt///ndxxxxx http://iinexxppppp/paaaaa wwtppppppp...aa.. AAAI wtt./////pppp////e/////p 16982
Lesia Semenova, Cynthia Rudin, and Ronald Parr. A study in rashomon curves and volumes: A new perspective on generalization and model simplicity in machine learning, 2020. URL https:
// 7/arxive v. wwwp://ggaaaaaaeeo 908. 908.01755
10

---

Published as a conference paper at ICLR 2021
Shai Shalev-Shwarte and Shai Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014.
Jinsung Yoon, Sercan O. Arik, and Tomas Pfister. RL-LIM: Reinforcement learning-based locally
interpretable modeling, 2019. URL URL httpe///aaxxii..orr////////0...
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.

---

Published as a conference paper at ICLR 2021
A MORE ON MIRRORED NEIGHBORHOOD FIDELITY
A.1 AN ALTERNATIVE INTERPRETATION
Here elaborate how the expression for MNF be parsed in the same way NF after juggling some terms around. Recall that MNF is defined as:
(NF(J.9) EgND
BEgtNNgt [([(x) 9r (x))
and with an abuse of notation, we let MNF = Nmi [[f(z) - gr (z))²].
Here the outer expectation is over the targer points that the explanations try fit, and the inner expectation is over the source points which give rise to the explanations gz²
If we can swap these expectations around, consider the joint distribution over x and x' that is induced by generating x ~ and then picking x' Nmir Under this joint distribution, need an expression for the marginal distribution of x'. This distribution, which we denote by DJ, is given by:
afford a similar parsing as NF. To get there, first
PDr (x') = / pD (z) Jzz
To get sense of what DI looks like, imagine that N is Gaussian centered at x. Then DI corresponds to convolving with a Gaussian i.e., a smoother version of D.
Next, under the same joint distribution, also need expression for the distribution of condi- tioned on x'. This distribution, denoted as Nj. is given by:
PD( (x') Pxt, (x)) Jx ( (x')dx
Intuitively, NI, is distribution that is centered around x' and is also weighted by the distribution D ie., points that both close to x' and realistic under D have greater weight under N This is because the term Pw (x') in the numerator prioritizes points that near x' (imagine N being Gaussian centered at æ), and the term (D( prioritizes realistic points.
With these definitions in hand, we can swap the expectations around and get:
MNF(J.9) = BR'nDt
B BENN [((()) g- (z))
This then has the same structure NF in that the outer expectation is over the source points and the inner distribution over target points, and hence can be interpreted similarly. The key insight here is that from the perspective of each individual explanation Js', the relevant distribution it needs fit (to achieve low MNF) N which takes into account both the local neighborhoods and the real data distribution D. In comparison, only the former matters for NF.
A.2 ALGORITHM FOR MINIMIZING EMPIRICAL MIRRORED NEIGHBORHOOD FIDELITY
We now consider how one might actually fit explanations to minimize MNF. Recall from the above discussion that from the point of view of each source point x', MNF measures how well gu' fits on Pn (x)) weg (x')
the distribution with density PNt, (x) Jx (o( jor (w')d= Note that one generally does not have access to samples from this distribution due to the dependence on D. However as we argue, one can minimize the empirical version of MNF given access finite sample S drawn i.i.d. from D by solving the following weighted regression problem:
Ies arg min
Σ (f(,)) - Ird
92 EGucal S
To see what the empirical version of MNF is, we can replace the outer expectation (over x ~ D) in the original definition of MNF with empirical expectation over S {=:) giving
12

---

Published as a conference paper at ICLR 2021
[8]
Empirical MNF
N [(](as) Dw (2x)))
[S|
/ -
- Gr (2:))
(a:)) ydx
S
S (f(x)) - gr (x:))) P (x') ydr'
To minimize the overall empirical MNF, one can thus choose a far for each x' such that minimizes the above integrand, which is akin to performing one weighted least squares regression. Thus, one notable difference between minimizing empirical MNF and NF that we need to use real examples to fit 9x for MNF but not for NF since the target distribution of interest there can be user-defined (i.e. it may be chosen such that it can be easily sampled from).
A.3 TRADE-OFFS BETWEEN MNF AND NF
We now discuss in further detail the comparison between MNF and NF, listing both the relative advantages and disadvantages of each. It should be noted that this discussion is of somewhat more exploratory nature; we do not aim to make definitive value judgments (i.e. one metric is always more useful than the other), but rather to provide better qualitative understanding of how these two metrics might be expected to behave. We hope that this discussion prompts a more careful consideration of fidelity metrics in future works involving local explanations.
A.3.1 ADVANTAGES OF MNF
In many practical situations (esp. for i.i.d. cases), it is reasonable to assume that practitioners will care significantly about generating explanations for predictions at realistic on-distribution points and hoping that those (local) models correctly approximate what the model will do at nearby points which are also realistic. Our core argument for the usefulness MNF compared to NF that can be used to come closer to characterizing performance relative to the second part of this goal (i.c. predicting what the model will do at realistic points).
To reiterate Section this is an especially important concern for modern ML settings, which often involve significant teature dependencies (i.e. lower dimensional data manifolds) and models that behave unstably when extrapolating beyond the given task and training data. As illustrate below in a toy example, when one uses NF with standard neighborhood choices that don't I respect data dependencies (e.g. N₂ (O, a [)), one may overemphasize the ability of explanations to fit this noisy behavior on regions that are off-manifold
Toy example. We compare the abilities of MNF and NF to serve the basis for generating local explanations. In what follows, we refer to N and MNF as the linear local explainers that minimize NF and MNF respectively. We specifically consider simple setup where the full input space has dimension d = 2 but the data exists on manifold of dimension & = 1. Under task distrribtti D, let 21 ~ A (0, 1) while 22 may assume 3 > 0. As an important note, on the task distribution D, f is functionally equivalent fairly simple function, i.e. f(x) = zT.
Further consider the learned model (x: = 21 f3 where one
Minimizing NF: To learn df we may simply sample many x' N₂ and find linear NF (-) that fits these points well. Now, we can expect this process to generalize 9x (z²))² is minimized. In fact, one could consider the ideal scenario where we sample infinitely many unlabeled examples, and thus find the best possible linear approximation given this neigh- borhood distribution. However, observe that minimizing the above quantity provides absolutely no guarantee whatsoever regarding the error committed on D ie.. (ff because D has zero measure when considering X = RR. This means that if is arbitrarily volatile along the irrelevant In direction, Ia. can also be arbitrarily incorrect on D. Indeed, this is the case in the setting above. Letting g (x')) = wory + w2rh and N, N(O, 7), it be shown that
way that Eg [((();)
(x')))) This is
13

---

Published as a conference paper at ICLR 2021
NF g.) is minimized by wi -1-3 3. Since can be arbitrarily large, this explanation can be unboundedly poor at recovering a function equivalent to f()) = 21 on D. Indeed, it can even get the sign of the coefficient for the active feature 21 wrong when 3 >> 1.
Minimizing MNF; Note that none of the above a problem when we learn MNF because we fit each J. only on target points that are from the real data manifold. F This will ensure that g MMF is in line with a potentially important desiderata for local explanations i.c., that they can faithfully capture function that is accurate along the task-relevant data directions (of course, only up to linear approximation). To illustrate more completely, recall that g MNF is learned as follows: assuming access to S {01...., Imj D we have
m Σ (f(x;) - gr (x:)) Px
MNF 9x"
arg min
Eluce
m
Now since S lies on the manifold of D, we have that x2 = 0 on all those points. Therefore, for each I, find the solution which minimizes
m
MNF Des
arg min
Σ (4,1 7
1 (x')
WIER
is easy to see that with just two distinct datapoints from S, we would recover w1 = 1, which leads to perfect predictions for how the function behaves on D.
As a remark, an even more natural version of the above setting would be one where f is non-linear even on the data manifold. But even here possible linear function within the manifold up to a 1/ ///m error (e.g., a generlization bound like our Theorem guarantees this average over x). On the other hand, regardless of how many unlabeled datapoints we fit g with, we would learn g NF that can behave arbitrarily poorly on the manifold.
still argue that g MNF would be close to the best
A.3.2 LIMITATIONS OF MNF
Below, we discuss some limitations of MNF as well as potential future directions for possibly ad- dressing them. At high-level, we believe while each represents legitimate concern, they may arguably be (depending on context) "reasonable prices to pay" for the advantages of MNF com- pared to NF described previously.
MNF explanations may lose local meaning: Using MNF to evaluate/generate explanations at low- probability source points z' may have little do with how f actually behaves around x'. Because the target point distribution is æ//2 & PD (z)P., (x'), very little probability mass might be placed in PD(ppD)) the vicinity around x' when (D( is small. This would be the case when is off-manifold or in low-density regions on the support of the real data distribution. The former might be dismissable if one cares about i.i.d. settings (which not always the case) but the latter could be very important in applications where cases correspond high-stakes decisions (e.g. disease diagnostics). In these scenarios, the explanation might still be too biased towards how the model is behaving at higher density regions. However, some potential future directions remedy this are:
It might help to allow Nmir to have smaller width around lower probability points from D (allowing one to concentrate Niir around x despite the form of D). It remains challenge to see how one would actually set these widths but it could be of help if a limit can be assumed on how quickly the value (xr) are allowed to change around given x.
There also could be some utility in considering more general definition of MNF that lets one choose an arbitrary outer distribution x ~ Q other than simply the task distribution D. That is, if one really cares about mutually consistent explanations in some arbitrary region (which could be on or off mafifonnf,,d), then this would potentially allow one to able customize metric for that purpose.
'Recall notation-wiss that NF and MNF swap the usage of x and x' for target points. Thus, when comparing MNF how individual explanations generated and evaluated, we refer to them as g.. and NF respectively.
14

---

Published as a conference paper at ICLR 2021
Less intuitive target point neighborhoods: Very closely related the previous limitation, in interpreting MNF-based explanations, an end-user would have to understand that 9x are not exactly approximations for the locality around z' but rather for the true target distribution that captures in some sense "on-manifold points near x' (modulated by the concentration of N )." This makes harder for user to know the exact window in which their explanation is directly valid for (compared to a user-specified target neighborhood for NF). In practice, this shortcoming could be at least partially mitigated as long is carefully communicated they should focus on using MNF explanations only at and for predicting what happens at realistic points.
users that this limitation exists, i.e.
Unnaturalness of source points: While MNF does emphasize realistic target points, it also focuses on explanations generated potentially off-manifold source points. Further, one could argue that the advantages of MNF are partly because N₂ is chosen naively for NF. For instance if one defined N₂ Nt in the definition for MNF, then g and /NF would produce the same explanations because the relevant (inner) expectations would be the same (comparing NF and the reversed expec- tation form of MNF from Appendix A.I)). However, in this proposal, now the average metric for NF seems more natural in additional sense since it also only reflects caring about ensuring realistic source points (as the outer expectation is over x ~ D).
NF = RE a' [x))((")- [(x'))² BE
MNF = E Egg'-D D BENNY, [x(g - [(x)]?
Given these two points, might MNF be less interesting on its own? For the first point, we argue that using standard "naive" settings of N₂ with NF can also be considered "unnatural" in that it takes into account how explanations at on-manifold source points perform at off-manifold target points. Second, though the specification NF proposed above may be more ideal as a metric, it also becomes less clear how to evaluate it computationally, as the inner distribution cannot be sampled from easily. On the other hand, can the original form of writing out MNF (without the expecations flipped) to directly approximate MNF with relevant samples from D.
Inability to reflect what the model "causally" depends on: In the second toy-example, it was shown that if f(x) = I _x,,, = but the data manifold is (2) = (.) one could get arbitrarily poor fidelity and feature relevancy (for xι) on this manifold using standard neighbor- hoods. But MNF runs into a new problem when the feature set actually includes a highly cor- related third feature: for example, consider (a11, 12, where the manifold is defined by points (I1, 22) = (,1,0, 0, Thus according to MNF, g(x) F1 + 2x3 are all equally good explanations (because MNF only cares about whether g(x) = f(x) on manifold). However, the output of f clearly only "depends" on the input value of T1 for its decisions (in a causal sense). On the other hand, because NF samples target points both on and off manifold, it would correctly see that 2y has no effect. More broadly, the argument here is that in any conversation involving manifolds, one inherently is speaking about some sort of feature dependencies. Thus, one may similarly suffer from the issues of explanations not being causal w.r.t. the output of f and also not being fully identifiable. On the other hand, we note that in the new toy-example, NF is not an ideal fix either because the cost is potentially an arbitrary coefficient for I1 and extremely poor fidelity on D. Overall, the intended usage of an explanation plays large role in whether MNF or NF is indeed appropriate. An argument could be made that finding "what the model uses for its decision"" (while perhaps an important goal) is simply not what MNF expla- nations are trying capture. What one could describe MNF as actually looking at is "can I build simpler local model relevant to the actual task at hand?"
I1. g(x) T3, and indeed
g(x)
15

---

Published as a conference paper at ICLR 2021
B MORE ON THE DISJOINTEDNESS FACTOR
B.1 BOUNDS
En (P (x)))²
Recall that the disjointedness factor is defined as ps == Jaex V show that it is bounded between and vm. Fact B.1. The disjointedness factor ps satisfies S pS S m
dr'. Here, we
Proof. For the lower bound, we note that since the arithmetic mean lower bounds the quadratic mean, we have:
Σ==1 (Pamy (x²))2
E Pamm(a'))
Jeex
da'
dx'
m
m
m
1
PN (x' ddr
m
Ja'EX'
m
j=1 m
For the upper bound, we make use of the fact that the l norm of vector is smaller than its é norm to get:
th Σラ= (D
(2'))²
Σ Prox (x')
J x'EX
dx
dx
m
x'E
vm
Parmir (x/ (x')da' )dx'
2'EX
mm
B.2 VALUES OF PS IN-BETWERN AND m
We know that the disjointedness factor Ps takes the values 1 and / in the two extreme cases where the neighborhoods are completely overlapping or disjoint respectively. We also know from Fact B.] that the only other values takes lie in between and /m. But when does take these values?
To get sense of how these in-between values can be realized, we present a toy example. Specif- ically, we can show that under some simplistic assumptions, PS Vmllk (where < k < 1) if every neighborhood is just large enough to encompass a प fraction mass of the distribution D.
Our main assumption is that Mmir a uniform distribution over whatever support covers. Further, to simplify the discussion, assume that X' is discrete set containing of M as very. very large). Our analysis should extend easily to settings where these assumptions are violated, but choose to keep these assumptions for readability.
M datapoints in total (think
16

---

Published as a conference paper at ICLR 2021
Then, if every neighborhood contains mi-x fraction of mass of the distribution D, this implies it contains M m points. Therefore, since N is a uniform distribution, we have that the probability mass of Nm on any point in its support is Mm Plugging this in the definition ps, we get:
M
( (x'))
Pr (s' xz5]
PS
x'E
i=1
1=1
M
1
I[ry E supp (N
Mm
1=1
M
Hæy E supp (Nmi
Mm
To further simplify this, we need to compute the innermost summation, which essentially corre- sponds to the number of mirrored neighborhoods that each point belongs to. For simplicity, let's assume that every point belongs to n neighborhoods. To estimate n, observe that for each of the m neighborhoods to contain M must have:
m.= points, and for each of the M points to be in neighborhoods, we
M
Mn = m
m ml
Thus, n = =m.. Plugging this back in, we get Ps = m 1
17

---

Published as a conference paper at ICLR 2021
C PIECE-WISE GLOBAL APPROXIMATION
C.O.I GENERALIZATION BOUND ASSUMING PIECEWISENESS
We now discuss the Rademacher complexity of simpler class of local-approximation functions: a class of piecewise-simple functions 9 9 with pieces. In partieular, one can show that the complexity of these functions grows with K vK.
To see why, first let us call the K disjoint regions that g is defined over Ri...., Rx. Correspond- ingly, the original training set S {xx)] ) can be divided into subsets S { Sp.
(TK.. ) ie that happen to fall into the respective regions and the pieces of are .1..... 9K E Mocal
are simple functions. Then, one can split the Rademacher complexity over the whole datasct in terms of these subsets, get:
Rs(
Eg
sup
org()))
gEG
K
EE
sup
m
01g (z; 114 S₁}
m7
k=
TR
E
sup
1/kk
Th. (Fks))
gEs
m
m,
K
mi E,
sup
Sh. (1tb)
9 E
km
m& Rs. (Gucal)
Now, assuming each R.s (Grocat) O Vimes
in the worst-case, each subset has the same number
of points me mm/ K, the sum in the last expression can be bounded as O K
18

---

Published as a conference paper at ICLR 2021
D PROOFS
Below, we present the full statement and proof of Lemma 4.1 which bounds the Rademacher com- plexity of G. The main difference between this statement and the version in the main paper that we replace the Rademacher complexity of Gocaa with slightly more carefully defined version of
defined below:
2
Rig (Glccl)
= max i5m TCS,
max
(I)
This quantity is essentially a bound on the empirical Rademacher complexity of Geeal on possible subsets of S, with an appropriate scaling factor.
We note that although this quantity is technically larger than the original quantity namely Rs (hocal)))) for all practical purposes, is reasonable to think of R'g as being identical R.s (loall modulo some constant factor. For example, if we have that for all h E Glocat, h(x) = w x where
||ll22 2 a, then one would typically bound (9 by O Lay VV |kx.l//m
The bound on
V/m
Rig (Giccl) however would resolve to a /max:sm || v/m
Now, as long as we assume that |>y|||
all bounded by some constant, both these bounds are asymptotically the same, and have the same 1/ /mm dependence on m. Additionally, we also remark that that it is possible to write our results in terms of tighter definitions of R3g (9rcca)) however our statements read much cleaner with the above definition.
Lemma D.1. (full, precise statement of Lemma 4.1 Let I(::y/) be c-Lipschitz function w.r.t y in that for all y1,32 E I-B, B}, [L(vi.3)) L( < clui - y2l. Let S {(11, Br..... (Ims 3m)} (X' &yymm Then, the empirical Rademacher complexity of under the loss function L is defined and bounded as:
( = =E
sup DEG
1
Σ
oi w' Nmw [[g (F:)), will < cps(In 1) (9tcaa))
m
D (P (x'))² da' the disjointedness factor.
where recall that ps == Sarex
Our high level proof idea is to first construct distribution D over X' such that each of the inner expectations over Amir (for each i) can be rewritten as an expectation over x' ~ D. This removes the dependence on from this expectation, which then allows us to pull this expectation all the way out. This further allows us to take each s' and compute Rademacher complexity corresponding the loss of a single local explanation function Ja', and then finally average that complexity over x' D.
Proof. We begin by noting that the inner expectations in the Rademacher complexity are over m unique distributions Amir. our first step is to rewrite these expectations in way that they all apply on the same distribution. Let call this distribution / and define what it is later. As long 5 has a support that contains the supports of the above m distributions, we can write:
Par (x')
( o o) = E,
sup gEg
Σ o (lee(())) wi
PB P)(x'))
this allows us to pull the inner expectation out in front of the summation and then the supremum (which now results in inequality):
Pa (x')
<
Eg
E
D'DD
sup 9Eg
Σ o. (x.) wz)
po ()(x²)
19

---

Published as a conference paper at ICLR 2021
which further allows rewrite the supremum to be over Geeall instead of G:
m Σ
Parii (a')
Ey
E g
sup heC
o,L((((;)) yi)
m
PD (x)
and finally, let us simply interchange the two outer expectations to rewrite the expression as:
m
PNT (x') (c')1
PD(x') ]
40 D
Ex
sup he
Σ
ozL(((Zz))))) yi)
m
What we now have an inner expectation which boils down to an empirical Rademacher complexity for fixed æ', and an outer expectation that averages this over x' D. For the rest the discussion,
P P (x')
we will fix x' and focus on bounding the inner term. For convenience, let us define w; ==
Po (w').
Without loss of generality, assume that w1 S W2 S S Wm. Also define wo = O. We then begin by expanding wi into telescopic summation:
Egg
sup hCDrca
Σ L,,(() (1)
Eg
sup hEDrea
Σ
Σ j=1
W3 W3 w--1)
m
m
then, we interchange the two summations while adjusting their limits appropriately:
Eg
sup
ΣΣ j=
u.L( wi-1)
hEGroa
and we pull the outer summation out in front of the supremum and expectation, making an upper bound:
1 ()) - Wy w)-1)
Eg
sup hEGuea
Intuitively, the above steps have executed the following idea. The Rademacher complexity the LHS can be thought of as involving a dataset with weights W1, W2. . Wm given to the losses on each of the datapoints. We then imagine decomposing this "weighted" dataset into multiple weighted datasets while ensuring that the weights summed across these datasets equal Wi, .......; Wm the respective datapoints. Then, could compute the Rademacher complexity for each of these datasets, and then sum them up to get an upper bound on the complexity corre- sponding the original dataset.
The way we decomposed the datasets is as follows: first we extract a weight out of all the m data points (which is possible since it's the smallest weight), giving rise to a dataset of m points all with equal weights W1. What remains is a dataset with weights 0, W2 W1, W3 wi....y Wm Wi. From this, we'll extract a W² w1 weight out of all but the first data point to create a dataset of m-1 datapoints all equally weighted as uh W1. By proceeding similarly, we can generate m such datasets of cardinality m, m 1, I respectively, such that all datasets have equally weighted points, and weights that follow the sequence we will eventually sum up Rademacher complexity terms computed with respect to each these datasets.
wo, W2 W1, ... and so on. As stated before,
Now, we continue simplifying the above term by pulling out (w, - w--1) since it is only a constant:
1
1
E
sup hESuaal
a:T(h((:))))
Σ ( Wi wi-1 Es
sup hESreal m
a L(((())))) vi)
772
20

---

Published as a conference paper at ICLR 2021
next, we apply the standard contraction lemma (Lemma D.2 make use of the fact h(x;)) is com- posed with a c-Lipschitz function to get:
Σ (n)()))
sup hE
using Sym denote the datapoints indexed from j to m. we can rewrite this in short as:
S e my w)-1) m + - R.s m (9tocat)
m
and finally, we make use of the definition of R (9lcal) in Equation to get:
S w w m + +
R (9lcaa).
vm
What remains now is to simplify the summation over w's. do this, we rearrange the telescopic summation as follows:
12
m
U W/ 1)-1)
w
1m+1-1
vm j)
j=1
Wij
m + I - + m -
]=1
W
Vm + -1-3
m3 (In + 1)
Note that in the penultimate step we've used the Cauchy-Schwarde inequality and the last step. have made use of the standard logarithmic upper bound on the m-th harmonic number. Plugging this back on the Rademacher complexity bound, we get:
Ris(Ciocal) mm
Rs(L L o 9) s Brnnd
Σ w3 (Inm + 1).
plugging in the values of Wj, get:
Σx (PNTr (21)22
Ris (9ieaa)
< BBnD
(Inm + 1)
(ar(x'))2
m
(P (#1))²
m
S clF FRDDD
(lam+ + 1) R9s(Ciaal))
(x)))
21

---

Published as a conference paper at ICLR 2021
(P CPame (x)))
Now we finally set D such that (z()))
where ps is a normalization constant
such that ps Sa'xx -ー= (P (2)))a
dx'. Then, the above term would simplify as:
m
Rs(L 9) cB BD (es] (Inm +1 R'g (Greca)
S cpss(lum Caamm+l +1) R2s (Sucal).
Next, we state and prove the full version of [ which provided generalization guarantee for the test error of f in terms of its local interpretability. This result follows by applying the previous lemma for the squared enror loss. For this we need to show that the squared error loss is Lipschitz, which follows from our assumption that the range of the functions in F and Gocal and also the labels y are bounded in [.B.B. B).
Theorem 3. (full, precise version of Theorem With probability over 1 - 5 over the draws of = ((I1,11),... (mm: }m)} D all j F and for all E 9, we have (ignoring 1/8 factors):
E $ 4 Σ (f(x.)) vi)² + 2 EEnDDBBe [[((x) Ios (x))
-y)
MNF(F.9)
m
g Nm [(((x;) - gr (x:))) +16Bps R (9rceal))))) m 1)
171
MNF(f.g.7.)
In 1/8
+ 2
m
where ps denotes the disjointedness factor defined as == Swex V
1 m Em (p (P (x') (2')) and
Rig (Crcca)) is defined in Equation
Proof. First, split the test error into two terms by introducing the g function follows:
[(ex))D((((x) y)31 E( Nmr (f(x) y)
S 2 Eew (Byr EE ((f(x) - 9x (x'(x)) (x)) + Ex B Ber Imrl (x)
y))11]
(2)
In the first step, we have introduced dummy expectation over x', and in the next step, we have used the following inequality: for any a, b, E R. (a - b)2 & (la fia-a cl lc-bb) < 2([a cl2 + |e b12) (the first inequality in this line is the triangle inequality and the second inequality is the root mean square inequality).
The first term on the RHS above is MNF g). To simplify the second term, we first apply generalization bound based on Rademacher complexity. Specifically, we have that w.h.p over the draws of S, for all E G,
1/8 m
Eg [er (o - y) < E Non (gg - -;) + (9) + 2
Nm
(3)
Now, (9) can be bounded using Lemma 4.1 under Lipschitzness of the squared error loss. Specif- ically, have that for h. N Glocal, and for all y E [- B3 B), ((1(z)) v)² (N'xx) y) <
22

---

Published as a conference paper at ICLR 2021
4B (x) (x)x),, since all of h(z), (z) and y lie in [- -B, Therefore, from Lemma 4.1 have that:
Rs( S 4B(In 1)ps (Giccl))
The only term that remains to be bounded the first term on the RHS. This can bounded again using
the inequality that for any a, b, E I. (a b)2 z (la c| + |c fc--b] b1)² - 2(
cf² - |c b)²):
m
E By
- -3:) )]
E (2:)
Σ (f(zi) - y1)
(5)
By combining the above three chains of inequalities, we get the final bound.
Below, we present an alternative version of Theorem D where the generalization bound does not involve the test MNF and hence does not require any unlabeled data from D; however the bound is not on the test error of f but the test error of g. Theorem 4. (an alternative version of Theorem 7 With probability over 1 - ô over the draws of and for all g E 9, have:
for ((x1, 91), .... (Tem Wm.] Dm all
m
2
m
Nm [(xx (x) E (x Nm
3))
(f(x.) - v1)
New [(f(x;) go. (2
m
m
MNF(f.g.zx)
In 1/8
+ RB +1)
V
m
Proof. The proof follows directly from the proof of Theorem 3
starting from Equation 3
We now state and prove the full version of Theorem 2 which provided a generalization guarantee for the quality of explanations.
Theorem 5. (full, precise statement of Theorem 2 For fixed function J. with high probability
1 - 8 over the draws of S ~ for all g E G, we have:
E
E Bar [U((x) Io (x:))
E Nmi [((sr.) Iot For (x:2)
Test MNF ie.. MNF(F.))
Train MNF
In 1/6
8Bps Rs Inm +
where (Qucall))) is defined in Equation
Proof. For this result, we need to think of f as fixed labeling function since it is independent of the dataset S that is used train g. Then, can apply standard Rademacher complexity bound and invoke Lemma 4.1 to get the final result (as invoked in Equation 4p.
Below, we state the standard contraction lemma for Rademacher complexity (e.g., Shalsh-Shhaar Shwartz & Ben-D (2014) Lemma 26.9). The lemma states that composing function class with a c- Lipschitz function can scale up its Rademacher complexity by multiplicative factor of at most
Lemma D.2. (Contraction lemma) For each i =.,2...., 1,2,...,77. let di R - IR be c-Lipschitz function in that for all i, t E B R, (t:(t) dx((')) < - t'). Then, for any class H of fanctions
h: IR B, we have:
Ea Σ a. (h(x))
s cEa
Σ (1(h((a))
23

---

Published as a conference paper at ICLR 2021
E EXPERIMENT DETAILS
E. PROCEDURE FOR CALCULATING Ps
As a reminder, we define ps be an integral over X. which is not trivial to evaluate in practice, especially when dealing with higher dimensional variables.
Σ (P (z')) 1=1
Ja
m
Common numerical integration techniques usually incur significant computational costs due the dimension of x. Though a variety of methods exist, one can intuit the inherent difficulty that causes this blow-up by considering the naive approach of simply constructing Riemann sum across rectangular meshgrid of points for d-dimensional X'. If one wants to create a grid of e points per dimension, then ea points (and thus evaluations of the integrand) must be processed.
Instead, we can apply Monte-Cart Integration to evaluate ps- As we will see, key feature of this approach is that eтror will not scale with data dimension and can be bounded probabilistically via basic Hoeffding bound. Currently, the integral does not take the form of an expectation so we must introduce a dummy distribution ((x") as follows
m Ex (omm((")))
Σnhh (P (s²))² m
1
g(x dd'' = Exiing
=
((x')
(x0')
J'EX
Now, we can estimate ps with n independent samples from q.
1 n n1 j=1
m Zim1
(DNTr (2())²
ssnn
(x,))
This is obviously an unbiased estimate of ps, but that in itself is not sufficient. only a feasible approach if can choose q such that (1) we can actually sample from it, (2) can calculate g(x')
for arbitrary x' and (3) we can control the variance of 20 (P wgg (wr))²
((x))
can be shown by choosing q to be a uniform mixture of the m training set neighborhoods (one for each ı; S),
satisfy all 3 properties. (1) and (2) are trivial if those same properties being satisfied by Nmmr (which is the case for the Gaussian neighborhoods we consider). If N can be sampled from, the mixture over m such distributions can obviously be sampled from. The same goes for calculating the density, which in this case is:
m
1 m
Σ
PNmi(1)
We observe that (3) can also be shown because we can upper and lower bound the quantity in question. To show this, we first re-write as
Di (x)))(x'))
m2
m bim (Pimmr (x'))²
((x")
m
PN (x')
==
E. (p (x'))²
vm
MM Pamm (I')
||s(('))l2
vm
[ps(x')ll
24

---

Published as a conference paper at ICLR 2021
where ps (2') is m-dimensional vector of densities each evaluated x' (i.e. one for each of the training points). Since for any vector v, ||0||2 I || I yml (7/l/e/22 the upper and lower bounds for this quantity in question are /m and 1 respectively. Thus can bound the variance of this quantity This does not scale with dimension but only the number
by (V m - 1)² v mn and Var( v m 4m
4
of training points!
To be even more concrete, for a given m and n, we can now apply a Hoeffding bound to control the error.
P(Lss psl > t) x 2e 2nr2
In our experiments we choose be 10m, meaning that the probability that ps is off by more than 0.5 is capped at about 1% (recall that scales from degree of accuracy).
[1, /m], which means this is fairly reasonable
E.2 FULL SET OF RESULTS
3921
Housing (d-21. 5061
Wine (d-11,
Diyyoom Crmatt zane
0.4
Iidyytima Grrowdh
0.3
Eslymomt
63
6.9
50
14
1.000
0.00
1.000
0.122
0302
1.000
6919 1000
2.000
0000
5.00
75
1borhood
Neighborhooe
Neighborheod
Day
(dm69, 1059:
Wepeaaman Cocwett daate
Grcech
02-
R
30
15
20
30
25
L0000 (MMB
C0022
1/305
0.00
co013
0.55
0.30
0.55
1000
0.60
30
15
20
20
30
25
Neighhort aod
Meigh
Figure 2:
Approximate exponent of ps's polynomial growth rate (top) and train/test MNF (below) plotted for various neighborhood widths across several UCI datasets.
Note that for the Day and Music datasets, the test MNF curves behave differently than for the other three datasets. Here, test MNF rises initially for small neighborhood widths but then drops and plateaus as neighborhoods get larger. As noted by Plumb et al. (2020). Day exhibits (globally) fairly linear relationship between inputs and outputs. Thus, we hypothesize our results here can be explained the basis that a global linear model (which is what the explanations saturate towards as a increases) actually can do quite well at approximating f. That is, the terms of the bound, the train MNF does not rise too sharply when saturation occurs but the complexity terms become smaller as neighborhoods get wider. We hypothesize a similar effect is at play for Music.
25


Reviews:
[{"review_id": "qi0U6s4fj9b", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper tries to make a novel connection between local explainability and learning theory, and proposes two theorems regarding bounds related to performance generalization and explanation generalization, respectively. The paper presents two sets of empirical results to illustrate the the usefulness of our bounds.\n\nOverall, the idea of the paper is interesting by exploring local explanations of black-box machine learning models from aspects of learning theory. Mirrored Neighborhood Fidelity (MNF) is proposed as a novel measure of local explainability and the core component of arguments and conclusions in the paper.\n\nThe paper claims that MNF naturally complements commonly used Neighborhood Fidelity (NF) and offers a unique advantage over NF when evaluating local explanations on “realistic” high-dimensional on-distribution data which often exhibit significant feature dependencies. However, there is no solid or convincing proof and empirical experiments for supporting the above claims except a toy example in the appendix.\n\nThe experimental section in the paper plots the polynomial growth rate and MNF for various neighborhood widths across several UCI datasets, but doesn’t show how the proposed MNF-based method can gain advantage over existing NF-based local explanation models such as LIME and MAPLE in terms of better explanation.\n\nThere is some space to improve readability. Some notations are not well-defined and self-contained for their first mentions.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ik6czSXbqJG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper presents two main theoretical results as its main contributions.  First, the authors provide a bound on the model generalization in terms its local explainability.  This bound relates the model generalization, the training accuracy, local explainability, and the complexity of the explanations.  Second the authors provide a bound on local explainability generalization.  This bound describes the relation between training local explainability and test time local explainability.  Both these bounds make concrete intuitive notions around local explainability generalization --- for instance, as we increase the size of the local explanation, generalization will decrease.  Last, the authors provide short empirical evaluation to demonstrate the properties they describe in their bounds appear in practice.\n\nQuestions + Comments:\n\nSection 3:\n\nBoth notions of neighborhood fidelity (NF) and mirrored neighborhood fidelity (MNF) are well described.  As the authors comment, NF is the commonly used notion of explanation fidelity --- the local error on sampled points within the neighborhood.  The authors perform their analysis on the related notion MNF, which relies on evaluating instead on training points. The authors comment that this notion is (1) relevant and well motivated (2) enables the connection between generalization and local interpretability.  While there is likely a good reason, its currently unclear why the same analysis can't be performed on the more commonly used NF notion.  Right now, the transition from NF and MNF lacks motivation and stating why MNF is needed very explicitly would help make the section much stronger.  \n\nSection 4:\n\nThe significance and meaning of Rademacher complexity could be more clearly described.  Though this might be a common tool for those from a learning theory background, readers with backgrounds in explainability could be less familiar.  For instance, what is $\\sigma_i$ in lemma 4.1? What is the significance of this term? Stating this more clearly within the section could strengthen the applicability to explainability focused readers.\n\nSection 5:\n\nIn the second paragraph, the authors claim that notions of local explanations which can repeatedly sample nearby points are not interesting from a generalization perspective because we have access to a potentially unlimited amount of data. However, in these situations, querying the model so much as to reach this level of data might not be practical.  Consider something like BERT where query time could be prohibitively slow (and f is not free by any means, both from a time and $ perspective) --- questions related to how well a particular explanation could generalize could be very useful for things like deciding when to stop querying the model.  I'd ask the authors to at least reconsider this strong assertion that investigation into this direction is not useful.  Further, I'd be curious to hear if the author's results could apply in this case? \n\nOverall comments:\n\nThis is a well written paper that outlines a number of useful properties of local explanations.  Because the results generally use the MNF notion of fidelity, some users of local explanations might not find them as immediately applicable.  Further, the results might not be so surprising to interpretability focused readers -- the assertion that decreasing the width of the local explanation will likely result in a better approximation is fairly well understood for instance, at least intuitively.  That said, the paper makes clear a number of key properties in local explanations and thus could be a useful contribution to the literature. \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ayshlCFr54p", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The manuscript proposes bounds for the MSE of the estimation of a function from finite samples. The novelty of the proposed bounds in comparison to classical results is that the complexity of the function is stated in terms of its local interpretability, i.e. how well it can be approximated by a family of simple functions. \n\nThe paper is very well written and clear. I think that the proposed way of characterizing function complexities is useful for providing new insights in learning theory. However, the authors may find it useful to address the following points: \n\n1. In the main result of the paper (e.g. the bound in the first page) would it be typically easier to find the complexity of the local approximation function class G, rather than finding the complexity of the actual function class F? Some comments would be useful.\n\n2. The neighborhood fidelity (NF) concept was proposed in some previous works, which the authors have modified to propose the mirrored neighborhood fidelity (MNF). The main difference between these two definitions seems to be the fact that the local approximations gx are evaluated at points x' within the neighborhood of a source point x in NF; while in MNF a different local approximation gx' is computed at each neighboring point, and gx' are evaluated at x. The authors have presented some arguments about the advantages of MNF over NF, but the essential difference between these two ideas is still not clear to me.\n\na. It is said that \"Selecting the target point distribution to be D rather than D perturbed by Nx better emphasizes the ability for explanations to accurately convey how well g will predict at realistic points.\" In my understanding, both x and x' will be samples in the data set in the empirical estimate of NF, as well as that of MNF. So I do not understand why MNF is more realistic than NF. \n\nb. It is also said that \"When one measures NF with standard neighborhood choices that\nignore feature dependencies (i.e. most commonly Nx = N(x, sigma I)), the resulting target distribution may concentrate significantly on regions that are non-relevant to the task at hand\". Again, in my understanding the choice of the neighborhood is something independent of whether NF or MNF is used. Both could be coupled with any neighborhood definition. \n\n3. Why don't the authors combine theorems 1 and 2 to bound the expected loss in terms of the empirical MNF and the Rademacher complexity of the local approximations? I guess that would be the most meaningful result from this paper. The main result summary in the first page of the paper does not exactly do this.\n\n4. The authors mention some limitations of their bounds referring to the dependence on the dimensionality. I guess to address this limitation, a nice extension of this study would be to remodel the neighborhood size by taking into account the intrinsic dimensionality of the data, using e.g. manifold models, low-dimensional models, etc. A Gaussian neighborhood seems to be considered throughout the paper. This often gives a too high estimation of the dimensionality of the data, whereas actual data sets are often low-dimensional although they reside in a high-dimensional space.\n\n5. In the practical scenario considered in this work, do gx's have to be computed in practice? I understand that the role of gx's is just to theoretically characterize the function complexity of f, so the proposed bounds would be applicable to any learning algorithm (not necessarily using local approximations), is this correct?\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an interesting connection between learning theory and local explainability. The reviewers have reacted to each others' thoughts, as well as the authors' comments; they are largely in favor of acceptance. I think the ICLR community will enjoy discussing this paper at the conference.
Decision: Accept (Poster)