On the Trade-Off between Actionable Explanations and the Right to be Forgotten
Authors: Martin Pawelczyk
Tobias Leemann
Asia Biega
Gjergji Kasneci
Venue: ICLR 2023 poster (2023)
Keywords: Counterfactual Explanations
Algorihtmic Recourse
Explainability
Interpretability
Transparency

Abstract: As machine learning (ML) models are increasingly being deployed in high-stakes applications, policymakers have suggested tighter data protection regulations (e.g., GDPR, CCPA). One key principle is the “right to be forgotten” which gives users the right to have their data deleted. Another key principle is the right to an actionable explanation, also known as algorithmic recourse, allowing users to reverse unfavorable decisions. To date, it is unknown whether these two principles can be operationalized simultaneously. Therefore, we introduce and study the problem of recourse invalidation in the context of data deletion requests. More specifically, we theoretically and empirically analyze the behavior of popular state-of-the-art algorithms and demonstrate that the recourses generated by these algorithms are likely to be invalidated if a small number of data deletion requests (e.g., 1 or 2) warrant updates of the predictive model. For the setting of differentiable models, we suggest a framework to identify a minimal subset of critical training points which, when removed, maximize the fraction of invalidated recourses.Using our framework, we empirically show that the removal of as little as 2 data instances from the training set can invalidate up to 95 percent of all recourses output by popular state-of-the-art algorithms. Thus, our work raises fundamental questions about the compatibility of ``the right to an actionable explanation'' in the context of the ``right to be forgotten'', while also providing constructive insights on the determining factors of recourse robustness.

Published as a conference paper at ICLR 2023
ON THE TRADE-OFF BETWEEN ACTIONABLE EXPLANATIONS AND THE RIGHT TO BE FORGOTTEN
Martin Pawelczyk'; Tobias Leemann', Asia Biega"; and Gjergji Kasneci'
Uniierssity of Tübingen. Germany
Maax-Planck Pl--cck-nnnntttttee for Security and Privacy, Germany
ABSTRACT
As machine learning (ML. models are increasingly being deployed in high-stakes applications, policymakers have suggested tighter data protection regulations (e.g.. GDPR, CCPA). One key principle is the "right to be forgotten" which gives users the right to have their data deleted. Another key principle is the right to an action- able explanation, also known as algorithmic recourse, allowing users to reverse unfavorable decisions. To date, it is unknown whether these two principles can be operationalized simultaneously. Therefore, recourse invalidation in the context of data deletion requests. More specifically, we theoretically and empirically analyze the behavior of popular tath-- algorithms and demonstrate that the recourses generated by these algorithms are likely be invalidated if a small number of data deletion requests (e.g., 1 or 2) warrant updates of the predictive model. For the setting of differentiable models, we suggest framework identify a minimal subset of critical training points which, when removed, maximize the fraction of invalidated recourses. Using our framework, we empirically show that the removal of as little as 2 data instances from the training set can invalidate up to 95 percent of all recourses output by popular state-of-the-ee algorithms. Thus, our work raises fundamental questions about the compatibility of "the right to an actionable explanation" in the context the "right to forgotten", while also providing constructive insights on the determining factors of recourse robustness.
introduce and study the problem
INTRODUCTION
Machine learning (ML) models make a variety of consequential decisions in domains such as finance, healthcare, and policy. To protect users, laws such as the European Union's General Data Protection Regulation (GDPR) (GDPR, 2016) or the California Consumer Privacy Act (CCPA) (OAG, 2021) constrain the usage of personal data and ML model deployments. For example, individuals who have been adversely impacted by the predictions these models have the right to recourse (Voigt & Von dem Bussche, 2017), i.e., constructive instruction how to act to arrive at more desirable outcome (e.g., change a model prediction from "loan denied" to "approved"). Several approaches in recent literature tackled the problem of providing recourses by generating instance level counterfactual explanations (Wachter et al., 2018; Ustun et al., 2019; Karimi et al., 2020; Pawelczyk et al., 2020a).
Complementarily, data protection laws provide users with greater authority over their personal data. For instance, users are granted the right to withdraw consent to the usage of their data at any time (Biega & Finck, 2021). These regulations affect technology platforms that train their ML models on personal user data under the respective legal regime. Law scholars have argued that the continued use of ML models relying on deleted data instances could be deemed illegal (Villaronga et al., 2018).
Irrespective of the underlying mandate, data deletion has raised number of algorithmic research questions. particular, recent literature has focused on the efficiency of deletion (i.e., how delete individual data points without retraining the model (Ginart et al., 2019; Golatkar et al., 2020a)) and model accuracy aspects of data deletion (i.e., how remove data without compromising model
Corresponding author: martin, wwwelczyk@uni-eeeeee.eep -enn--tueinnge..ee
I Equal senior author contribution.

---

Published as a conference paper at ICLR 2023
accuracy (Biega et al., 2020; Goldsteen al., 2021)). An aspect of data deletion which has not been examined before whether and how data deletion may impact model examenationramewwrrt frameworks. Thus, there is need to understand and systematically characterize the limitations of recourse algorithms when personal user data may need to be deleted from trained MI models. Indeed, deletion of certain data instances might invalidate actionable model explanations both for the deleting user and, critically, unsuspecting other users. Such invalidations can be especially problematic in cases where users have already started to take costly actions to change their model outcomes based on previously received explanations.
In this paper, we formally examine the problem of algorithmic recourse in the context of data deletion requests. We consider the setting where small set of individuals has decided to withdraw their data and, as a consequence of the deletion request, the model needs to updated (Ginart et al., 2019). In particular, this work tackles the subsequent pressing question:
What the worst impact that a deleted data instance can have on the recourse validity?
We approach this question by considering two distinct scenarios. The first setting considers to what extent the outdated recourses still lead to a desirable prediction (e.g., loan approval) on the updated model. For this scenario, we suggest robustness measure called recourse outcome instability to quantify the fragility of recourse methods. Second, we consider the setting where the recourse action is being updated as consequence of the prediction model update. In this case, we study what maximal change in recourse will be required to maintain the desirable prediction. To quantify the extent of this second problem, we suggest the notion of recourse action instabiliry.
Given these robustness measures, we derive and analyze theoretical worst-case guarantees of the maximal instability induced for linear models and neural networks in the overparameterized regime, which we study through the lens of neural tangent kernels. We furthermore define an optimization problem for empirically quantifying recourse instability under data deletion. For given trained ML model, we identify small sets of data points that maximize the proposed instability measures when deleted. Since the resulting brute-force approach (i.e.. retraining models for every possible removal set) is NP-hard, we propose two relaxations for recourse instability maximization that can be optimized using (i) end-to-end gradient descent or (ii) via a greedy approximation algorithm. To summarize, in this work we make the following key contributions:
Novel recourse robustness problem. We introduce the problem of recourse invalidation under the right be forgotten by defining two new recourse instability measures.
Theoretical analysis. Through rigorous theoretical analysis, we identify the factors that determine the instability of recourses when users whose data is part of the training set submit deletion requests.
Tractable algorithms. Using our instability measures, we present an optimization frame- work to identify small set of critical training data points which, when removed, invalidates most the issued recourses.
Comprehensive experiments. We conduct extensive experiments on multiple real-world data sets for both regression and classification tasks with our proposed algorithms, showing that the removal of even one point from the training set can invalidate up to 95 percent of all recourses output by state-of-the-arn methods
Our results also have practical implications for system designers. First, our analysis and algorithms help identify parameters and model classes leading to higher stability when a trained ML model is subjected to deletion requests. Furthermore, our proposed methods can provide informed way towards practical implementations of data minimization (Finck & Biega, 2021), as one could argue that data points contributing to recourse instability could be minimized out. Hence, our methods could increase designer's s awareness and the compliance of their trained models.
2 RELATED WORK
Algorithmic Approaches to Recourse. Several approaches in recent literature have been suggested to generate recourse for users who have been negatively impacted by model predictions (Tolomei et al., 2017; Laugel et al., 2017; Dhurandhar et al., 2018; Wachter et al., 201 8; Ustun al., 2019;
2

---

Published as a conference paper at ICLR 2023
Van Looveren & Klaise, 2019; Pawelczyk et al., 2020a; Mahajan al., 2019; Karimi et al., 2020; Rawal & Lakkaraju, 2020; Dandl et al., 2020; Antorán et al., 2021: Spooner al., 2021; Albini et al., 2022). These approaches generate recourses assuming static environment without data deletion requests, where both the model and the recourse remain stable.
Mothilal et al., 2020;
A related line of work has focused on determining the extent which recourses remain invariant to the model choice (Pawelczyk et al., 2020b; Black et al., 2021), to data distribution shifts (Rawal et al., 2021; Upadhyay et al., 2021), perturbations the input instances (Artelt al., 2021; Dominguez- Olmedo et al., 2022: Slack et al., 2021), or perturbations to the recourses (Pawelczyk et al., 2023).
Sample Deletion in Predictive Models. Since according EU's GDPR individuals can request to have their data deleted, several approaches in recent literature have been focusing on updating a machine learning model without the need of retraining the entire model from scratch (Wu et al., 2020; Ginart et al., 2019; Izzo et al., 2021; Golatkar et al., 2020a;b; Cawley & Talbot, 2004). A related line of work considers the problem of data valuation (Ghorbani et al., 2020; Ghorbani & Zou, 2019). Finally, removing subsets of training data is ingredient used for model debugging (Doshi-Velez & Kim, 2017) or the evaluation of explanation techniques (Hooker et al., 2019; Rong et al., 2022).
Contribution. While we do not suggest new recourse algorithm, our work addresses the problem of recourse fragility in the presence of data deletion requests, which has previously not been studied. To expose this fragility, we suggest effective algorithms to delete a minimal subset of critical training points so that the fraction of invalidated recourses due to a required model update maximized. Moreover, while prior research in the data deletion literature has primarily focused on effective data removal strategies for predictive models, there is no prior work that studies to what extent recourses output by state-of-the-arr methods are affected by data deletion requests. Our work is the first to tackle these important problems and thereby paves the way for recourse providers to evaluate and rethink their recourse strategies in light of the right to be forgotten.
PRELIMINARIES
The Predictive Model and the Data Deletion Mechanism. We consider prediction problems from some input space IRd to an output space V, where is the number of input dimensions. We denote a sample by z (x. y), and denote the training data set by D = {zi..... Z.). Consider the weighted empirical risk minimization problem (ERM), which gives rise to the optimal model parameters:
W arg mim Σ Wi e(ys.. fow (x:),,
where E(.,) .) is an instance wise loss function (e.g., binary cross-entropy, mean ween-ssquree-eeror (MSE) loss, etc.) and w E 13" are data weights that are fixed at training time. If wi 1, then the point z; (x;; y/) is part of the training data set, otherwise it is not. During model training, we set = 1 Vi. that is, the decision maker uses all available training instances at training time. In the optimization expressed equation 1, the model parameters w are usually an implicit function of the data weight vector w and we write ww to highlight this fact; in particular, when all training instances are used we write W1, where 1 E R is vector of 1s. In summary, we have introduced the weighted ERM problem since it allows us to understand the impact of arbitrary data deletion patterns on actionable explanations as we allow users to withdraw their entire input z; = (yi, x;) from the training set used to train the model fwi. Next, we present the recourse model we consider.
The Recourse Problem in the Context of the Data Deletion Mechanism. We follow an established definition of counterfactual explanations originally proposed by Wachter et al. (2018). For given model fw.. : RRd > RR parameterized by w and a distance function d(..)) :) X x X + R4, the problem of finding recourse x
for factual instance x is given by:
8 E arg min (fw.. (x + 8') - s)² + X d(x, x 6'),
(2)
8'E,AA
where À > 0 is scalar tradeoff parameter and denotes the target score. In the optimization from equation 2, the optimal recourse action 8 usually depends on the model parameters and since the model parameters themselves depend on the exact data weights configuration we write 6w. to highlight this fact. The first term in the objective on the right-hand hand-side of equation 2 encourages the outcome fwo (x) to become close to the user-defined target score s, while the second term encourages
3

---

Published as a conference paper at ICLR 2023
the distance between the factual instance and the recourse X x Sw.x x to be low. The set of constraints Ad ensures that only admissible changes are made to the factual x.
Recourse Robustness Through the Lens of the Right to be Forgotten. We first introduce several key terms, namely, prescribed recourses and recourse outcomes. A prescribed recourse x refers to a recourse that was provided to end user by recourse method (e.g., salary increased by $500). The recourse outcome f(x) is the model's prediction evaluated at the recourse. With these concepts in place, we develop two recourse instability definitions.
Definition 1. (Recourse outcome instability) The recourse outcome instability with respect factual instance x, where at least one data weight set to 0, is defined as follows:
Ax(w) = fw. (xx) - fww (x1));
(3)
where Swa (x1) is the prediction at the prescribed recourse 81 based on the model that uses the full training set (i.e., fw:) and fw.. (x1) is the prediction at the prescribed recourse for an updated model and data deletion requests have been incorporated into the predictive model (ie.. fwoh.
The above definition concisely describes the effect of applying "outdated"" recourses to the updated model. We assume that only the model parameters are being updated while the prescribed recourses remain unchanged. For discrete model with nition 1 captures whether the prescribed recourses will be invalid (Ax 1) after deletion of training instances (see Fig. la). To obtain invalidation rates of recourses for continuous- with target value 8, we can also apply Definition I with discretized (x = [x() > s). where T denotes the indicator function.
322
f
Updated houndary [ww Invalidated recourse
{0, 1}. Defi-
Original boundaryy f
model
In Definition 2, consistent with related work (e.g.. Wachter et al. (2018)), the distance function d is specified to be p-norm and the recourse is allowed to change due to model parameter updates.
(a)
Recourse Outcome Instability
222
f =1
Updated recourse
Updated houndary: [w Invalidated recourse
Definition 2. (Recourse action instability) The Recourse action instability with respect to faciual input x. where at least one data weight set to 0, is defined as follows:
Original boundary: fwr
T (w) 1 -
(4)
=
where p E [1, 20), and Xw is the recourse obtained for the model trained the data instances that remain present in the data set after the deletion request.
(b) Recourse Action Instability
Definition 2 quantifies the extent to which the prescribed recourses would have to additionally change to still achieve the desired re- course outcome after data deletion requests (i.c., X see Fig. 1b). Note that are interested in how the optimal low cost recourse changes even if the outdated recourse would remain valid. Using our invalidation measures defined above, in the next section, we formally study the trade-off's between actionable explanations and
Figure 1: Visualizing the two key robustness notions. Fig. la, recourse X₁ for an input x is invalidated due to a model up- date. In Fig. 1b, recourse is ad- ditionally recomputed (i.c., X to avoid recourse invalidation. the right to be forgotten. To do so, we provide data dependent upper bounds on the invalidation measures from Definitions I and 2, which practitioners can use to probe the worst-case vulnerability of their algorithmic recourse to data deletion requests.
4 TRADE-OFFS BETW. ALG. RECOURSE AND THE RIGHT TO BE FORGOTTEN
Here we relate the two notions of recourse instability presented in Definitions and to the vulnerability of the underlying predictive model with respect to data deletion requests. We show that the introduced instability measures are directly related to data points with a high influence on the parameters after deletion.
Analyzing the Instability Measures. With the basic terminology in place, we provide upper bounds for the recourse instability notions defined in the previous section when the underlying models are
4

---

Published as a conference paper at ICLR 2023
linear overparameterized neural networks. Throughout our analysis, the term dj == W1 w- has an important impact. measures the difference from the original parameters W1 to the parameter vector w-, obtained after deleting the i-th instance (x,, 34) from the model. In the statistics literature, this term is also known as the empirical influence function (Cook & Weisherg, 1980). Below we provide upper bound for recourse outcome instability in linear models.
Proposition 1 (Upper bound on recourse outcome instability for linear models). For the linear regression model f(x) = w x with model parameters wt. = (X (x)x)-XX Y, an upper bound for the recourse invalidation from Definition 1 by removing instance from the training set is given by:
x S
|x|1l
max ||d/12, (E!n)
(5)
where d! = -WL WL,-i
x x; 1- 7 ys w. x, and h2: = x! (X (xX -x;
The term X X xx;
dwL describes how sensitive the model parameters are to yi. while the
dy:
residual T; captures how well y/s can be fit by the model. On the contrary, the term hys from the denominator is known as the leverage and describes how atypical is with respect to all training inputs X. In summary, data instances that have influential labels or are atypical will have the highest impact when deleted. Next, provide generic upper bound on recourse action instability.
Proposition 2 (Upper bound on recourse action instability). For any predictive model with scoring function f Rd > R. an upper bound for the recourse instability from Definition! 2 by removing an instance 2, = (x. y) from the training set is given by:
Dõ Dw
2 S <|doll2
(w)
dr,
where D6 denotes the Jacobian of optimal recourse with the corresponding operator matrix norm, Dw
w = 7 + (1 --)) wi with w- being the optimal model parameters with the i-th training instance removed from the training set, and d, W W---
The norm of the Jacobian of optimal recourse indicates the local sensitivity of optimal recourse with respect to changes in model parameters w. High magnitudes indicate that a small change in the parameters may require fundamentally different recourse action. The total change by the integral over these local sensitivities, which means that low local sensitivities along the path will result in a low overall change. Next, we specialize this result the case of linear models.
be bounded
Corollary (Upper bound on recourse action instability for linear models). For the linear model f(x) W| x with model parameters wL = (X" X) ' T Y, an upper bound for the recourse action instability when 0, - 0 by removing an instance from the training set is given by:
max iE(n]
|dd(ll2)
min() well2 mingeja [WW.-1l12)
under the condition that w. Wt,-i 2 (no diametrical weight changes), where WL,-1 Wt dd the weight after removal of training instance and d = xx -lx;
(w.-w,x.)
1-ha his
For models trained on large data sets, the absolute value of the model parameters' norm ||w,,] will not change much under deletion of single instance. Therefore argue that the denominator min(I) (I| wL min || [L,-+ll2) = [|w/]] Thus, recourse action instability is mainly determined by
the sensitivity model parameters to deletion, max4e[n]
|| scaled by the ratio of [x||a T|wi]]2"
Neural Tangent Kernels. Studying the relation between deletion requests and the robustness of algorithmic recourse for models as complex neural networks requires recent results from computational learning theory. In particular, we also rely on insights on the behaviour of over- parameterized neural networks from the theory of Neural Tangent Kernels (NTKs), which we will now briefly introduce. Thus we study our robustness notions for neural network models in the overparameterized regime with ReLU activation functions that take the following form:
faNN(x)
1 aj relu(w].xr x).
Σ
(8)
Vk
5

---

Published as a conference paper at ICLR 2023
where W [W1...... Wil E Bd and [a.,..., 04] R To concretely study the impact of data deletion on recourses in non-linear models such as neural networks, we leverage ideas from the neural tangent kernel (NTK) literature (Jacot al., 2018; Lee et al., 2019; Arora et al., 2019; Du et al., 2019). The key insight from this literature for the purpose of our work is that infinitely wide neural networks can be expressed as kernel ridge regression problem with the NTK under appropriate parameter initialization, and gradient descent training dynamics. In particular, in the limit as the number of hidden nodes + oc, the neural langent kernel associated with two-layer ReLU network has closed-fore form expression (Chen & Xu, 2021; Zhang & Zhang, 2021) (see Appendix A.5):
x x π arcos
X
|X|
K (x,,
(9)
2T
Thus, the network's prediction at an input x can be described by:
fNIK (x) = (K (x, X)) WNIK:
(10)
where X E IRad is the input data matrix, K XX X) R is the NTK matrix evaluated on the
training data points: [K X) ~ (x, x,) and WNTK (K (X. X) + 3I,) "y solves
the lg regularized minimization problem with MSE loss where Y R" are the prediction targets.
With this appropriate terminology in place we provide an upper bound on recourse outcome instability of wide neural network models.
Proposition 3 (Upper bound on recourse outcome instability for wide neural networks). For the NTK model with Wyrk = (X,(X, + BI,) 3 an upper bound for the recourse invalidation from Definition I by removing instance (x, y) from the training set is given by:
Ax | |K (x1, X)|l2 max
|| 1|,,
(11)
iE(n)
where a.TKK Kes kik,, Y, where k; is the i-th column of the matrix (K (X, + BI.) and küa is its i-th diagonal element.
Intuitively, d,T is the linear model analog to dt and d. represents the importance that the point z; 34) has on the model parameters WNTK.
In practical use-cases, when trying to comply with both the right to data deletion and the right to actionable explanations, our results have practical implications. For example, instances with high influence captured by d, should be encountered with caution during model training in order to provide reliable recourses the individuals who seek recourse. summary, our results suggest that the right to data deletion may be fundamentally at odds with reliable state-of-the-art actionable explanations as the removal of an influential data instance can induce a large change in the recourse robustness, the extent to which is primarily measured by the empirical influence function d,.
FINDING THE SET OF MOST CRITICAL DATA POINTS
The Objective Function. In this section, we present optimization procedures that can be readily used to assess recourses' vulnerability to deletion requests. On this way, we start by formulating our optimization objective. We denote by m E (A, $(2)) the measure we want to optimize for. We consider the summed instability of over the data set by omitting the subscript ExeDi., Ax. Our goal is to find the smallest number of deletion requests that leads to a maximum impact on the instability measure m. To formalize this, define the set of data weight configurations:
e.g., A
rg = {w Maximally [a n| entries of w are 0 and the remainder is 1.].
(12)
In equation 12, the parameter a controls the fraction of instances that are being removed from the training set. For fixed fraction our problem of interest becomes:
arg max mm)). w
(13)
Fundamental Problems. When optimizing the above objective we face two fundamental problems: (i) evaluating m(w) for many weight configurations w can be prohibitively expensive the objective

---

Published as a conference paper at ICLR 2023
defined implicitly through solutions of several non-linear optimization problems (i.e., model fitting and finding recourses). Further, (ii) even for an objective m(w) which can be computed in constant polynomial time optimizing this objective can still be NP-hard (a proof is given in Appendix A.3).
Practical Algorithms. We devise two practical algorithms which approach the problem in equa- tion 13 in different ways. As for the problem of computing m(w) in (i), we can either solve this by (a) using a closed-form expression indicating the dependency of m on w or (b) by using an approximation of m that is differentiable with respect w. As for the optimization in (ii), once we have established the dependency of m on w we can either (a) use gradient descent approach or (b) we use greedy method. Below we explain the individual steps required for our algorithms.
5.1 COMPUTING THE OBJECTIVE
In the objective m(w), notice the dependencies Ax(w) Ax (S(w(w), x)) for the recourse outcome instability, and (2 (w) 2 (5(w(w), x))) for the recourse action instability. In the following, we briefly discuss how efficiently compute each of these functions without numerical optimization.
Model parameters from data weights w(w). For the linear model, an analytical solution can be obtained, Wr. Wt. (w) (X (x) -1 X ΩY, where Ω diag(w). The same goes for the NTK model where WNIx Ω ( x)nt Si) 's Y (Busuttil & Kalnishkan, 2007, Eqn. 3). When no closed-form expressions for the model parameters exist, we can resort to the infinitesimal jackknife (IJ) (Jaeckel, 1972; Efron, 1982; Giordano et al., 2019b;a), that can be seen
linear approximation to this implicit function. We refer to Appendix C for additional details on this matter.
Model prediction from model parameters f(w,x) x). Having established the model parameters, evaluating the prediction at given point can be quickly done even in a differentiable manner with respect w for the models we consider in this work.
Recourse action from model parameters 8(w, Estimating the recourse action is more chal- lenging it requires solving equation 2. However, differentiable solution exists for linear mod- els, where the optimal recourse action is given by 8, s-w wi,(w. When the underly- ing predictor wide neural network we can approximate the recourse expression of the corre- s-fw.NI(xx) sponding NTK, δNTK RV X+ X+1| WNTK (w)), which stems from the first-order taylor expansion NI + 5) xe (I) WNIK (w) with WNTK (w) = VxK X) WNI((W).
[+]|]
5.2 OPTIMIZING THE OBJECTIVE FUNCTION
The Greedy Algorithm. We consider the model on the full data set and compute the objective function m(w) under deletion of every instance (alone). We then select the instance that leads to the highest increase in the objective. We add this instance to the set of deleted points. Subsequently, refit the model and compute the impact of deletion for every second instance, when deleted in combination with the first one. Again, we add the instance that results in the largest increase to the set. Iteratively repeating these steps, we identify more instances to be deleted. Computational complexity depends on the implementation of the model weight recomputation, which is required Oann²) times.
The Gradient Descent Algorithm. Because our developed computation of m(w) can be made differentiable, we also propose a gradient-based optimization framework. We consider the relaxation of the problem in equation 13,
arg max m(w) - ||1 wllor (0(
(14)
where the to norm encourages to change as few data weights from to 0 as possible while few removals of training instances should have maximum impact on the robustness measure. The problem in equation 14 can be further relaxed to a continuous and unconstrained optimization problem. To do so we recently suggested stochastic surrogate loss for the Eu term (Yamada et al., 2020). Using this technique, a surrogate loss for equation 14 can be optimized using stochastic gradient descent (SGD). We refer to Appendix C for more details and pseudo-code of the algorithms.
7

---

Published as a conference paper at ICLR 2023
% Recourees Invalidaeed
dice
% Rocourses Invalidated
sele
% Recourses Invalidated
200
2000
300
73
75
18
12
655677 6
101111111455
101112131415
2 5 7 9 111113111
Number Training fratances Removed
Number
Iraeances Removed
Number Training Inetances Removed
gooedy. linng
greedy,
nundom, lanng
ramdon,
(a) Admission
R.Roosarss Invaiskaaa
dice
Rocrureee Invaledrted
100
To Rooosssse InvoRibited
cem
Number Triiiin Iratancc Remuved
Number Training Instanoee Removed
Namber Training Inatance Removved
greedy, Unnog
greedy, nik
random, lineeg
candom, okk
Heloc
Figure 2: Measuring the tradeoff between recourse outcome instability and the number of deletion requests for both the Admission and the Heloc data sets for regression and NTK models and various recourse methods. Results were obtained by greedy optimization; Appendix B for SGD results.
EXPERIMENTAL EVALUATION
We experimentally evaluate framework in terms of its ability find significant recourse invalida- tions using the instability measures presented in Section 3.
Data Sets. For experiments on regression tasks we provide results for two classification datasets in the Appendix B. First, we use law school data from the Law School Admission Council (Admission). The council carried out surveys across 163 law schools in the US, in which they collected information from 21,790 law students across the US (Wightman, 1998). The data contains information on the students' prior performances. The task is to predict the students' first-year law-school average grades. Second, we use the Home Equity Line of Credit (Heloc) data set. Here, the target variable is score indicating whether individuals will repay the Heloc account within a fixed time window. Across both tasks we consider individuals in need of recourse if their scores lie below the median score across the data set.
two real-world data sets. In addition,
Recourse Methods. We apply our techniques to four different methods which aim to generate low-cost recourses using different principles: SCFE was suggested by Wachter et al. (Wachter et al., 2018) and uses gradient-based objective to find recourses, DICE (Mothilal et al., 2020) uses gradient-based objective to find recourses subject to a diversity constraint, and CEM (Dhurandhar et al., 2018) uses a generative model encourage recourses to lie on the data manifold. For all methods, we used the recourse method implementations from the CARLA library (Pawelczyk et al., 2021) and specify the é cost constraint. Further details on these algorithms provided in App. C.
For the purpose of our evaluation, we use both the recourse outcome instabil- ity measure and the recourse action instability measure presented in Definitions I and 2. We evaluate the efficacy of our framework to destabilize large fraction of recourses using a small number of deletion requests (up 14). To find critical instances, use the greedy and the gradient-based algorithms described in Sec. 5. After having established a set of critical points, we recompute the metries with the refitted models and recourses obtain ground truth result.
Evaluation Measures.
For the recourse outcome instability, our metric A counts the number of invalidated recourses. We use the median as the target score 8, i.e., if the recourse outcome flips back from positive leaning prediction (above median) to a negative one (below median) it is considered invalidated. When evaluating recourse action instability, we identify a set of critical points, delete these points from the train set and refit the predictive model. In this case, also have recompute the recourses to evaluate p We then measure the recourse instability using Definition 2 with p = 2. Additionally, compare with random baseline, which deletes points uniformly random from the train set. We compute these measures for individuals from the test set who require algorithmic recourse. To obtain standard errors, we split the test into folds and report averaged results these 5 folds.
8

---

Published as a conference paper at ICLR 2023
1.5
scfe
Ave. Arsolute change
scfe
Jwne absolute
0.9
4
6
8
10 13
10 13
Number Training Instances Remooed
Number Training Instances Removed
sgd, linrog random, linrog
sg4 ntk
sg4 linreg
sg4, ntk
random, nik
random, linreg
random, nik
(a) Admission
(b) Heloc
Figure 3: Quantifying the tradeoff between recourse action instability as measured in Definition and the number of deletion requests for both the Admission and the Heloc data sets for the SCFE method when the underlying model is linear or an NTK (results by SGD optimization).
Results. In Figure 2, we measure the tradeoff between recourse outcome instability and the number of deletion requests. We plot the number of deletion requests against the fraction of all recourses that become invalidated when up to A (1..... 14) training points are removed from the training set of the predictive model. When the underlying model linear, we observe that the removal of as few as 5 training points induces invalidation rates of all recourses that are as high as 95 % percent we observe a similar trend across all recourse methods. Note that similar trend is present for the NTK model; however, larger number of deletion requests (roughly 9) is required to achieve similar invalidation rates. Finally, also note that our approach is always much more effective at deleting instances than the random baseline. In Figure 3, we measure the tradeoff between recourse action instability and the number of deletion requests with respect to the SCFE recourse method when the the
underlying predictive model is linear or an NTK model. For this complex objective, more efficient SGD optimization. Again, we observe that our optimization method significantly outperforms the random baselines at finding the most influential points be removed.
Additional Models and Tasks. In addition to the here presented results, we provide results for classification tasks with (a) Logistic Regression, (b) Kernel-SVM and (c) ANN models on two additional data sets (Diabetes and COMPAS) in Appendix B. Across all these models, we observe that our removal algorithms outperform random guessing: often by up 75 percentage points.
Factors of Recourse Robustness. Our empirical results shed light on which factors are influential in determining robustness of trained ML. models with respect deletion requests. In combination with results from Fig. 4 (see Appendix B), our results suggest that linear models are more susceptible to invalidation in the worst-case but are slightly more robust when comes to random removals. Furthermore, the characteristics of the data set play a key role; in particular those of the critical points. We perform an additional experiment where we consider modified data sets without the most influential points identified by our optimization approaches. In Appendix B, initial results show that this simple technique decreases the invalidation probabilities by up to percentage points.
7 DISCUSSION AND CONCLUSION
In this work, we made the first step towards understanding the tradeoffs between actionable model explanations and the right to be forgotten. We theoretically analyzed the robustness of state-of-the-art recourse methods under data deletion requests and suggested (i) a greedy and (ii) maddient-based algorithm to efficiently identify a small subset of individuals, whose data, when removed, would lead to invalidation of a large number of recourses for unsuspecting other users. Our experimental evalua- tion with multiple real-world data sets on both regression and classification tasks demonstrates that the right to be forgotten presents a significant challenge to the reliability of actionable explanations.
Finally, our theoretical results suggest that the robustness to deletion increases when the model parameter changes under data deletion remain small. This formulation closely resembles the definition of Differential Privacy (DP) (Dwork et al., 2014). We therefore conjecture that the reliability of actionable recourse could benefit from models that have been trained under DP constraints. As the field of AI rapidly evolves, data protection authorities will further refine the precise interpretations of general principles in regulations such GDPR. The present paper contributes towards this goal theoretically, algorithmically, and empirically by providing evidence of tensions between different data protection principles.

---

Published as a conference paper at ICLR 2023
Ethics statement. Our findings raise compelling questions the deployment of counterfactual explanations in practice. First of all, Are the two requirements of actionable explanations and the right to be forgotten fundamentally at odds with another? The theoretical and empirical results in this work indicate that for many model and recourse method pairs, this might indeed be the case. This finding leads to the pressing follow-up question: How can practifioners make sure that their recourses stay valid under deletion requests? A first take might be to implement the principle of data minimization (Biega al., 2020; Biega & Finck, 2021; Shanmugam et al., 2022) in the first place, i.e., exclude the k most critical data points from model training.
Acknowledgments. We would like to thank the anonymous reviewers for their insightful feedback. MP would like to thank Jason Long, Emanuele Albini. Jiāháo Chén, Daniel Dervovic and Daniele Magazzeni for insightful discussions early stages of this work.
REFERENCES
Emanuele Albini, Jason Long, Danial Dervovic, and Daniele Magazzeni. Counterfactual shapley addi- tive explanations. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAccT), 2022.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias:
There's software used across the country to predict future criminals. and it's biased against blacks, 2016.
Javier Antorán, Umang Bhatt, Tameem Adel, Adrian Weller, and José Miguel Hernández-Lobato. Getting a clue: A method for explaining uncertainty estimates. In International Conference on Learning Representations (ICLR), 2021.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
André Artelt, Valerie Vaquet, Riza Velioglu, Fabian Hinder, Johannes Brinkrolf, Malte Schilling, and Barbara Hammer. Evaluating robustness of counterfactual explanations. arXiv:2103.02355: 2021.
Asia J. Biega and Michèle Finck. Reviving purpose limitation and data minimisation in data-driven systems. Technology and Regulation, 2021.
Asia J. Biega, Peter Potash, Hal Daumé, Fernando Diaz, and Michèle Finck. Operationalizing the legal principle of data minimization for personalization. In ACM(43) SIGIR '20, pp. 399-408, 2020.
Emily Black, Zifan Wang, Matt Fredrikson, and Anupam Datta, Consistent counterfactuals for deep models. 1xXi::2100003109 2021.
Steven Busuttil and Yuri Kalnishkan. Weighted kernel regression for predicting changing dependen- cies. In European Conference on Machine Learning, pp. 542. Springer, 2007.
Gavin C Cawley and Nicola LC Talbot. Fast exact leave-one-out cross-validation of sparse least- squares support vector machines. Neural networks, 17(10):1467-1477 2004.
Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same (rkhs). In International Conference on Learning Representations (ICLR), 2021.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. Advances in neural information processing systems (NeurIPS), 22, 2009.
R Dennis Cook and Sanford Weisberg. Characterizations of empirical influence function for detecting influential cases in regression. Technometrics, 22(4):495-508, 1980.
Lehel Csató and Manfred Opper. Sparse on-line gaussian processes. Neural computation, 14(3): 641-668, 2002.
Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl. Multi-objective counterfactual explanations. In International Conference on Parallel Problem Solving from Nature, pp. Springer, 2020.
10

---

Published as a conference paper at ICLR 2023
Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun-Cher Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Ricardo Dominguez-Olmeed Amir-Hossein Karimi, and Bernhard Schölkopf. On the adversarial robustness of causal algorithmic recourse. In International Conference Machine Learning (ICML), 2022.
Finale Doshi-Veler and Been Kim. Towards rigorous science of interpretable machine learning. 2017.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. In International Conference on Learning Representations (ICLR), 2019.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor, Comput. Sci., 9(3-4):211-40) 2014.
Bradley Efron. The jackknife, the bootstrap and other resampling plans. SIAM, 1982.
Michele Finck and Asia J Biega. Reviving purpose limitation and data minimisation in data-driven systems. Technology and Regulation, 2021:44-61, 2021.
GDPR. Regulation (eu) 2016/679 of the european parliament and of the council. Official Journal of the European Union, 2016.
Amirata Ghorbani and James Zou, Data shapley: Equitable valuation of data for machine learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97, pp. 2242-2251. PMLR, 2019.
Amirata Ghorbani, Michael Kim, and James Zou. A distributional framework for data valuation. In International Conference on Machine Learning (ICML), pp. 3535-3544. PMLR, 2020.
Antonio Ginart, Melody Y. Guan, Gregory Valiant, and James Zou. Making ai forget you: Data deletion machine learning. In Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada, 2019.
Ryan Giordano, Michael I. Jordan, and Tamara Broderick. A higher-order swiss army infinitesimal jackknife. ArXiv, bbss/190..12111 2019a.
Ryan Giordano, William Stephenson, Runjing Liu, Michael Jordan, and Tamara Broderick. A swiss army infinitesimal jackknife. In Proceedings of the Twenty-econd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019b.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020a.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations. arXiv:2003.0280 029600 2020b.
Abigail Goldsteen, Gilad Ezov, Ron Shmelkin, Micha Moffie, and Ariel Farkash. Data minimization for gdpr compliance in machine learning models. Al and Ethics, pp. 1-15, 2021.
Sara Hooker, Dumitru Erhan, Pieter-Jan Kindermans, and Been Kim. A benchmark for interpretabil- ity methods deep neural networks. In Advances Neural Information Processing Systems (NeurIPS), 2019.
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In Arindam Banerjee and Kenji Fukumizu (eds.). Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 130.
PMLR. WMLR, 2021.
11

---

Published as a conference paper at ICLR 2023
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kerne:: Convergence and generalization in neural networks. Advances in neural information processing systems (NeurIPS), 31, 2018.
L Jaeckel. The infinitesimal jackknife. memorandum. Technical report, MM 72-1215-11, Bell Lab. Murray Hill, NJ, 1972.
Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Model-agnostic counterfactual explanations for consequential decisions. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computa- tions, pp. 85-103. Springer, 1972.
Thibault I Laugel, Marie-Jeanne Lesot, Christophe Marsala, Xavier Renard, and Marcin Detyniecki. Inverse classification for comparison-basel interpretability in machine learning. arXiv preprini arXiv:/7/2.08444, 2017.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems (NeurIPS), 32, 2019.
Divyat Mahajan, Chenhao Tan, and Amit Sharma. Preserving causal constraints in counterfactual explanations for machine learning classifiers. arXiv preprint arXiv: 1912.03277, 2019.
Rupert G Miller Jr. An unbalanced jackknife. The Annals of Statistics, pp. 880-891, 1974.
Ramaravind K. Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*), 2020.
CA OAG. Cepa regulations: Final regulation text. Office of the Attorney General, California Department of Justice, 2021.
Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. Learning model-agnostic counterfactual explanations for tabular data. In Proceedings of The Web Conference 2020 (WWW). ACM, 2020a.
Martin Pawelezyk, Klaus Broelemann, and Gjergji. Kasneci. On counterfactual explanations un- der predictive multiplicity. In Proceedings of the 36th Conference on Uncertainty Artificial Intelligence (UAI), pp. 809-818. PMLR, 2020b.
Martin Pawelczyk, Sascha Bielawski, Johan Van den Heuvel, Tobias Richter, and Gjergji Kasneci. Carla: A python library to benchmark algorithmic recourse and counterfactual explanation al- gorithms. In Advances in Neural Information Processing Systems (NeurIPS) (Benchmark and Datasets Track), 2021.
Martin Pawelczyk, Chirag Agarwal, Shalmali Joshi, Sohini Upadhyay, and Himabindu Lakkaraju. Exploring counterfactual explanations through the lens ofadversarial examples: theoretical and empirical analysis. In International Conference Artificial Intelligence and Statistics (AISTATS),
2022.
Martin Pawelczyk, Teresa Datta, Johannes van-den Heuvel, Gjergji Kasneci, and Himabindu Lakkaraju. Algorithmic recourse in the face of noisy human responses. In International Conference on Learning Representations (ICLR), 2023.
Kaivalya Rawal and Himabindu Lakkaraju. Interpretable and interactive summaries ofactionable recourses. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
Kaivalya Rawal, Ece Kamar, and Himabindu Lakkaraju. Algorithmic recourse in the wild: Under- standing the impact of data and model shifts. arXiv:2012.11788, 2021.
Yao Rong, Tobias Leemann, Vadim Borisov, Gjergji Kasneci, and Enkelejda Kasneci. A consistent and efficient evaluation strategy for attribution methods. In International Conference on Machine Learning (ICMI., 2022.
12

---

Published as a conference paper at ICLR 2023
Divya Shanmugam, Fermando Diaz, Samira Shabanian, Michèle Finck, and Asia J. Biega. Learning to limit data collection via scaling laws: A computational interpretation for the legal principle of data minimization. In ACM FAccT 22, 2022.
Dylan Slack, Sophie Hilgard, Himabindu Lakkaraju, and Sameer Singh. Counterfactual explanations can be manipulated. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
Thomas Spooner. Danial Dervovic, Jason Long, Jon Shepard, Jiahao Chen, and Daniele Magazzeni. Counterfactual explanations for arbitrary regression models. arXiv preprint #xXiv2216.152113 2021.
Beata Strack, Jonathan P DeShazo, Chris Gennings, Juan L Olmo, Sebastian Ventura, Krzysztof Cios, and John N Clore. Impact of hbalc measurement hospital readmission rates: analysis of 70,000 clinical database patient records. BioMed research international, 2014, 2014.
Gabriele Tolomei, Fabrizio Silvestri, Andrew Haines, and Mounia Lalmas. Interpretable predictions of tree-based ensembles via actionable feature tweaking. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD). ACM, 2017.
Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorithmic recourse. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
Berk Ustun, Alexander Spangher, and Y. Liu. Actionable recourse in linear classification. In Proceedings of the Conference Fairness, Accountability, and Transparency (FAT*), 2019.
Arnaud Van Looveren and Janis Klaise. Interpretable counterfactual explanations guided by proto- 2019.
types. arXiv preprint
Eduard Fosch Villaronga, Peter Kieseberg, and Tiffany Li. Humans forget, machines remember: Artificial intelligence and the right to be forgotten. Computer Law Security Review, 34(2): 304 313, 2018.
Paul Voigt and Axel Von dem Bussche. The general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 10:3152676, 2017.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: automated decisions and the gdpr. Harvard Journal of Law Technology, 31),), 2018.
Linda F Wightman. Lsac national longitudinal bar passage study. Isac research report series. 1998.
Yinjun Wu, Edgar Dobriban, and Susan Davidson. Deltagrad: Rapid retraining of machine learning models. In International Conference on Machine Learning (ICML), pp. 10355-10366. PMLR, 2020.
Bo Xie, Yingyu Liang. and Le Song. Diverse neural network learns true target functions. In Artificial Intelligence and Statistics (AISTATS), pp. 1224. PMLR, 2017.
Yutaro Yamada, Ofir Lindenbaum, Sahand Negahban, and Yuval Kluger. Feature selection using stochastic gates. In Proceedings of the 37th International Conference on Machine Learning
(ICML), volume 119, 13-18 Jul 2020.
Rui Zhang and Shihua Zhang. Rethinking influence functions of neural networks in the over- parameterized regime. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2021.
13

---

Published as a conference paper at ICLR 2023
APPENDIX
A THEORETICAL RESULTS
A.1 UPPER BOUNDS ON RECOURSE OUTCOME INSTABILITY
Proposition 1 (Upper Bound on Output Robustness for Linear Models), For the linear regression model f(x) w with weights given by w (X x Y. an upper bound for the output robustness by removing an instance (x, y) from the training set is given by:
x max M
||: || 1|2,
(15)
where (X x)- X; I-hu
Ti V1 w x; and hu x (X XX
-x-xx-x Xx;
Proof. By Definition have:
4x [ x1 -
(16)
(W1 w-i) X1
(x"xx x) 'x, (B1 - w xx)
X1
(by Theorem 1)
(17)
his
||d||2 ||>1||| ||2
(by
(18)
|x
||2
max ||d2|l2' ie(n)
(19)
where d, (X"X) (u w Tx,)
1-ha This completes our proof.
Proposition 2 (Upper Bound Output Robustness for NTK). For the NTK model with Wark
[K*(X,X) + AI,) 'Y, Y, an upper bound for the output robustness by removing an instance (x, y)
from the training set given by:
Ax K R (x1,
max ||d:||2, =E(n)
(20)
where d; = k.k, where k; is the i-th column the matrix (X,() BI.) and kai is its i-th diagonal element.
Proof. By Definition and the weight-update theorem by Zhang & Zhang (2021) (see Appendix A.4) and the assumption of the over- parameterized regime, we have:
4x [NTTK(81) (NiK(x1))
=I(K0
(x1, (X1 X))
WNIK (K (X1, x))
T(KX(XXXX II.)
1
k,k Y
(21)
kitt
I(KK (x1, X))
kik Y
(22)
Kii
||d/||2 K (x1, X2 (by Cauchy- Scnchy-Schwartz)
| max veln
||d/l2,,
(23)
where d;
k,k Y which completes our proof.
A.2 UPPER BOUNDS ON RECOURSE ACTION INSTABILITY
Proposition 3 (Upper Bound on Input Robustness). For the linear regression model f(x) = w Tx with weights given by (X x) 1 Y, an upper bound for the input robustness in the setting s = 0, A 0 by removing the i-th instance (Xi, yi) from the training set is given by:
4 4/2
(2) < </ddl1/ min(
(24)
w 12, w 122)
14

---

Published as a conference paper at ICLR 2023
under the condition that w w-s 0 (no diametrical weight changes), where w-, d, is the 13n
weight after removal of training instance and d; = x) Xi
w x.)
he
Proof. For a linear scoring function f(x) w' x with given parameters w', under the squared & norm constraint with balance parameter X, the optimal recourse action is given by (Pawelczyk et al., 2022):
8 (ww)
w'.
(25)
Using Definition 2, we can express the total change in 8 as path integral over changes in w, times the change D6 Dw they entail:
(2)
|0
8w 2 = 1110(w) (w) - 8 (w-s) l12
(26)
x
(7w + - (1-7)
w wi) (ww-wwllled
(27)
Dw
where Dd denotes the Jacobian, with the corresponding operator matrix norm. Defining =
Dw
yw + (1- 7) w-; and using |ww -will2 12. we obtain
|d:ll L.
Dg Dw
(w)
dr.
(28)
Because of the form 8(w') = f(w')w', where f(w') = wll++ is scalar function, its Jacobian
has the form
D6
w' (VS(W')) J(w')I. We will derive bound the Jacobian's
Dw
operator norm:
D6
D6
(W)
max
a
max |a]==1
w' (Vf((W)) a f(W)a
(29)
Dw
2
la |=1
Dw
V w
[|2 w + (w))
(30)
Additionally, we know that for 0, l.fww)) <
|
|x l2 [
The gradient is given by
wilg
- -I] w + X)x 2(s w x w
||V WW]
(31)
[| 1/2 + X)2
[12 + x)|| x12 + 2(s +
||
|
122
(32)
| 11
3||
(Using - 0,
(33)
| 2
In summary,
DO
3||x|| w
|x||a
4||x||2
(w)
|w
1|2
(34)
Dw
|w|
|
Because W is a line between w and w-s. its norm is bounded from below by || >
1 v min(/wwllz, (|w=) 2 v2 (lwllp ||w- - w vs (l]w]12 ||d. We can thus uni-
formly bound the integral and plug in the bound because of its positivity,
D5
(2) < ||d./12
dy
(35)
Dw
4 2
< ||d.||2
min( w 2; || w =112) d7
(36)
4 x
= ||d min(
(37)
|w 1|, (
which completes the proof.
n
15

---

Published as a conference paper at ICLR 2023
A.3 CALCULATING RECOURSE OUTCOME INSTABILITY FOR K DELETIONS IS NP-HARK
We can show that, for a general scoring function f. the problem defined in equation 13 is NP-hard. We make this proof by providing a function for which solving the recourse outcome invalidity problem is as hard as solving the well-known Knapsack problem, that has been shown to be NP-hard (Karp, 1972). The knapsack problem is defined follows:
max BE (0.1)
UiAI S.L. Σ yoth S W
(38)
where the problem considers fixed items (vi, Wi) with a value v; and knapsack weight yı > 0, and W is a fixed weight budget. The optimization problem consists of choosing the items that maximize the summed values but have weight lower than W. To solve this problem through the recourse outcome invalidation problem, we suppose there is a data point for each item. We can W of points to be deleted, where this condition ensures that we can remove the number of samples maximally required to solve the corresponding knapsack problem. Note that can always add a number of dummy points that have no effect such that the total number of data points is at least k. Suppose there a classifier function:
choose any k min y
El= 01(1 ww), Σ vi(1 wi) S W 0.
fu(x)
(39)
else
In this case, solving Eqn. 13 comes down to finding the set of items (i.e., removing the data points) that have maximum value, but stay under the threshold W. Thus, if we can solve Eqn. 13, the solution to the equivalent knapsack problem is given by q (1 - w).
A.4 AUXILIARY THEORETICAL RESULTS
We state the following classic result by Miller Jr (1974) without proof.
Theorem 1. (Leave-One-Ous Estimator, Miller Jr (1974)) Define (x,, y:) as the point to be removed
from the training set. Given the optimal weight vector = (X"))= xx-xxx X Y which solves for linear model under mean- geeean-quared-erree loss, the leave-one-out estimator is given by:
(y):
x+) (X'X) -x;
(3) w xx) d,-
w - w (X
(X
has
We restate the analtical solution for the NTK weights in case of a single deletion from Zhang & Zhang (2021).
Theorem 2. (Leave- (Leave-One-Ol One-Out weights for NTK models, Zhang & Zhang (2021)) Let WNTk
(K (X,X) X) + AIn)) > "'Y be the weight for the NTK model on the full data Kernel model, where K (X. X) the NTK matrix evaluated the training data points: [X*(X,X)]s X))x)]s K (x,:x)). Then, the NTK model that would be obtained when removing instance i, could be equivalently described by
fwiK (x) K
(x, WWTTWWWKKK- -x>(xxx
(K*((,X) + AL,)
1
q 9 )
9-1
where q-i the i-th column of the matrix Q (Ko0 AI,) -1 and 9-i is its i-th diagonal element of this inverse.
Proof. We begin by introducing some notation. Define:
Q = (xX) II
(40)
R R= = (x,
x +
(41)
then the analytical NTK model when considering the dataset with one instance x; removed given by
JNix (x) K (x, X T YY_
(42)
16

---

Published as a conference paper at ICLR 2023
where X-, denotes the data matrix with row i missing and Y- denotes the label vector with the i-th label missing. We have to show that this expression is equivalent to that stated in the theorem.
Without loss of generality, can assume the is the last point in the dataset (otherwise, we just permute the data set accordingly). Therefore, we can write the matrix Q in block form:
R K K (x,, X)
K (xi, x)
R
qi 9ts
(43)
Km (x,,
q
Through the block matrix inversion formula (see for example Csató & Opper (2002) (eqn. 52)) can write Q's inverse as
we
Q = R R q.q. R
R q
(44)
7 9, R
7-1
with y = 9is q, R q..
7 R q 7-1
We denote the i-th (and last) column of Q as q-i
and the i-th and last diagonal
element of the inverse as q-a = 7- We will now show, that the form of the weights given in the theorem (i.e., the weights for the points not removed) are equivalent to the weights that would have been computed by plugging in the smaller kernel matrix K x_1) in the analytical solution and the weight for the point deleted will have value of zero, i.c.
(K (KK.( SI,)
1 q-ii
Y
QQ- 10-1-19-00
9-
Y
(45)
q-ii
R YY-
(46)
To show this, we plug in the inversion formula Q-1 from equation 44 into equation 45 and using q- =7 11
Q
q 9-- Y
(47)
9-ii
R + R 9:
R
Y-R 7-1
RR' 9
R
1
7 R qi
7
R
9:
Y
(48)
7 r- R
7
7-1
Y;
R + R R-9.
9:9;
R
R-'R-
2
9:9.
R-
2
4. ))
Y
7 q. R
7
-7
2 q
R
7-
Y;
(49)
R
R : T R 1-11-- --1
R
q:g,
R-1
7- g r R
Y
(50)
q. R - q
R-1
Yi
R-1
0
Y
R YY
(51)
T
0
Y
Therefore, we have equivalence between equation 42 and the formulation in the theorem.
A.5 AN ANALYTICAL NTK KERNEL
In this section, we provide theoretical results that allow deriving the closed form solution of the NTK for the two-layer ReL.U network. First, the paper by Jacot et al. Jacot al. (2018) for the original derivation of the neural tangent kernel.
closed-form solution for two-layer ReLU networks. From (Zhang Zhang, 2021; Du al., 2019, Assumption 3.1) we obtain the definition of the Kernel matrix K (termed Gram matrix in the paper Du al. (2019)) for ReLU networks:
K K (x,, xj) Bw-N( [x] x, (w w x; 2 0, w.wT x, 20]
17

---

Published as a conference paper at ICLR 2023
[I(w'] JwwTo x; 2 0, wow x2 2 07]
x X3 SyEBwNN(0
x X,
arcos
X |
x
2m
The last reformulation uses an analytical result by Cho & Saul (2009). The derived result matches the one by Xie et al. (2017), which however does not provide a comprehensive derivation.
B ADDITIONAL EXPERIMENTAL RESULTS
Data sets for the Classification Tasks When considering classification tasks on the heloc and admission data sets, we threshold the scores based on the median to obtain binary target lahels. On the Admission data set (in the classification setting), a counterfactual found when the predicted first- year average score switches from 'below median' to 'above median'. We then count an invalidation if, after the model update, the score of counterfactual switches back to 'below median'. In addition to the aforementioned data sets, we use both the Diabetes and the Compas data sets. The Diabetes data set which contains information on diabetic patients from 130 different US hospitals (Strack et al., 2014). The patients are described using administrative (e.g.. length of stay) and medical records (e.g.. test results), and the prediction task is concerned with identifying whether a patient will be readmitted within the next 30 days. We sub sampled smaller data sets of 10000 points from this dataset. 8000 points are left to train the model, while 2000 points are left for the test set. The Compas data set Angwin et al. (2016) contains data for more than 10,000 criminal defendants in Florida. It is used by the jurisdiction to score defendant's 's likelihood of reoffending. We kept a small part of the raw data as features like name, id, casenumbers or date-time were dropped. The classification task consists of classifying instance into high risk of recidivism. Across all data sets, we dropped duplicate instances.
Discussing the Results As suggested in Section 6, here we are discussing the remaining recourse outcome invalidation results. We show these results for two settings. In Figure 4, we demonstrate the efficacy of our greedy deletion algorithm across 4 data sets on the classification tasks using different classification models (ANN, logistic regression, Kernel-SVM), For the logistic regression and the jackkniff approximation to calculate the probitively expensive ANN model, we use the infinitesimal jackknife
retraining step as described in Section 5. We observe that our method well outperforms random guessing. The results also highlight that while the NTK theory allows to study the deletion effects from theoretical point of view, if one is interested in empirical worst-case approximations, the infinitesimal jackknife can be a method of choice. As we observe this pattern across all recourse methods, we hypothesize that this is related to the instability of the trained ANN models, and we leave an investigation of this interesting phenomenon for future work.
Additionally, in Figure 5, we compare our SGD-based deletion algorithm to the greedy algorithm. For the SGD-based deletion results, we observe inverse-u-shaped curves on some method-data- model combinations. The reason for this phenomenon can be explained follows: when the to regularization strength (i.e., 1/) is not strong enough, then the importance weights for the k-th removal with A: become more variable (i.e., SGD does not always select the most important data weight for larger k). This drop in performance can be mitigated by increasing the strength of the lo regularizer within our SGD-based deletion algorithm.
In Figure 6, we study a simple removal strategy aimed at increasing the stability of algorithmic recourse. To this end, we identified the 15 points that lead to the highest invalidation on the NTK and linear regression models when the underlying recourse method is SCFE. Using our greedy method, we remove these 15 points from the training data set, and we then then rerun our proposed greedy removal algorithm. This strategy leads to an improvement of up to 6 percentage points over the initial model where the most critical points were included, suggesting that the removal of these critical points can be used to alleviate the recourse instability issue. In future work, we plan to investigate strategies that increase the robustness of algorithmic recourse even further.
Finally, in Figure 7 we study how well the critical points identified for the NTK model would invalidate a wide 2-layer ReLU network with 10000 hidden nodes. To study that question, we identified the points that lead to the highest invalidation on the NTK using our greedy method, and we then use these identified training points to invalidate the recourses suggested by the wide ANN. As before, we are running these experiments on the full data set across 5 folds. Figure 7 demonstrates
18

---

Published as a conference paper at ICLR 2023
the results of this strategy for the SCFE recourse method. We that this strategy increases the robustness up to 30 percentage points over the random baseline, suggesting that critical points under NTK can be used to estimate recourse invalidation for wide ANN models.
%o Receursss Invalideted
Ro.oonnccc Brvalidttdd
"...arursss Inveliddaeed
cem
100
100
100
50-
90
15
2
13
101112131110
Number Training fnatances Removed
Number Training Inetences Removed
Number Training Instences Removed
groedy, logrog
greedy, kernellsvvm
random, logreg
Jernellsvvm
greedy,
randoen,
(a) Admission
Recoeeseee Incalit.ted
dice
Th Rocouneees Invalidated
scle
Invelidated
100
1000
100
75
75
23-
12
10111220111
Number Training Inolances Removed
Number Training Inelances Removed
Number Training Instances Removed
gready, logreg
- greedy, kernellsvvm
randoen, logreg
random, kemnelssvmm
gredy
random,
(b) Heloc
% Recourses llvaatde
dice
% Recounses Inwallidated
scfe
Roceunes Iovalidated
cem
75
-3
9019111111 131112131615
101112131415
10111213445
Training Instances Removed
Training
Removed
Training
greody logreg
greedy, kemellssvm
randoen, logreg
random, kemnllssvm
greedy, and
randocn, ana.
(c) Compas
55 Receursss Invalidated
"s Reccuusss Brveliddtted
300
100
100
50-
50
23-
10 13 13
10 12
6 101112131410
Number Training Instances Removed
Number Training Instences Removed
Number Training Instences Removed
groedy, logrog
greedy, bernellsvvm
random, logreg
Jernellssvm
greedy.
randoen,
(d) Diabetes
Figure 4: Measuring the tradeoff between recourse outcome instability and the number of deletion requests for the Admission, Heloc, Diabetes and Compas data sets for logistic regression, kernel svm, and ANN models across recourse methods on classification tasks. Results were obtained by greedy optimization. The dotted lines indicate the random baselines.
C IMPLEMENTATION DETAILS
C.I DETAILS ON MODEL TRAINING
We train the classification models using the hyperparameters given Table The ANN and the Logistic regression models are fit using the quasi-newton lbgfs solver. We add L2-regularization to the ANN weights. The other methods are trained via their analytical solutions. Below, in Algorithms 1 and show pseudocodes for both our greedy and sgd-based deletion methods to invalidate the recourse outcome. In order to do the optimization with respect to the recourse action stability measure, slightly adjust Algorithm 2 to optimize the right metric from Definition 2.
19

---

Published as a conference paper at ICLR 2023
% Recourses Invalidated
% Recoursass Invalidated
scfe
% Rocourses Invalldated
Qem
100
100
75
75
75
85
25
13
12
2
6 15
1
5 101112151111
10112215111
Number Training Instances Removed
Training Instamoes Remooeed -
Training Instances Removeed
greedy, linreg
greedy, ntk
random, lirreg
random, nik
(a) Admission (Greedy)
5% RRorurse Invalidated
100
%% Kocourse Invalidated
100
Rocoouure Invallddted
100
cem
50
50
80
25
12
6
13
101111211111 12111115
101112131415
Number Trining Instances Removed
Number Taiiing Instanoes Removed
Number Thaining Instances Removee
agd, linzeg
agd, ntk
random, linreg
random, nik
(b) Admission (SGD)
% Reoourses Invaltesred
dice
%. Recourseo Invalldated
sefe
Nt Recorrsss Invalldated
cem
100
75
75
25-
25
5
15
3
10
1011 12111113141
Number Training Instances Removed
Number Training Instances Removed
Training Instances
greedy, linzeg
greedy, ntk
-
random, linreg
random, nik
(c) Heloc (Greedy)
% Recouus inv invaiidsted
100
dice
Rocouuse Invaiidated
100
sefe
100
cem
73
R.Roouuse
25
25
4 6 10 1011122331115
3
8 1011 12 1315
101112151415
Number Traiiing Instamces Removed
Training Removed
Training Instances Removed
agd, linreg
agd, ntk
-
random, linneg
candom, ntk
(d) Heloc (SGD)
Figure 5: Measuring the tradeoff between recourse outcome instability and the number of deletion requests for the Admission and Heloc data sets for linear regression and NTK models across recourse methods on regression tasks. Results were obtained by both SGD and Greedy optimization. The dotted lines indicate the random baselines.
C.2 DETAILS ON GENERATING THE COUNTERFACTUALS
For DICE, for every test input, we generate two different counterfactual explanations. Then we randomly pick either the first second counterfactual to be the counterfactual assigned the given input. Across all recourse methods the success rates lie above 95%, i.c., for 95% of recourse seeking individuals the algorithms can identify recourses. The only exception is admission data set for the NTK model, where the success rate lies at 60%. Across all recourse methods we set À -> 0. Note that the default implementations use early stopping once feasible recourse has been identified.
C.3 DETAILS THE to REGULARIZER
Since an lo regularizer is computationally intractable for high-dimensional optimization problems, have to resort approximations. One such approximation approach was recently suggested by Yamada et al. (2020). The underlying idea consists converting the combinatorial search problem continuous search problem distribution parameters. To this end, recall optimization
20

---

Published as a conference paper at ICLR 2023
scfe
scle
100
% Recoumes Invalidated
% Recuuess lnvalidatedd
75
greedy, nit random, linreg random, nikk
linreg (removal)
50
greedy (remova
randomm linreg (remoscal) random, nik (removal)
15
greedy linreg
greedy, linreg (removal)
greedy, nik
greedy, nik (pemoovll)
random, linreg
Fandrim, linreg (removal)
random, nik
random, nik (removal)
10 12 14
Number Training Instances Removed
Training Instances
(a) Heloc (Greedy)
(b) Admission (Greedy)
Figure 6: Measuring the efficacy of a simple removal strategy on the Heloc and Admission data set for linear and NTK regression models. We removed the 15 critical points identified for the linear and NTK models when the underlying recourse method is SCFE E and reran the removal algorithm on the remaining training set. Results were obtained by Greedy optimization. The dotted lines indicate the random baselines.
% Recourses Invalidated
scfe
100
75
50
25
0123
4
101112131415
Number Training Instances Removed greedy, annreg
random, annreg
(a) Admission (Greedy)
Figure 7: Measuring the tradeoff between recourse outcome instability and the number of deletion requests for the Admission data set for neural network regression model. We used the critical points identified for the NTK model to invalidate the recourses identified by a wide 2-layer ReL.U network with 10000 hidden nodes. Results were obtained by Greedy optimization. The dotted lines indicate the random baselines.
problem from the main text:
w- arg max m(w) - 17 || wolo- we(0,1)
(52)
We will now introduce Bernoulli random variables Z; E {0, 1} with corresponding parameters T; to model the individual wi. Instead of optimizing the objective above with respect to we will optimize
Model
Parameters
Linear Regression
OLS, no hyperparameters. B = 2 (Admission), 3 = 5 (other data sets)
NTK Regression
Logistic Regression
L2-Regularization with = 1.0 Gaussian Kernel with 1.0 (see Cawley & Talbot (2004))
Kernel-LSSVM ANN
L-Lay,r, 30 Hidden units, Sigmoid, a 10 (12--aegularization)
Table 1: Model hyperparameters used in this work
21

---

Published as a conference paper at ICLR 2023
Algorithm 1 Greedy recourse outcome invalidation
Required: Model: [w(1); Matrix of Recourses: X1 E Roxd, d: input dimension; q number of recourse points test set; nı # train points; M: max # deleted train points; invalidation target (() 1n for m 1: M do
> All training instances present
w (m)) f- w (m-1)
0nxq
Recourse outcomes b Invalidations present
J = Onxq
((m) i
(m) # }}
Set of train instances present at iteration m
for i ((m) do
W update_vis ( (m))
(ma) has additionally set weight i to 0. D wh
b Use analytical or solution for w(w) b New recourse outcomes
Y [ = fwe (X1) = =
[( < s)
Invalidation present
end for
index < arg max :1l
b Find point that leads to highest invalidation > Remove training point
(m)) [index] = 0
end for return: (Mr)
data weights indicating M removals
with respect to distribution parameters π.:
π arg max m (Z(())) - 1) || Z(T)
(53)
Since the above optimization problem is known to suffer from high- variance solutions, (Yamada et al., 2020) suggest to use a Gaussian based continuous relaxation of the Bernoulli variables:
Z: max (0, min(1, /4: + +:))
(54)
where 6, (0, d²), resulting in the following optimization problem:
1r arg max m (2())) - 7) || (())llo-
(55)
At inference time, the optimal weights are then given by ž max(0, mi,(1, Vi E [m]. To obtain discrete weights, we take the argmax over each individual Z..
C.4 DETAILS ON THE JACKKNIFE APPROXIMATION
When the model parameters approximate w(w) using the infinitesimal Jackknife (IJ) without having to optimize equation repeatedly (Jaeckel, 1972; Efron, 1982; Giordano et al., 2019b;a):
function of the data weights by solving equation 1 we
w
G.--1
(56)
where G and H2 are the Jacobian and the Hessian matrices of the loss function with respect to
the data weights evaluated the optimal model parameters w, i.e. G 1 (w; 1)
(x...() and H, 1 Σn (x).))))))))) Note that this technique computes the Hessian matrix dw H, only once. Using this Jackknife approximation, the Jacobian term Gw-1 becomes an explicit function of the data weights which makes the Jackknife approximation amenable to optimization.
Sw3w
22

---

Published as a conference paper at ICLR 2023
Algorithm 2 SGD recourse outcome invalidation
Required: Model: Sw(1); Matrix of Recourses: X, E Roxd, d: input dimension; q number of recourse points test set; nı # train points; M: max # deleted train points; invalidation target Mu are soft data weights that are opimized. Perform Step number of updates.
(1()) 1 for m Step do 1-loss-0.0 for : K do
D Use K Monte-Carlo Samples for the approximation
Sample E (m)
~ (0,
(m) max 0, min (1, (mm) ) Sample (soft) data weights in Yamada et al.
k
(2020)
(m) update_w(uu)
> Compute model weights from data
w R n,new
weights either analytically with IJ Predict with new weights and com- pute soft invalidation.
(m)
sigmoid (fmsm) (m) (X1)-9)
8 losss- 8-loss + || l/2
Add up soft inval. loss
end for ((m)
-' + 1-(p(());
Sparsity Regularizer from Yamada et al. (2020) Grad. Descent with Ir. ?
(m+1) / (m) V (m) 6-soss Ar-(ma)
end for removed ind argsort ar (S((ept+)))))) (Stept)))
Sort indices ascendingly
j=0
w w
while j < M do j=j+1
Binarize and fulfil max number M
end while return:
data weights indicating M removals
23


Reviews:
[{"review_id": "lVs0sn_tpeW", "reviewer": "Reviewer_2k5p", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "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.\n\nNote: 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.\n\n", "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.", "strength_and_weaknesses": "Strengths:\n- a novel direction, combines two questions which I have not seen combined before (recourse + deletion)\n- 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\n- the theoretical and experimental work both provide clear, concrete contributions to the central question of the paper\n\nWeaknesses:\n- 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?\n- 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\n- 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)\n- 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\n- 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\n- \"Evaluation Measures\" paragraph refers to the gradient-based method but I don't see it in Fig 2\n- \"... by up to 6 percentage points\" - I'm not sure I understand this result, might need more clarification in the paper\n- 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?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gPvBW2BWpCD", "reviewer": "Reviewer_9bdZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "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.", "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.", "strength_and_weaknesses": "### Strengths\n\n1. 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.\n2. 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.\n\n### Weaknesses\n\n1. 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?\n\n2. 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GEbVs2azJgG", "reviewer": "Reviewer_CkVr", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "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.", "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. ", "strength_and_weaknesses": "### Strengths\n\n- The studied problem is novel and interesting. Both algorithmic resource and the right to forgotten are very relevant and important.\n- The perspective of considering resource instability is interesting.\n- The paper is generally well written and organized.\n\n### Weaknesses\n- 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. \n\n\n- 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 \n> 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\n\n    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).\n\n- 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$).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "E8YKj_JIJzH", "reviewer": "Reviewer_8JMg", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "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.", "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.", "strength_and_weaknesses": "Strengths:\n1. The paper calls the newly formulated research problem that investigates connections between explainability and the right to be forgotten.\n2. The paper is well-written, clear and presented with interpretable results throughout.\n3. The paper presents several theoretical and practical insights towards building deletion robust applications from the perspective of both data and model.\n\nStrengths:\n1. The paper calls the newly formulated research problem that investigates connections between explainability and the right to be forgotten.\n2. The paper is well-written, clear and presented with interpretable results throughout.\n3. The paper presents several theoretical and practical insights towards building deletion robust applications from the perspective of both data and model.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster