Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes smoothness/robustness of explainers of blackbox classifiers as a desirable objective. It gives theoretical bounds for this measure of robustness, (called explainer astuteness) in terms of the Lipschitz constant of the learned blackbox model. Theorems relating the two are given for three types of explainers, and the results are demonstrated empirically on a few datasets.
strength_and_weaknesses: Strengths:

The paper has an easy-to-follow structure and repeatedly emphasizes its message relating the model Lipshitzness and explainer astuteness. 

Weakness:

It is not at all clear why the end user of a blackbox explainer cares about the robustness of the explainer. The blackbox model is typically not under the end-user's control, and the only thing expected of an explainer is its faithfulness to the blackbox model. These results would be interesting, if different explainers had drastically different robustness for the same blackbox model -- that way the paper can be viewed as an advisory on what types of explainers to use in case the user cared about smoothness of the explainer.

The technical results are hard to follow and not written mathematically precisely. e.g. in Lemma 1 what are these "sampling points"? What is "i" in the set N_k? The usage of "approaching" is confusing -- what is the limit or sequence here? It looks like the set N_k is the set of points with k non-zero co-ordinates. Does the statement mean that beta=alpha when the data points all contain only one non-zero entry? Elsewhere in the paper something else is mentioned that confuses me further. 

As the authors themselves mention, it is not at all surprising that the Lipshitz constant of the learned model affects the Lipschitz constant of the explainer, as indeed the explainer is designed and required to mimic the black-box model. 



clarity,_quality,_novelty_and_reproducibility: Clarity:

The technical results are written in mathematically imprecise language, round up of this will make the contributions less messy. 

The paper structure is somewhat strange. A single subsection (3.1) is larger than the rest of the paper.


Originality:

While a formal theorem relating explainer smoothness to blackbox function smoothness might be novel, it is not particularly surprising or immediately useful. 


summary_of_the_review: Summary:

1. The significance of explainer astuteness to the end-user needs validation.
2. The mathematical details are imprecise.
3. A method for modifying existing explainers, with increased astuteness without sacrificing faithfulness to the black-box model is required  to bump this paper to the next level 
4. A result showing the theoretical maximum astuteness of any explainer for a given blackbox model (with appropriate faithfulness) would also be appreciated.

Comments:

If explainer astuteness is proposed to be of independent interest, a subjective study is required where test subjects rank different explainers based on repeated use of the blackbox model and the explainer.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides a theoretical analysis on the robustness of explainers.
Here, the robustness is measured as the difference between the two point $x$ and $x'$ in a close neighborhood.
If explanations for $x$ and $x'$ largely differ, the explainer is deemed to be not robust.
For the analysis, the authors adopted the notion of *astuteness* which was originally introduced for measuring the robustness of classifiers.
The authors extended the idea of astuteness for explainers and defined the explainer astuteness (larger the better), which is the robustness measure considered in this paper.
The authors derived the lower bounds of the explainer astuteness for some popular explainers, such as SHAP, feature removal, and RISE.
The results indicate that if the target function to be explained is $L$-Lipschitz with respect to the $\ell_p$ distance (more formally, locally probabilistic Lipschitz), the explainers are $O(\sqrt[p]{d}L)$-Lipschitz with high probability.

strength_and_weaknesses: ### Strength
This will be the first study connecting the smoothness of the target function and the robustness of the explainers.
As the authors stated as "the statement is intuitive", the results look reasonable; for less smooth functions with sharp changes, the explainers also need to change drastically to reflect the change of the function, leading to less robust explanations.
Providing rigorous proofs to intuitions will be an important step towards understanding the relationship between the models and the explainers.

### Weakness
(My comment here is not really a weakness, but a suggestion for a further improvement.)
The weakness of the paper is that all the explainers considered are found to be $O(\sqrt[p]{d}L)$-Lipschitz.
Although dedicated proof techniques are required for different explainers, the results are not very surprising.
The results will be far more interesting if there are explainers that have different orders of Lipschitzness.
For example, if an explainer with large Lipschitzness is found, the use of that explainer should be avoided.
Or, if an explainer with small Lipschitzness is found, that explainer can be a recommended choice in practice.
I wonder whether there are any explainers with these interesting properties.
clarity,_quality,_novelty_and_reproducibility: ### Clarity, Quality, Novelty
The research motivation as well as main results are stated clearly.
Formalizing the theoretical framework connecting the smoothness of the function and the robustness of the explainers will be the novelty of the paper.

### Reproducibility
Experimental setups are described briefly in the paper.
The results may be reproducible.
summary_of_the_review: This is an interesting study connecting the smoothness of the function and the robustness of the explainers.
Although the results are not very surprising, establishing a theoretical framework would be an important contribution to the field.
The current paper analyzed a few popular explainers and concluded that they are all $O(\sqrt[p]{d}L)$-Lipschitz.
The results will be far more interesting if there are explainers that have different orders of Lipschitzness.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: With the increase in the complexity of machine learning models, it becomes crucial to explain model decisions and increase transparency between human-model interactions. To this end, several explanation methods have been proposed in recent literature for explaining model predictions, but few works discuss necessary desiderata (faithfulness, stability, and fairness) to evaluate the reliability of an output explanation. In this work, the authors discuss the stability property of an explainer, i.e., an explainer should give similar explanations for similar data inputs. The paper formalizes explainer astuteness by leveraging probabilistic Lipschitzness (the probability of local smoothness of a function). Further, it provides bounds for guarantees on the astuteness of these explainers given the Lipschitzness of the prediction function and empirically validates the behavior using real-world datasets. 
strength_and_weaknesses: **Strengths**

1. The paper presents a theoretical analysis of the stability of explanations generated using a variety of diverse explanation methods, including SHAP, RISE, and CXPlain.
2. Theoretical and empirical analysis show that locally smooth predictive models lead to more robust explanations.

**Weaknesses and Open Questions**

1. The notion of stability is limited to the prediction behavior of the model, defined in Alvarez-Melis & Jaakkola et al. However, recently Agarwal et al. highlighted that the existing stability definition assumes model $f$ has the same behavior for similar inputs $\mathbf{x}$ and $\mathbf{x}'$, i.e., the model uses the same logic path (e.g., activating same neurons in a deep neural network) to predict the same label for the original and perturbed instance. It would be great if the authors can comment on this property of relative stability.
2. Previous works like Alvarez-Melis & Jaakkola et al., Agarwal et al., and Fel et al. have used the predictive model's Lipschitz constant to quantify the stability of explanations. This limits the novelty of the proposed work.
3. Unlike RISE and SHAP, we do not observe higher astuteness for the CXplain explanation method. It would be beneficial for the readers if the authors can give any insights into this behavior.


**References**
1. Fel, T., Vigouroux, D., Cadène, R. and Serre, T. How good is your explanation? algorithmic stability measures to assess the quality of explanations for deep neural networks. In WACV, 2022.
2. Agarwal, C., Zitnik, M. and Lakkaraju, H. Towards a rigorous theoretical analysis and evaluation of gnn explanations. In AISTATS, 2022.
3. Alvarez-Melis, D. and Jaakkola, T.S. On the robustness of interpretability methods. In arXiv, 2018.
clarity,_quality,_novelty_and_reproducibility: **Clarity**

The main idea and hypothesis of the paper is clear.

**Quality**

The paper is not well written. Especially, the authors have significantly changed the ICLR latex template by removing spaces between the sections and subsections. 

**Novelty**

The paper presents incremental novelty.
summary_of_the_review: The paper provides interesting theoretical and empirical stability analysis of diverse explanation methods. The proof for the Astuteness of explainers that remove individual features should scale to a plethora of feature attribution methods, but the paper does not show the results for any.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper attempts to provide explanations which are similar for similar datapoints. Borrowing on the idea of astuteness of a classifier, nearby points should have the same predictions, it develops the idea of explainer astuteness. One of the main takeaways is locally smooth 
prediction functions provide locally robust explanations.
The main issue seems to be that the paper needs to be more clear on the contributions vis-a-vis existing work. Several references were made by the referees. An extensive discussion on the merits of the proposed approach versus those references would be important to appreciate the contributions.




justification_for_why_not_higher_score: There are serious presentation issues.
Decision: Reject