Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Overall, 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.

The 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.

The 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.

There is some space to improve readability. Some notations are not well-defined and self-contained for their first mentions.
review_title: Connection between local explainability and learning theory

final_score: rating: 7: Good paper, accept
review_content: 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. 

The 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: 

1. 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.

2. 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.

a. 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. 

b. It is also said that "When one measures NF with standard neighborhood choices that
ignore 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. 

3. 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.

4. 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.

5. 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?


review_title: Well written, insightful paper

final_score: rating: 7: Good paper, accept
review_content: Summary:

This 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.

Questions + Comments:

Section 3:

Both 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.  

Section 4:

The 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.

Section 5:

In 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? 

Overall comments:

This 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. 



review_title: Review

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)