Auditing Local Explanations is Hard

We thank the reviewer for their thoughtful review. We will respond to each weakness in order.

W1. We agree that empirical validation is an important direction for further work, and will emphasize this in the final version of our paper. We chose to take a theoretical focus because the main result of our work is a lower bound that applies to any algorithm.

W2. We thank the reviewer for the added reference, and will include a more detailed comparison with prior works in the final version of our paper. With regards to Dasgupta et. al., it is indeed correct that the notion of "local consitency" (Definition 1) provided in their paper precisely matches our notion of "local loss" (Definition 2.3) when the region they define, $C_\pi$, is construed as a local explanation region. However, a key difference with their work is that ours provides lower bounds on the amount of data needed to estimate the local loss (over the entire distribution), and this result is the main point of our paper.

With regards to Bassan and Katz, we agree that their work provides an interesting idea for provably correct local explanations (thus, in some cases, circumventing the need for an audit). By contrast, the results in our work are designed to apply to any local explanation scheme.

W3. We agree that our work is limited to a certain type of "local explanation" and doesn't encapsulate explanation methods such as SHAP. As we explained in our general rebuttal, we will make sure to carefully outline the scope of our paper in the final version. We will also emphasize in the final paper that studying other types of local explanation methods is an important and interesting direction for future work.

We thank the reviewer for their review. We will begin by addressing the listed weaknesses

1. As we mention in our global rebuttal, we respectfully disagree that the considered explanations are too limited. LIME and Anchors are both reasonably utilized methods in practice, and more generally we believe our general formulation captures a meaningful subset of explanation methods.

2. We will clarify further what we meant in lines 181-188 in the final paper. We never state that $g_x(x) = (\nabla_x f(x))^t x$. We rather meant that $g_x$ should be some linear classifier that matches these coefficients. In particular, we would also fit a bias term so that $g_x$ agree with $f$ at the point $x$. Additionally, as mentioned in our global rebuttal, our framework does not consider SHAP.

3. We have left an empirical validation of our results for future work. We believe that the theory provided is sufficient for meaningfully arguing the difficulties posed by local explanations that are too local. We view the results of this paper as serving as a "theoretical demonstration."

4. Thank you, this will be fixed.

5. Could you please elaborate on what you found lacking in our framework? Additionally, what precisely about our framework can be "difficult to satisfy." Please see our global rebuttal for our general argument for the utility of our framework.

Next, we will address the direct questions

1. We will correct this to be more precise in our general paper. While technically speaking, LIME does not use a gradient, we believe that at a high level it uses similar ideas to Gradient based methods by providing a local "linear-like" approximation to the general classifier.

2. We believe the binary classification setting is sufficiently relevant to be independently considered. However, we note that our lower bound directly extends to more general classification settings as binary classification is a subtask of multiclass classification. We also believe that our lower bound can be relatively easily adapted to regression by simply replacing the 0-1 loss used to define the local loss with an MSE based loss.

3. Could you specify specifically which assumptions are not justified? Furthermore, the user-specified threshold $\gamma$ is not set to $\frac{1}{3}$, it is instead assumed that $\gamma \leq \frac{1}{3}$. This is an extremely mild assumption considering that a local loss above $\frac{1}{3}$ would be considered egregiously inaccurate in most settings.

We thank the reviewer for reading and responding to our rebuttal. While we agree that empirical validation is an important direction, we don't agree that it is a straightforward verification task.

Our main result is a lower bound that holds for any general explanation method (note that this necessarily includes manipulative explanations where the explainer might create explanations that appear as though they come from a gradient based method but in reality are maliciously modified) along with any general auditing method. Thus, experiments run for a specific pair of explanation and auditing methods do not serve as strong evidence for our theorem holding. Furthermore, the fact that local regions in high dimensional space can be extremely small implies that determining a ground truth value for the local loss itself could prove challenging.

Due to these factors, we do not have enough time to include a meaningful empirical validation of our lower bound in this submission. Although we believe that our current results are sufficient for a complete paper, we respect the reviewers view that an empirical validation is a needed component.

We appreciate the review and the detailed questions. In order

1. As we mention in our global rebuttal, we do not believe the local loss is sufficient for preventing adversarial attacks. We rather believe that maintaining a low local loss is one of many necessary components required for a trustworthy explanation. We intentionally do not define trustworthiness, we are rather just showing that auditing one part of it can be difficult from a data perspective.

2. Our scheme isn't intended to encapsulate ways to "establish a local explainer." It is rather meant to reflect plausible settings where an Auditor might seek to audit explanations provided by some entity that desires to protect information about their models.

3. Could you finish this question in a comment? We'd be happy to respond during the next period of the review.

4-5. Thank you, we will fix these.

6. This is a constant chosen simply for mathematical reasons. It is merely designed to make the algebra within our bounds to work out and is not tight (as our goal is to simply provide an asymptotical lower bound). Replacing it with a different constant would simply result in changing values of $\epsilon$ and $\delta$. Note that for small values of $\lambda$ (in high dimensional data), this constant would be easily dominated by $\lambda$.

7. This is an interesting question. This would depend a lot on the manner in which the K examples are chosen. While it appears that querying samples from a single local region would allow for very quick estimation of the local loss, we believe that ensuring that these examples are "in-distribution" would pose a technical challenge. In particular, the auditor would have to have some notion of what constitutes a "realistic" example. We believe this is an interesting direction for future work.

We would additionally like to respond to some of the other points raised in the "Weaknesses" section. As we mention in our global rebuttal, we don't feel that our setting is too limited to bear relevance, and we also aren't quite sure what the "linear assumption" being referenced is. As we mentioned in answer 1 and in our global rebuttal, we do not define trust as the local loss. We rather argue that a low local loss is necessary but not sufficient for there to be trust.

Finally, as we mentioned in answer 2, our paper is designed to examine a natural default way in which a set of explanations might be audited. In fact, one of the implications of our results is precisely the necessity for other methodologies.

We thank the reviewer for their detailed review. We will first respond to the listed weaknesses.

1. As we mention in our global rebuttal, we believe our setting reflects cases where an Auditor might have access to a set of explained cases by default. For example, applicants to a bank for loans could, in principle, pool their explanations to provide a dataset with which an Auditor could operate within our setting. We will discuss further in the final version of our paper, and will include examples of cases where our setting could plausibly apply.

2. We appreciate the feedback on figure 1, we will certainly add more detail to the caption and simplify the figure by removing the green decision boundary and including enough points to visually demonstrate the concept of "enough data for auditing."

3. The key issue posed by Figure 2 is the curvature in the data manifold. Thus, we believe that cases with high dimensional and highly curved data manifolds would pose similar issues as the decision boundary involved would seldom be linear. A detailed empirical investigation of this is left as a direction for future work.

4-5. Thank you, these will both be fixed.

Regarding the direct questions:

1. We believe $\gamma$ to be largely application based, and for this reason chose to leave it as a user-specified parameter. However, one basic guiding principle might be to set $\gamma$ similarly to the general loss of the classifier being explained. For example, it doesn't seem necessary to require local explanations with a corresponding local loss of 0.001% for a classifier with a 30% misclassification rate.

2. Our local and upper bounds are designed for arbitrary, potentially complex classifiers. We chose this as the default starting point for theoretical analysis. We believe that studying more restricted cases of classifiers could be very interesting and promising. For example, we believe that ensuring a classifier satisfies some degree of smoothness (i.e. close to locally linear decision boundaries) could plausibly greatly reduce the amount of data needed for auditing.