Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper looks at two aspects of ethics-aware ML: right-to-be-forgotten and right-to-explanation, and makes the points that the two could be in conflict with each other. Specifically, a change in the model parameters resulting from the right-to-be-forgotten requests could lead to invalidation of previously provided counterfactual explanations. The paper proposes metrics to measure change in explanations and also proposes algorithms for identifying data points whose removal would lead to the largest changes.
strength_and_weaknesses: ### Strengths

1. The potential conflict between right-to-be-forgotten and right-to-explanation sounds like a very relevant and timely area to explore. To the best of my knowledge, the paper is the first one to explore this question.
2. The paper is generally easy to follow. The metrics proposed here are simple and intuitive (though some details could be explained better -- see comments below). Same goes for the proposed strategies for identifying the data points that would lead to the most change.

### Weaknesses

1. At times, there is too much information and the takeaways are not easy to follow. E.g., how was it decided that only logreg and NTK should make it to the main paper? Why not add at least a summary of the experiments with related models?

2. Some of the details about the experimental setup could use more discussion, e.g., what is the intuition behind the 'median" strategy in Section 6? Please see detailed comments under the Clarity section.
clarity,_quality,_novelty_and_reproducibility: ### Clarity

The paper is mostly easy to follow. However, its a bit too dense at places and important details are missed. Specifically:

1. Section 6: What is the median score? Why not consider the predicted class label?
2. Section 6: “positive leaning prediction (above median) to a negative one (below median)”. Does that mean that only negatively predicted inputs were considered? Would the results change if the other class was also included?
3. Eq 4: Would $\check{x}_{\omega}$ still be compute even if $\check{x}_1$ remains a valid recourse? This seems like a very crucial point that should be explicitly discussed.
4. Eq 4: How are categorical features handled in this definition (e.g., using Gower distance)? Are the features scaled?
5. Eq 3: I initially missed the fact that $\check{x}_1$ refers to the recourse with w_1. It might be worth clarifying this.
6. Eq 3: Shouldn’t \Delta(\omega) also be a function of x?
7. Were the methods (e.g., DICE) configured to generate more than one counterfactual or just a single one?

### Quality
For a first paper introducing a concept, the quality of theoretical analysis (though preliminary) and experimental results seems sufficient.

### Novelty
To the best of my knowledge, potential conflicts between right-to-be-forgotten and right-to-explanation have not been explored in the prior work.

### Reproducibility
The models are simple and the hyperparameters etc are reported. Explainers are used from the open-source CARLA library.

summary_of_the_review: Overall, the problem proposed in the paper is quite important and timely. To the best of my knowledge, the paper is the first one to look into it. The algorithms and experiments are somewhat preliminary but sufficient for a first paper in the area.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents an initial study on the trade-off and connections between two key data regularization principles, “the right to be forgotten” and “the right to recourse”. The authors formalize the new recourse robustness problem through outcome and action instability, and subsequently upper bounds the recourse instabilities caused by a single data instance removal on simple (kernelized) linear models. The paper also proposed algorithms to efficiently find the critical data points responsible for the instabilities. Empirical experiments show that simple models considered in this paper are very susceptible to data deletion requests and not stable in terms of recourse actions. Also, the algorithm proposed is effective in finding those critical points.
strength_and_weaknesses: Strengths:
1. The paper calls the newly formulated research problem that investigates connections between explainability and the right to be forgotten.
2. The paper is well-written, clear and presented with interpretable results throughout.
3. The paper presents several theoretical and practical insights towards building deletion robust applications from the perspective of both data and model.

Strengths:
1. The paper calls the newly formulated research problem that investigates connections between explainability and the right to be forgotten.
2. The paper is well-written, clear and presented with interpretable results throughout.
3. The paper presents several theoretical and practical insights towards building deletion robust applications from the perspective of both data and model.
clarity,_quality,_novelty_and_reproducibility: The paper’s focus is on the theoretical understanding of the trade-off between the right to be forgotten and recourse invalidation. It is nice to have the recourse instability notions formalized first, and analyzed later for worst-case performance (vulnerability).

Below are some concerns I have:

1. I feel connections should be drawn between the accuracy and explanation aspects of deletion. When there exist works that delete data without compromising model accuracy, in their context, deletion robustness aims to prevent significant change in model parameters (i.e., no large $d_i$, the influence). It is not so different here when we consider recourse outcomes that are also linked to model parameter changes. Hence, the novelty of this work is lowered as the explanation framework is another deletion-robust problem in disguise. Could you explain why is deletion robustness insufficient? 

2. It is nice to have comparisons for the robustness of different model classes in the experiments. It would be nice to see another application that the authors mention, which is the use of the method to perform data minimization for a model more robust to deletion. For example, is the model trained with the most influential points removed more robust now? Or, would it suggest the exclusion of certain input features, which is also an aspect of data minimization?

3. The definition of $\Delta$ and $\Phi$ in Definition. 1 and 2 are general to data weights $\omega$. However, the $\Delta$ and $\Phi$ in the Propositions refers to instability with respect to a single instance deletion. This may cause confusion and consider changing. Also, can the Propositions be generalized to multiple instances deletion?

4. For proposition 2, wouldn’t the NTK matrix $K^\infty(X,X)$ change in dimension when a data instance is removed? Would this cause a problem to the derivation in Equation (21) in Appendix A.1?

5. It is understandable and reasonable to conduct theoretical analysis on the simplest model classes as an initial investigation. Note that both “the right to be forgotten” and “explainability” stems from practical problems, it is necessary to at least empirically study the larger and more complex neural networks we use in practice? Are they much less susceptible to removal? Are the recourses then less vulnerable to deletion requests?
summary_of_the_review: Overall, I like the refreshing idea that relates data deletion to actionable explanations, while efforts are still needed to better distinguish this problem from other aspects already studied under data deletion (e.g., accuracy). I also think the theoretical analysis sheds insights into the direct link between data point influence and counterfactual explanation instability. The clear writing is also a bonus. Some points mentioned above can still be improved.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors discuss the properties of recourse-type counterfactual explanations under model perturbation by removing a data point. Drawing a line to the impact this would have on the usefulness of recourse recommendations in a regime where data deletion occurs post-training, they specify two ways in which explanations can be non-robust under this perturbation - the usefulness of an old explanation under a new (post-deletion) model, and the change in an explanation pre- and post-deletion. They upper bound these impacts in the case of a linear model and an NTK, and provide heuristic approaches for finding the set of points whose deletion would cause the most instability in explanations and their outcomes. They provide some experimental validation, showing in particular that you can find very small subsets which "invalidate" recourses - that is, which cause old recourses to not provide the desired outcome under the new model.

Note: I think I reviewed this paper in a past conference, so apologies if some of this content is familiar. I did not go back and look at that review before re-reading the paper, so I had fresh eyes on it, although its plausible some of the feedback is similar.


strength_and_weaknesses: Strengths:
- a novel direction, combines two questions which I have not seen combined before (recourse + deletion)
- Beyond responsible AI-type questions, this research direction could have more general ramifications for understanding the shape of the decision-boundary in e.g. an NTK
- the theoretical and experimental work both provide clear, concrete contributions to the central question of the paper

Weaknesses:
- I'm not sure the theoretical work provides that much insight - it seems that the main takeaway is that points with higher influence are going to provide more recourse instability, which seems obvious. I'm not saying they're bad results (it's good to have them) but not sure they are that revealing. Maybe there is intuition here which can be expanded on?
- would be good to draw more comparisons to related work looking at robustness of explanations/recourse, since that's what this paper is essentially about
- I'd like to know more about what happens in the average case of deletion, since in practice that's what we'd mostly be looking at (rather than the worst-case)
- the logic on page 6 below Corollary 1 confuses me: why would we assume that the parameter norm's change will be minimal, but not assume that the actual difference change will be minimal? I understand the two are not equivalent, I'm just not sure why the authors choose to make one assumption and not the other
- the algorithms in 5.2 seem very computationally intensive, requiring the re-learning of the model after every point removal - I'm wondering if the authors could expound more on these challenges practically, or discuss if they think there are ways around this
- "Evaluation Measures" paragraph refers to the gradient-based method but I don't see it in Fig 2
- "... by up to 6 percentage points" - I'm not sure I understand this result, might need more clarification in the paper
- on page 9 (in conclusion, and possibly in the last paragraph of Sec 6 as well), an approach is discussed where you remove the highest influence points from training. I don't totally understand how you could do this before the model is trained - is that the intention?
clarity,_quality,_novelty_and_reproducibility: Clarity: pretty good, problem is clearly motivated. Some minor claims are not totally clear to me (see previous section of review)
Quality: good, the paper is neatly written and the results and experiments seem correct, albeit not mind-blowing
Novelty: definitely a novel problem formulation
Reproducibility: I think this would probably be reproducible, information is given on hyperparameters in the paper and the code is provided
summary_of_the_review: I think the novelty of this setup combined with the clarity and quality of the writeup and basic results are sufficient to recommend acceptance. I don't necessarily feel the paper goes the "extra mile" to be a slam dunk accept - the theoretical and experimental results are mostly as I would have expected and I don't necessarily feel like they give me tons of extra insight. However this does not make them bad results and it's good to have them done.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the trade-off between the ability to achieve algorithmic resource vs. the right to be forgotten in machine learning, specifically via linear models and wide neural networks. It illustrates that these two desiderate (algorithimic resource and the right to be forgotten) are fundamentally at odds by defining two measures of recourse instability. The paper further devises an algorithm to demonstrate this by opimizting for the minimum number of data points to forget that result in the highest instability. Empirical results on two real-world datasets are provided.
strength_and_weaknesses: ### Strengths

- The studied problem is novel and interesting. Both algorithmic resource and the right to forgotten are very relevant and important.
- The perspective of considering resource instability is interesting.
- The paper is generally well written and organized.

### Weaknesses
- The connection between the setting of ERM in Section 3 and the NTKs in Section 4 can be made more explicit. While I understand that NTKs are probably adopted here because they offer the theoretical result equation (7) and the subsequent results, perhaps a simpler learning setting where the model parameters (and thus updates) are more analytically tractable and can explicitly leverage the ERM setting would make the argument more grounded. For instance, there are a few places the authors used the concepts of influence, leverage. I wonder whether following the simpler setting (i.e., linear regression) to leverage these well-understood concepts would enable a more in-depth and "tighter" analysis. 


- The key result in Section 4 depends on neural tangent kernel, which may give a looser theoretical result than ideal. Specifically, there are a few steps of approximations necessary for NTKs (e.g., $k \to \infty$). While this may be a weaknesss of NTK itself, highlighting this point or in what way the approximations in NTK can limit the analysis. For instance, the authors mention 
> we provide data dependent upper bounds on the invalidation measures from Definitions 1 and 2, which practitioners can use to probe the worst-case vulnerability of their algorithmic recourse to data deletion requests

    It would be nice to help the readers gauge the tightness of this worst-case vulnerability. Right now, while the upper bounds are a nice theoretical result, how they should be applied in practice can be explained further (e.g., are the upperbounds likely to be overly pessimistic, what are the situations these might not hold).

- Section 5 is proposed to specifically tackle the computational challenges arising from (i) possible retraining from deletion; (ii) a combinatorial subset selection to maximize the instability. It would be more reassuring that some theoretical guarantees are provided, especially if the dataset is large and/or the model is complex (as motivated earlier where the number of hidden node $k\to \infty$).
clarity,_quality,_novelty_and_reproducibility: ### Clarity and Quality:

The paper is generally clearly and well written.

### Novelty:
To the best of my knowledge, the consideration of the trade-off between algorithmic resource and the right to be forgotten and the recource instability measures are novel.

### Reproducibility:
Reproducibility should not be an issue as the authors provide sufficient details of the experiments and the code as well. I quickly scanned through the code but did not run it.
summary_of_the_review: I think the paper takes an interesting approach to a relevant problem. Though the choice of the particular theoretical/technical framework can be improved to make the argument more grounded, I believe there are sufficient contributions both theoretical and empirical. The paper is generally well written with clarity.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper provides a theory on how algorithmic recourse may be affected by data deletions (framed as "right to be forgotten" requests) that change the predictive model over which recourse operates.

Strengths: an original take on the challenges to algorithmic recourse that is framed based on very plausible real-world considerations about (lack of) dataset persistence. It is presented in a very well-organised and detailed fashion.

Weaknesses: the theory is not the most surprising (classical concepts such as leverage play a role) and the resulting algorithm does not have guarantees per se as it leads to a combinatorial optimization problem without a tractable solution in general.
justification_for_why_not_higher_score: The theory is not the most surprising (classical concepts such as leverage play a role) and the resulting algorithm does not have guarantees per se as it leads to a combinatorial optimization problem without a tractable solution in general.
justification_for_why_not_lower_score: It's an original take on the challenges to algorithmic recourse that is framed based on very plausible real-world considerations about (lack of) dataset persistence. It is presented in a very well-organised and detailed fashion.
Decision: Accept: poster