# On the Trade-Off between Actionable
Explanations and the Right to be Forgotten

Martin Pawelczyk1, Tobias Leemann1, Asia Biega2, and Gjergji
Kasneci122footnotemark: 2
1University of Tübingen, Germany
2Max-Planck-Institute for Security and Privacy, Germany
Corresponding author<EMAIL_ADDRESS>senior author
contribution.

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

##  1 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) (Union,
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 of these models have the right
to _recourse_ (Voigt & Von dem Bussche, 2017), i.e., a constructive
instruction on how to act to arrive at a 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 a number of
algorithmic research questions. In particular, recent literature has focused
on the efficiency of deletion (i.e., how to 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 to remove data without
compromising model accuracy (Biega et al., 2020; Goldsteen et al., 2021)). An
aspect of data deletion which has not been examined before is _whether and how
data deletion may impact model explanation frameworks_. Thus, there is a need
to understand and systematically characterize the limitations of recourse
algorithms when personal user data may need to be deleted from trained ML
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 a small set
of individuals has decided to withdraw their data and, as a consequence of the
deletion request, the model needs to be updated (Ginart et al., 2019). In
particular, this work tackles the subsequent pressing question:

_What is 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 a 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 a
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 instability_.

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 a 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 to 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 framework to identify a small set of critical training data
points which, when removed, invalidates most of 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-art
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 an 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 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., 2018; Ustun et al., 2019; Van
Looveren & Klaise, 2019; Pawelczyk et al., 2020a; Mahajan et al., 2019;
Mothilal et al., 2020; Karimi et al., 2020; Rawal & Lakkaraju, 2020; Dandl et
al., 2020; Antorán et al., 2021; Spooner et al., 2021; Albini et al., 2022).
These approaches generate recourses assuming a static environment without data
deletion requests, where both the model and the recourse remain stable.

A related line of work has focused on determining the extent to 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 to the input instances (Artelt et 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 to 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 an 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 a 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 is 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-art 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.

##  3 Preliminaries

The Predictive Model and the Data Deletion Mechanism. We consider prediction
problems from some input space $\mathbb{R}^{d}$ to an output space
$\mathcal{Y}$, where $d$ is the number of input dimensions. We denote a sample
by $\mathbf{z}=(\mathbf{x},y)$, and denote the training data set by
$\mathcal{D}=\\{\mathbf{z}_{1},\dots,\mathbf{z}_{n}\\}$. Consider the weighted
empirical risk minimization problem (ERM), which gives rise to the optimal
model parameters:

$\displaystyle\mathbf{w}_{\bm{\omega}}=\operatorname*{arg\,min}_{\mathbf{w}^{\prime}}\sum_{i=1}^{n}\omega_{i}\cdot\ell\big{(}y_{i},f_{\mathbf{w}^{\prime}}(\mathbf{x}_{i})\big{)},$
(1)

where $\ell(\cdot,\cdot)$ is an instance-wise loss function (e.g., binary
cross-entropy, mean-squared-error (MSE) loss, etc.) and
$\bm{\omega}\in\\{0,1\\}^{n}$ are data weights that _are fixed at training
time_. If $\omega_{i}=1$, then the point
$\mathbf{z}_{i}=(\mathbf{x}_{i},y_{i})$ is part of the training data set,
otherwise it is not. During model training, we set $\omega_{i}=1~{}\forall i$,
that is, the decision maker uses all available training instances at training
time. In the optimization expressed in equation 1, the model parameters
$\mathbf{w}$ are usually an implicit function of the data weight vector
$\bm{\omega}$ and we write $\mathbf{w}_{\bm{\omega}}$ to highlight this fact;
in particular, when all training instances are used we write
$\mathbf{w}_{\bm{1}}$, where $\bm{1}\in\mathbb{R}^{n}$ is a 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
$\mathbf{z}_{i}=(y_{i},\mathbf{x}_{i})$ from the training set used to train
the model $f_{\mathbf{w}_{\bm{1}}}$. 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 a given model
$f_{\mathbf{w}_{\bm{\omega}}}:\mathbb{R}^{d}\xrightarrow{}\mathbb{R}$
parameterized by $\mathbf{w}$ and a distance function
$d(\cdot,\cdot):\mathcal{X}\times\mathcal{X}\to\mathbb{R}_{+}$, the problem of
finding a recourse $\check{\mathbf{x}}=\mathbf{x}+\bm{\delta}$ for a factual
instance $\mathbf{x}$ is given by:

$\displaystyle\bm{\delta}_{\bm{\omega},\mathbf{x}}\in\operatorname*{arg\,min}_{\bm{\delta}^{\prime}\in\mathcal{A}_{d}}\,(f_{\mathbf{w}_{\bm{\omega}}}(\mathbf{x}+\bm{\delta}^{\prime})-s)^{2}+\lambda\cdot\,d(\mathbf{x},\mathbf{x}+\bm{\delta}^{\prime}),$
(2)

where $\lambda\geq 0$ is a scalar tradeoff parameter and $s$ denotes the
target score. In the optimization from equation 2, the optimal recourse action
$\bm{\delta}$ usually depends on the model parameters and since the model
parameters themselves depend on the exact data weights configuration we write
$\bm{\delta}_{\bm{\omega},\mathbf{x}}$ to highlight this fact. The first term
in the objective on the right-hand-side of equation 2 encourages the outcome
$f_{\mathbf{w}_{\bm{\omega}}}(\check{\mathbf{x}})$ to become close to the
user-defined target score $s$, while the second term encourages the distance
between the factual instance $\mathbf{x}$ and the recourse
$\check{\mathbf{x}}_{\bm{\omega}}:=\mathbf{x}+\bm{\delta}_{\bm{\omega},\mathbf{x}}$
to be low. The set of constraints $\mathcal{A}_{d}$ ensures that only
admissible changes are made to the factual $\mathbf{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 $\check{\mathbf{x}}$ refers to a recourse
that was provided to an end user by a recourse method (e.g., salary was
increased by $500). The recourse outcome $f(\check{\mathbf{x}})$ is the
model’s prediction evaluated at the recourse. With these concepts in place, we
develop two recourse instability definitions.

$x_{1}$$f^{\prime}=0$$f^{\prime}=1$Original boundary:
$f_{\mathbf{w}_{\bm{1}}}$Updated boundary:
$f_{\mathbf{w}_{\bm{\omega}}}$Invalidated
recourse$\mathbf{x}$$\tilde{\mathbf{x}}_{\bm{1}}$$x_{2}$ (a) Recourse Outcome
Instability

$x_{1}$$f^{\prime}=0$$f^{\prime}=1$Original boundary:
$f_{\mathbf{w}_{\bm{1}}}$Updated boundary:
$f_{\mathbf{w}_{\bm{\omega}}}$Invalidated recourse Updated recourse
$\tilde{\mathbf{x}}_{\bm{\omega}}$$\mathbf{x}$$\tilde{\mathbf{x}}_{\bm{1}}$$x_{2}$
(b) Recourse Action Instability

Figure 1: Visualizing the two key robustness notions. In Fig. 1(a), recourse
$\tilde{\mathbf{x}}_{1}$ for an input $\mathbf{x}$ is invalidated due to a
model update. In Fig. 1(b), recourse is additionally recomputed (i.e.,
$\tilde{\mathbf{x}}_{\bm{\omega}}$) to avoid recourse invalidation.

######  Definition 1.

(Recourse outcome instability) The recourse outcome instability with respect
to a factual instance $\mathbf{x}$, where at least one data weight is set to
$0$, is defined as follows:

$\displaystyle\Delta_{\mathbf{x}}(\bm{\omega})=\big{\lvert}f_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathbf{w}_{\bm{1}}}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\check{\mathbf{x}}_{\bm{1}}}\big{)}-f_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathbf{w}_{\bm{\omega}}}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\check{\mathbf{x}}_{\bm{1}}}\big{)}\big{\rvert},$
(3)

where
$f_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathbf{w}_{\bm{1}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\check{\mathbf{x}}_{\bm{1}}})$
is the prediction at the prescribed recourse
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\check{\mathbf{x}}_{\bm{1}}}$
based on the model that uses the full training set (i.e.,
$f_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathbf{w}_{\bm{1}}}}$)
and
$f_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathbf{w}_{\bm{\omega}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\check{\mathbf{x}}_{\bm{1}}})$
is the prediction at the prescribed recourse for an updated model and data
deletion requests have been incorporated into the predictive model (i.e.,
$f_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathbf{w}_{\bm{\omega}}}}$).

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 a discrete
model with $\mathcal{Y}=\left\\{0,1\right\\}$, Definition 1 captures whether
the prescribed recourses will be invalid ($\Delta_{\mathbf{x}}=1$) after
deletion of training instances (see Fig. 1(a)). To obtain invalidation rates
of recourses for a continuous-score model with target value $s$, we can also
apply Definition 1 with a discretized
$f^{\prime}(\mathbf{x})=\mathbb{I}\left[f(\mathbf{x})>s\right]$, where
$\mathbb{I}$ denotes the indicator function.

In Definition 2, consistent with related work (e.g., Wachter et al. (2018)),
the distance function $d$ is specified to be a p-norm and the recourse is
allowed to change due to model parameter updates.

######  Definition 2.

(Recourse action instability) The Recourse action instability with respect to
a factual input $\mathbf{x}$, where at least one data weight is set to $0$, is
defined as follows:

$\Phi^{(p)}_{\mathbf{x}}(\bm{\omega})=\big{\lVert}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\check{\mathbf{x}}_{\bm{1}}}-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\check{\mathbf{x}}_{\bm{\omega}}}\big{\rVert}_{p},$
(4)

where $p\in[1,\infty)$, and
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\check{\mathbf{x}}_{\bm{\omega}}}$
is the recourse obtained for the model trained on the data instances that
remain present in the data set after the deletion request.

Definition 2 quantifies the extent to which the prescribed recourses would
have to additionally change to still achieve the desired recourse outcome
_after data deletion_ requests (i.e., $\check{\mathbf{x}}_{\bm{\omega}}$, see
Fig. 1(b)). Note that we 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-offs between actionable explanations and the right to be forgotten.
To do so, 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.

##  4 Trade-offs Betw. Alg. Recourse and the Right to be Forgotten

Here we relate the two notions of recourse instability presented in
Definitions 1 and 2 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 linear or overparameterized
neural networks. Throughout our analysis, we the term
$\mathbf{d}_{i}\coloneqq\mathbf{w}_{\bm{1}}-\mathbf{w}_{-i}$ has an important
impact. It measures the difference from the original parameters
$\mathbf{w}_{\bm{1}}$ to the parameter vector $\mathbf{w}_{-i}$ obtained after
deleting the $i$-th instance $(\mathbf{x}_{i},y_{i})$ from the model. In the
statistics literature, this term is also known as the empirical influence
function (Cook & Weisberg, 1980). Below we provide an 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(\mathbf{x})=\mathbf{w}_{\text{L}}^{\top}\mathbf{x}$ with model parameters
$\mathbf{w}_{\text{L}}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\mathbf{Y}$,
an upper bound for the recourse invalidation from Definition 1 by removing an
instance from the training set is given by:

$\displaystyle\Delta_{\mathbf{x}}\leq\lVert\check{\mathbf{x}}_{\bm{1}}\rVert_{2}\cdot\max_{i\in[n]}~{}\lVert\mathbf{d}_{i}^{\text{L}}\rVert_{2},$
(5)

where
$\mathbf{d}_{i}^{\text{L}}\coloneqq\mathbf{w}_{L}{-}\mathbf{w}_{L,-i}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{x}_{i}\cdot\frac{r_{i}}{1-h_{ii}}$,
$r_{i}=y_{i}-\mathbf{w}_{\text{L}}^{\top}\mathbf{x}_{i}$ and
$h_{ii}=\mathbf{x}_{i}^{\top}(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{x}_{i}$.

The term
$(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{x}_{i}=\frac{d\mathbf{w}_{\text{L}}}{dy_{i}}$
describes how sensitive the model parameters are to $y_{i}$, while the
residual $r_{i}$ captures how well $y_{i}$ can be fit by the model. On the
contrary, the term $h_{ii}$ from the denominator is known as the _leverage_
and describes how atypical $\mathbf{x}_{i}$ is with respect to all training
inputs $\mathbf{X}$. In summary, data instances that have influential labels
or are atypical will have the highest impact when deleted. Next, we provide a
generic upper bound on recourse action instability.

######  Proposition 2 (Upper bound on recourse action instability).

For any predictive model with scoring function
$f:\mathbb{R}^{d}\to\mathbb{R}$, an upper bound for the recourse instability
from Definition 2 by removing an instance $\mathbf{z}_{i}=(\mathbf{x},y)$ from
the training set is given by:

$\displaystyle\Phi^{(2)}_{\mathbf{x}}$
$\displaystyle\leq\lVert\mathbf{d}_{i}\rVert_{2}\int_{0}^{1}\bigg{\lVert}\frac{\mathbf{D}\bm{\delta}}{\mathbf{D}\mathbf{w}}\left(\tilde{\mathbf{w}}\right)\bigg{\rVert}_{2}d\gamma,$
(6)

where $\frac{\mathbf{D}\bm{\delta}}{\mathbf{D}\mathbf{w}}$ denotes the
Jacobian of optimal recourse with the corresponding operator matrix norm,
$\tilde{\mathbf{w}}\coloneqq\gamma\mathbf{w}+\left(1-\gamma\right)\mathbf{w}_{-i}$
with $\mathbf{w}_{-i}$ being the optimal model parameters with the i-th
training instance removed from the training set, and
$\mathbf{d}_{i}=\mathbf{w}-\mathbf{w}_{-i}$.

The norm of the Jacobian of optimal recourse indicates the local sensitivity
of optimal recourse with respect to changes in model parameters $\mathbf{w}$.
High magnitudes indicate that a small change in the parameters may require a
fundamentally different recourse action. The total change can be bounded 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 to the case of linear models.

######  Corollary 1 (Upper bound on recourse action instability for linear
models).

For the linear model $f(\mathbf{x})=\mathbf{w}_{\text{L}}^{\top}\mathbf{x}$
with model parameters
$\mathbf{w}_{\text{L}}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\mathbf{Y}$,
an upper bound for the recourse action instability when $s=0,\lambda\to 0$ by
removing an instance from the training set is given by:

$\displaystyle\Phi^{(2)}_{\mathbf{x}}\leq\left(\max_{i\in[n]}~{}\lVert\mathbf{d}_{i}^{\text{L}}\rVert_{2}\right)\frac{4\sqrt{2}\lVert\mathbf{x}\rVert_{2}}{\min(\lVert\mathbf{w}_{\text{L}}\rVert_{2},\min_{i\in[n]}\lVert\mathbf{w}_{\text{L},-i}\rVert_{2})},$
(7)

under the condition that
$\mathbf{w}_{\text{L}}^{\top}\mathbf{w}_{\text{L},-i}\geq 0$ (no diametrical
weight changes), where
$\mathbf{w}_{\text{L},-i}=\mathbf{w}_{\text{L}}-\mathbf{d}_{i}^{\text{L}}$ is
the weight after removal of training instance $i$ and
$\mathbf{d}_{i}^{\text{L}}=(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{x}_{i}\frac{(y_{i}-\mathbf{w}^{\top}_{\text{L}}\mathbf{x}_{i})}{1-h_{ii}}$.

For models trained on large data sets, the absolute value of the model
parameters’ norm $\lVert\mathbf{w}_{L}\rVert$ will not change much under
deletion of a single instance. Therefore we argue that the denominator
$\min(\lVert\mathbf{w}_{\text{L}}\rVert_{2},\min_{i\in[n]}\lVert\mathbf{w}_{\text{L},-i}\rVert_{2})\approx\lVert\mathbf{w}_{\text{L}}\rVert$.
Thus, recourse action instability is mainly determined by the sensitivity of
model parameters to deletion,
$\max_{i\in[n]}~{}\lVert\mathbf{d}_{i}^{\text{L}}\rVert_{2}$, scaled by the
ratio of
$\frac{\lVert\mathbf{x}\rVert_{2}}{\lVert\mathbf{w}_{\text{L}}\rVert_{2}}$.

Neural Tangent Kernels. Studying the relation between deletion requests and
the robustness of algorithmic recourse for models as complex as 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:

$\displaystyle
f_{\text{ANN}}(\mathbf{x})=\frac{1}{\sqrt{k}}\sum_{j=1}^{k}a_{j}\cdot\text{relu}(\mathbf{w}_{j}^{\top}\mathbf{x}),$
(8)

where $\mathbf{W}=[\mathbf{w}_{1},\dots,\mathbf{w}_{k}]\in\mathbb{R}^{d\times
k}$ and $\mathbf{a}=[a_{1},\dots,a_{k}]\in\mathbb{R}^{k}$. 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 et 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 a 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 $k\to\infty$, the neural tangent kernel associated with a two-layer ReLU
network has a closed-form expression (Chen & Xu, 2021; Zhang & Zhang, 2021)
(see Appendix A.5):

$\displaystyle
K^{\infty}(\mathbf{x}_{0},\mathbf{x})=\frac{\mathbf{x}_{0}^{\top}\mathbf{x}\left(\pi-\text{arcos}\left(\frac{\mathbf{x}_{0}^{\top}\mathbf{x}}{\lVert\mathbf{x}_{0}\rVert\lVert\mathbf{x}\rVert}\right)\right)}{2\pi}.$
(9)

Thus, the network’s prediction at an input $\mathbf{x}$ can be described by:

$\displaystyle f_{\text{NTK}}(\mathbf{x})$
$\displaystyle=\big{(}\mathbf{K}^{\infty}(\mathbf{x},\mathbf{X})\big{)}^{\top}\mathbf{w}_{\text{NTK}},$
(10)

where $\mathbf{X}\in\mathbb{R}^{n\times d}$ is the input data matrix,
$\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})\in\mathbb{R}^{n\times n}$ is the
NTK matrix evaluated on the training data points:
$[\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})]_{ij}=K^{\infty}(\mathbf{x}_{i},\mathbf{x}_{j})$
and
$\mathbf{w}_{\text{NTK}}=\big{(}\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})+\beta\mathbf{I}_{n}\big{)}^{-1}\mathbf{Y}$
solves the $\ell_{2}$ regularized minimization problem with MSE loss where
$\mathbf{Y}\in\mathbb{R}^{n}$ 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
$\mathbf{w}_{\text{NTK}}=\big{(}\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})+\beta\mathbf{I}_{n}\big{)}^{-1}\mathbf{Y}$,
an upper bound for the recourse invalidation from Definition 1 by removing an
instance $(\mathbf{x},y)$ from the training set is given by:

$\displaystyle\Delta_{\mathbf{x}}\leq\lVert\mathbf{K}^{\infty}(\check{\mathbf{x}}_{\bm{1}},\mathbf{X})\rVert_{2}\cdot\max_{i\in[n]}~{}\lVert\mathbf{d}_{i}^{\text{NTK}}\rVert_{2},$
(11)

where
$\mathbf{d}_{i}^{\text{NTK}}=\frac{1}{k_{ii}}\mathbf{k}_{i}\mathbf{k}_{i}^{\top}\mathbf{Y}$,
where $\mathbf{k}_{i}$ is the $i$-th column of the matrix
$\big{(}\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})+\beta\mathbf{I}_{n}\big{)}^{-1}$,
and $k_{ii}$ is its $i$-th diagonal element.

Intuitively, $\mathbf{d}_{i}^{\text{NTK}}$ is the linear model analog to
$\mathbf{d}_{i}^{\text{L}}$ and $\mathbf{d}_{i}^{\text{NTK}}$ represents the
importance that the point $\mathbf{z}_{i}=(\mathbf{x}_{i},y_{i})$ has on the
model parameters $\mathbf{w}_{\text{NTK}}$.

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
$\mathbf{d}_{i}$ should be encountered with caution during model training in
order to provide reliable recourses to the individuals who seek recourse. In
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 $\mathbf{d}_{i}$.

##  5 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\in\\{\Delta,\Phi^{(2)}\\}$ the measure we want to optimize for.
We consider the summed instability of over the data set by omitting the
subscript $\mathbf{x}$, e.g.,
$\Delta=\sum_{\mathbf{x}\in\mathcal{D}_{test}}\Delta_{\mathbf{x}}$. 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:

$\displaystyle\begin{split}\Gamma_{\alpha}:=\\{\bm{\omega}:\text{Maximally
}\lfloor\alpha\cdot n\rfloor\text{ entries of }\bm{\omega}~{}\text{are 0 and
the remainder is 1.}\\}.\end{split}$ (12)

In equation 12, the parameter $\alpha$ controls the fraction of instances that
are being removed from the training set. For a fixed fraction $\alpha$, our
problem of interest becomes:

$\displaystyle\bm{\omega}^{*}=\operatorname*{arg\,max}_{\bm{\omega}\in\Gamma_{\alpha}}m(\bm{\omega}).$
(13)

Fundamental Problems. When optimizing the above objective we face two
fundamental problems: (i) _evaluating_ $m(\bm{\omega})$ for many weight
configurations $\bm{\omega}$ can be prohibitively expensive as the objective
is defined implicitly through solutions of several non-linear optimization
problems (i.e., model fitting and finding recourses). Further, (ii) even for
an objective $m(\bm{\omega})$ which can be computed in constant or 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 equation 13 in different ways. As for the problem of computing
$m(\bm{\omega})$ in (i), we can either solve this by (a) using a closed-form
expression indicating the dependency of $m$ on $\bm{\omega}$ or (b) by using
an approximation of $m$ that is differentiable with respect to $\bm{\omega}$.
As for the optimization in (ii), once we have established the dependency of
$m$ on $\bm{\omega}$ we can either (a) use a gradient descent approach or (b)
we use a greedy method. Below we explain the individual steps required for our
algorithms.

###  5.1 Computing the Objective

In the objective $m(\bm{\omega})$, notice the dependencies
$\Delta_{\mathbf{x}}(\bm{\omega})=\Delta_{\mathbf{x}}\left(f(\mathbf{w}(\bm{\omega}),\check{\mathbf{x}})\right)$
for the recourse outcome instability, and
$\Phi^{(2)}_{\mathbf{x}}(\bm{\omega})=\Phi_{\mathbf{x}}^{(2)}\left(\bm{\delta}(\mathbf{w}(\bm{\omega}),\mathbf{x}))\right)$
for the recourse action instability. In the following, we briefly discuss how
we efficiently compute each of these functions without numerical optimization.

Model parameters from data weights $\mathbf{w}(\bm{\omega}).$ For the linear
model, an analytical solution can be obtained,
$\mathbf{w}_{\text{L}}(\bm{\omega})=\big{(}\mathbf{X}^{\top}\mathbf{\Omega}\mathbf{X}\big{)}^{-1}\mathbf{X}^{\top}\mathbf{\Omega}\mathbf{Y}$,
where $\mathbf{\Omega}=\text{diag}(\bm{\omega})$. The same goes for the NTK
model where
$\mathbf{w}_{\text{NTK}}(\bm{\omega})=\mathbf{\Omega}^{\frac{1}{2}}\big{(}\mathbf{\Omega}^{\frac{1}{2}}\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})\mathbf{\Omega}^{\frac{1}{2}}+\beta\mathbf{I}\big{)}^{-1}\mathbf{\Omega}^{\frac{1}{2}}\mathbf{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 as a
linear approximation to this implicit function. We refer to Appendix C for
additional details on this matter.

Model prediction from model parameters $f(\mathbf{w},\check{\mathbf{x}}).$
Having established the model parameters, evaluating the prediction at a given
point can be quickly done even in a differentiable manner with respect to
$\mathbf{w}$ for the models we consider in this work.

Recourse action from model parameters
$\bm{\delta}(\mathbf{w},\check{\mathbf{x}}).$ Estimating the recourse action
is more challenging as it requires solving equation 2. However, a
differentiable solution exists for linear models, where the optimal recourse
action is given by
$\bm{\delta}_{\text{L}}=\frac{s-\mathbf{w}_{\text{L}}(\bm{\omega})^{\top}\mathbf{x}}{\lambda+\lVert\mathbf{w}_{\text{L}}(\bm{\omega})\rVert_{2}^{2}}\mathbf{w}_{\text{L}}(\bm{\omega})$.
When the underlying predictor is a wide neural network we can approximate the
recourse expression of the corresponding NTK,
$\bm{\delta}_{\text{NTK}}\approx\frac{s-f_{\bm{\omega},\text{NTK}}(\mathbf{x})}{\lambda+\lVert\bar{\mathbf{w}}_{\text{NTK}}(\bar{\bm{\omega}})\rVert_{2}^{2}}\bar{\mathbf{w}}_{\text{NTK}}(\bm{\omega})$,
which stems from the first-order taylor expansion
$f_{\bm{\omega},\text{NTK}}(\mathbf{x}+\bm{\delta})\approx
f_{\bm{\omega},\text{NTK}}(\mathbf{x})+\bm{\delta}^{\top}\bar{\mathbf{w}}_{\text{NTK}}(\bm{\omega})$
with
$\bar{\mathbf{w}}_{\text{NTK}}(\bm{\omega})=\nabla_{\mathbf{x}}K(\mathbf{x},\mathbf{X})\mathbf{w}_{\text{NTK}}(\bm{\omega})$.

###  5.2 Optimizing the Objective Function

The Greedy Algorithm. We consider the model on the full data set and compute
the objective function $m(\bm{\omega})$ 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, we
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 $\mathcal{O}(\alpha n^{2})$ times.

The Gradient Descent Algorithm. Because our developed computation of
$m(\bm{\omega})$ can be made differentiable, we also propose a _gradient-based
optimization_ framework. We consider the relaxation of the problem in equation
13,

$\displaystyle\bm{\omega}^{*}=\operatorname*{arg\,max}_{\bm{\omega}\in\\{0,1\\}^{n}}~{}m(\bm{\omega})-\lVert\bm{1}-\bm{\omega}\rVert_{0},$
(14)

where the $\ell_{0}$ norm encourages to change as few data weights from $1$ 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
use a recently suggested stochastic surrogate loss for the $\ell_{0}$ 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 two algorithms.

##  6 Experimental Evaluation

We experimentally evaluate our framework in terms of its ability to find
significant recourse invalidations using the instability measures presented in
Section 3.

Data Sets. For our experiments on regression tasks we use two real-world data
sets. In addition, 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 a 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.

(a) Admission

(b) 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; see Appendix B for SGD results.

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 a gradient-based objective
to find recourses, DICE (Mothilal et al., 2020) uses a gradient-based
objective to find recourses subject to a diversity constraint, and CEM
(Dhurandhar et al., 2018) uses a generative model to 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 $\ell_{1}$ cost constraint. Further details on these algorithms are
provided in App. C.

Evaluation Measures. For the purpose of our evaluation, we use both the
recourse outcome instability measure and the recourse action instability
measure presented in Definitions 1 and 2. We evaluate the efficacy of our
framework to destabilize a large fraction of recourses using a small number of
deletion requests (up to 14). To find critical instances, we use the greedy
and the gradient-based algorithms described in Sec. 5. After having
established a set of critical points, we recompute the metrics with the
refitted models and recourses to obtain a ground truth result.

For the _recourse outcome instability_ , our metric $\Delta$ counts the number
of invalidated recourses. We use the median as the target score $s$, i.e., if
the recourse outcome flips back from a 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, we also have to recompute the recourses to evaluate $\Phi_{p}$.
We then measure the recourse instability using Definition 2 with $p=2$.
Additionally, we compare with a random baseline, which deletes points
uniformly at random from the train set. We compute these measures for all
individuals from the test set who require algorithmic recourse. To obtain
standard errors, we split the test set into 5 folds and report averaged
results over these 5 folds.

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 $k\in\\{1,\dots,14\\}$ training points are removed from
the training set of the predictive model. When the underlying model is 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 a similar trend
is present for the NTK model; however, a 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 underlying predictive model is linear or
an NTK model. For this complex objective, we use the more efficient SGD
optimization. Again, we observe that our optimization method significantly
outperforms the random baselines at finding the most influential points to 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 to 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 to 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 it 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 6 percentage points.

(a) Admission

(b) Heloc

Figure 3: Quantifying the tradeoff between recourse action instability as
measured in Definition 2 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).

##  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) a gradient-
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 evaluation 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 as GDPR. The present paper contributes towards this goal
theoretically, algorithmically, and empirically by providing evidence of
tensions between different data protection principles.

Ethics statement. Our findings raise compelling questions on 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 one 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 practitioners make sure that their recourses stay valid
under deletion requests?_ A first take might be to implement the principle of
data minimization (Biega et 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
at early stages of this work.

## References

  * Albini et al. (2022) Emanuele Albini, Jason Long, Danial Dervovic, and Daniele Magazzeni.  Counterfactual shapley additive explanations.  In _Proceedings of the Conference on Fairness, Accountability, and Transparency (FAccT)_ , 2022.
  * Angwin et al. (2016) 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.
  * Antorán et al. (2021) 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.
  * Arora et al. (2019) 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.
  * Artelt et al. (2021) André Artelt, Valerie Vaquet, Riza Velioglu, Fabian Hinder, Johannes Brinkrolf, Malte Schilling, and Barbara Hammer.  Evaluating robustness of counterfactual explanations.  _arXiv:2103.02354_ , 2021.
  * Biega & Finck (2021) Asia J. Biega and Michèle Finck.  Reviving purpose limitation and data minimisation in data-driven systems.  _Technology and Regulation_ , 2021.
  * Biega et al. (2020) 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.
  * Black et al. (2021) Emily Black, Zifan Wang, Matt Fredrikson, and Anupam Datta.  Consistent counterfactuals for deep models.  _arXiv:2110.03109_ , 2021.
  * Busuttil & Kalnishkan (2007) Steven Busuttil and Yuri Kalnishkan.  Weighted kernel regression for predicting changing dependencies.  In _European Conference on Machine Learning_ , pp. 535–542. Springer, 2007.
  * Cawley & Talbot (2004) 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–1475, 2004.
  * Chen & Xu (2021) Lin Chen and Sheng Xu.  Deep neural tangent kernel and laplace kernel have the same {rkhs}.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Cho & Saul (2009) Youngmin Cho and Lawrence Saul.  Kernel methods for deep learning.  _Advances in neural information processing systems (NeurIPS)_ , 22, 2009.
  * Cook & Weisberg (1980) R Dennis Cook and Sanford Weisberg.  Characterizations of an empirical influence function for detecting influential cases in regression.  _Technometrics_ , 22(4):495–508, 1980.
  * Csató & Opper (2002) Lehel Csató and Manfred Opper.  Sparse on-line gaussian processes.  _Neural computation_ , 14(3):641–668, 2002.
  * Dandl et al. (2020) Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl.  Multi-objective counterfactual explanations.  In _International Conference on Parallel Problem Solving from Nature_ , pp. 448–469. Springer, 2020.
  * Dhurandhar et al. (2018) Amit Dhurandhar, Pin-Yu Chen, Ronny Luss, Chun-Chen 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.
  * Dominguez-Olmedo et al. (2022) Ricardo Dominguez-Olmedo, Amir-Hossein Karimi, and Bernhard Schölkopf.  On the adversarial robustness of causal algorithmic recourse.  In _International Conference on Machine Learning (ICML)_ , 2022.
  * Doshi-Velez & Kim (2017) Finale Doshi-Velez and Been Kim.  Towards a rigorous science of interpretable machine learning.  2017\.
  * Du et al. (2019) 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.
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Found. Trends Theor. Comput. Sci._ , 9(3-4):211–407, 2014.
  * Efron (1982) Bradley Efron.  _The jackknife, the bootstrap and other resampling plans_.  SIAM, 1982.
  * Finck & Biega (2021) Michele Finck and Asia J Biega.  Reviving purpose limitation and data minimisation in data-driven systems.  _Technology and Regulation_ , 2021:44–61, 2021.
  * Ghorbani & Zou (2019) 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.
  * Ghorbani et al. (2020) 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.
  * Ginart et al. (2019) Antonio Ginart, Melody Y. Guan, Gregory Valiant, and James Zou.  Making ai forget you: Data deletion in machine learning.  In _Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada_ , 2019.
  * Giordano et al. (2019a) Ryan Giordano, Michael I. Jordan, and Tamara Broderick.  A higher-order swiss army infinitesimal jackknife.  _ArXiv_ , abs/1907.12116, 2019a.
  * Giordano et al. (2019b) Ryan Giordano, William Stephenson, Runjing Liu, Michael Jordan, and Tamara Broderick.  A swiss army infinitesimal jackknife.  In _Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2019b.
  * Golatkar et al. (2020a) 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.
  * Golatkar et al. (2020b) Aditya Golatkar, Alessandro Achille, and Stefano Soatto.  Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations.  _arXiv:2003.02960_ , 2020b.
  * Goldsteen et al. (2021) Abigail Goldsteen, Gilad Ezov, Ron Shmelkin, Micha Moffie, and Ariel Farkash.  Data minimization for gdpr compliance in machine learning models.  _AI and Ethics_ , pp. 1–15, 2021.
  * Hooker et al. (2019) Sara Hooker, Dumitru Erhan, Pieter-Jan Kindermans, and Been Kim.  A benchmark for interpretability methods in deep neural networks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Izzo et al. (2021) 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, 2021.
  * Jacot et al. (2018) Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  _Advances in neural information processing systems (NeurIPS)_ , 31, 2018.
  * Jaeckel (1972) L Jaeckel.  The infinitesimal jackknife. memorandum.  Technical report, MM 72-1215-11, Bell Lab. Murray Hill, NJ, 1972.
  * Karimi et al. (2020) 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.
  * Karp (1972) Richard M Karp.  Reducibility among combinatorial problems.  In _Complexity of computer computations_ , pp. 85–103. Springer, 1972.
  * Laugel et al. (2017) Thibault Laugel, Marie-Jeanne Lesot, Christophe Marsala, Xavier Renard, and Marcin Detyniecki.  Inverse classification for comparison-based interpretability in machine learning.  _arXiv preprint arXiv:1712.08443_ , 2017.
  * Lee et al. (2019) Jaehoon 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.
  * Mahajan et al. (2019) Divyat Mahajan, Chenhao Tan, and Amit Sharma.  Preserving causal constraints in counterfactual explanations for machine learning classifiers.  _arXiv preprint arXiv:1912.03277_ , 2019.
  * Miller Jr (1974) Rupert G Miller Jr.  An unbalanced jackknife.  _The Annals of Statistics_ , pp. 880–891, 1974.
  * Mothilal et al. (2020) 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.
  * OAG (2021) CA OAG.  Ccpa regulations: Final regulation text.  _Office of the Attorney General, California Department of Justice_ , 2021.
  * Pawelczyk et al. (2020a) 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.
  * Pawelczyk et al. (2020b) Martin Pawelczyk, Klaus Broelemann, and Gjergji. Kasneci.  On counterfactual explanations under predictive multiplicity.  In _Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)_ , pp. 809–818. PMLR, 2020b.
  * Pawelczyk et al. (2021) Martin Pawelczyk, Sascha Bielawski, Johan Van den Heuvel, Tobias Richter, and Gjergji Kasneci.  Carla: A python library to benchmark algorithmic recourse and counterfactual explanation algorithms.  In _Advances in Neural Information Processing Systems (NeurIPS) (Benchmark and Datasets Track)_ , 2021.
  * Pawelczyk et al. (2022) Martin Pawelczyk, Chirag Agarwal, Shalmali Joshi, Sohini Upadhyay, and Himabindu Lakkaraju.  Exploring counterfactual explanations through the lens ofadversarial examples: A theoretical and empirical analysis.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2022.
  * Pawelczyk et al. (2023) 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.
  * Rawal & Lakkaraju (2020) Kaivalya Rawal and Himabindu Lakkaraju.  Interpretable and interactive summaries ofactionable recourses.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 33, 2020.
  * Rawal et al. (2021) Kaivalya Rawal, Ece Kamar, and Himabindu Lakkaraju.  Algorithmic recourse in the wild: Understanding the impact of data and model shifts.  _arXiv:2012.11788_ , 2021.
  * Rong et al. (2022) 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 (ICML)_ , 2022.
  * Shanmugam et al. (2022) Divya Shanmugam, Fernando 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.
  * Slack et al. (2021) 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.
  * Spooner et al. (2021) Thomas Spooner, Danial Dervovic, Jason Long, Jon Shepard, Jiahao Chen, and Daniele Magazzeni.  Counterfactual explanations for arbitrary regression models.  _arXiv preprint arXiv:2106.15212_ , 2021.
  * Strack et al. (2014) Beata Strack, Jonathan P DeShazo, Chris Gennings, Juan L Olmo, Sebastian Ventura, Krzysztof J Cios, and John N Clore.  Impact of hba1c measurement on hospital readmission rates: analysis of 70,000 clinical database patient records.  _BioMed research international_ , 2014, 2014.
  * Tolomei et al. (2017) 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.
  * Union (2016) European Union.  Regulation (eu) 2016/679 of the european parliament and of the council.  _Official Journal of the European Union_ , 2016.
  * Upadhyay et al. (2021) Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju.  Towards robust and reliable algorithmic recourse.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 34, 2021.
  * Ustun et al. (2019) Berk Ustun, Alexander Spangher, and Y. Liu.  Actionable recourse in linear classification.  In _Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*)_ , 2019.
  * Van Looveren & Klaise (2019) Arnaud Van Looveren and Janis Klaise.  Interpretable counterfactual explanations guided by prototypes.  _arXiv preprint arXiv:1907.02584_ , 2019.
  * Villaronga et al. (2018) 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.
  * Voigt & Von dem Bussche (2017) Paul Voigt and Axel Von dem Bussche.  The eu general data protection regulation (gdpr).  _A Practical Guide, 1st Ed., Cham: Springer International Publishing_ , 10:3152676, 2017.
  * Wachter et al. (2018) 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(2), 2018.
  * Wightman (1998) Linda F Wightman.  Lsac national longitudinal bar passage study. lsac research report series.  1998\.
  * Wu et al. (2020) 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.
  * Xie et al. (2017) Bo Xie, Yingyu Liang, and Le Song.  Diverse neural network learns true target functions.  In _Artificial Intelligence and Statistics (AISTATS)_ , pp. 1216–1224. PMLR, 2017.
  * Yamada et al. (2020) 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.
  * Zhang & Zhang (2021) 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.

## Appendix

##  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(\mathbf{x})=\mathbf{w}^{\top}\mathbf{x}$
with weights given by
$\mathbf{w}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\mathbf{Y}$, an
upper bound for the output robustness by removing an instance $(\mathbf{x},y)$
from the training set is given by:

$\displaystyle\Delta_{\mathbf{x}}\leq\max_{i\in[n]}~{}\lVert\mathbf{d}_{i}\rVert_{2}\cdot\lVert\check{\mathbf{x}}_{\bm{1}}\rVert_{2},$
(15)

where
$\mathbf{d}_{i}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{x}_{i}\cdot\frac{r_{i}}{1-h_{ii}}$,
$r_{i}=y_{i}-\mathbf{w}^{\top}\mathbf{x}_{i}$ and
$h_{ii}=\mathbf{x}_{i}^{\top}(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{x}_{i}$.

###### Proof.

By Definition 1, we have:

$\displaystyle\Delta_{\mathbf{x}}$
$\displaystyle=\big{\lvert}\mathbf{w}_{\bm{1}}^{\top}\check{\mathbf{x}}_{\bm{1}}-\mathbf{w}_{-i}^{\top}\check{\mathbf{x}}_{\bm{1}}\big{\rvert}$
(16)
$\displaystyle=\big{\lvert}\big{(}\mathbf{w}_{\bm{1}}-\mathbf{w}_{-i}\big{)}^{\top}\check{\mathbf{x}}_{\bm{1}}\big{\rvert}$
$\displaystyle=\bigg{\lvert}\bigg{(}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{x}_{i}\frac{(y_{i}-\mathbf{w}^{T}\mathbf{x}_{i})}{1-h_{ii}}\bigg{)}^{\top}\check{\mathbf{x}}_{\bm{1}}\bigg{\rvert}$
$\displaystyle(\text{by Theorem \ref{theorem:leave_one_out_w}})$ (17)
$\displaystyle\leq\lVert\mathbf{d}_{i}\rVert_{2}\cdot\lVert\check{\mathbf{x}}_{\bm{1}}\rVert_{2}$
$\displaystyle(\text{by Cauchy-Schwartz})$ (18)
$\displaystyle\leq\lVert\check{\mathbf{x}}_{\bm{1}}\rVert_{2}\cdot\max_{i\in[n]}~{}\lVert\mathbf{d}_{i}\rVert_{2}\cdot,$
(19)

where
$\mathbf{d}_{i}=(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{x}_{i}\frac{(y_{i}-\mathbf{w}^{T}\mathbf{x}_{i})}{1-h_{ii}}$.
This completes our proof. ∎

######  Proposition 2 (Upper Bound on Output Robustness for NTK).

For the NTK model with
$\mathbf{w}_{\text{NTK}}=\big{(}\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})+\lambda\mathbf{I}_{n}\big{)}^{-1}\mathbf{Y}$,
an upper bound for the output robustness by removing an instance
$(\mathbf{x},y)$ from the training set is given by:

$\displaystyle\Delta_{\mathbf{x}}\leq\lVert\mathbf{K}^{\infty}(\check{\mathbf{x}}_{\bm{1}},\mathbf{X})\rVert_{2}\cdot\max_{i\in[n]}~{}\lVert\mathbf{d}_{i}\rVert_{2},$
(20)

where
$\mathbf{d}_{i}=\frac{1}{k_{ii}}\mathbf{k}_{i}\mathbf{k}_{i}^{\top}\mathbf{Y}$,
where $\mathbf{k}_{i}$ is the $i$-th column of the matrix
$\big{(}\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})+\beta\mathbf{I}_{n}\big{)}^{-1}$,
and $k_{ii}$ is its $i$-th diagonal element.

###### Proof.

By Definition 1 and the weight-update theorem by Zhang & Zhang (2021) (see
Appendix A.4) and the assumption of the over-parameterized regime, we have:

$\displaystyle\Delta_{\mathbf{x}}$
$\displaystyle=\big{\lvert}f_{\text{NTK}}(\check{\mathbf{x}}_{\bm{1}})-f^{-i}_{\text{NTK}}(\check{\mathbf{x}}_{\bm{1}})\big{\rvert}$
$\displaystyle=\big{\lvert}\big{(}\mathbf{K}^{\infty}(\check{\mathbf{x}}_{\bm{1}},\mathbf{X})\big{)}^{\top}\mathbf{w}_{\text{NTK}}-\big{(}\mathbf{K}^{\infty}(\check{\mathbf{x}}_{\bm{1}},\mathbf{X})\big{)}^{\top}\bigg{(}(\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})+\beta\mathbf{I}_{n}\big{)}^{-1}-\frac{1}{k_{ii}}\mathbf{k}_{i}\mathbf{k}_{i}^{\top}\bigg{)}\mathbf{Y}\big{\rvert}$
(21)
$\displaystyle=\big{\lvert}\big{(}\mathbf{K}^{\infty}(\check{\mathbf{x}}_{\bm{1}},\mathbf{X})\big{)}^{\top}\frac{1}{k_{ii}}\mathbf{k}_{i}\mathbf{k}_{i}^{\top}\mathbf{Y}\big{\rvert}$
(22)
$\displaystyle\leq\lVert\mathbf{d}_{i}\rVert_{2}\cdot\lVert\mathbf{K}^{\infty}(\check{\mathbf{x}}_{\bm{1}},\mathbf{X})\rVert_{2}~{}~{}~{}(\text{by
Cauchy-Schwartz})$
$\displaystyle\leq\lVert\check{\mathbf{x}}_{\bm{1}}\rVert_{2}\cdot\max_{i\in[n]}~{}\lVert\mathbf{d}_{i}\rVert_{2},$
(23)

where
$\mathbf{d}_{i}=\frac{1}{k_{ii}}\mathbf{k}_{i}\mathbf{k}_{i}^{\top}\mathbf{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(\mathbf{x})=\mathbf{w}^{\top}\mathbf{x}$
with weights given by
$\mathbf{w}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\mathbf{Y}$, an
upper bound for the input robustness in the setting $s=0,\lambda=0$ by
removing the $i$-th instance $(\mathbf{x}_{i},y_{i})$ from the training set is
given by:

$\displaystyle\Phi^{(2)}_{\mathbf{x}}\leq\lVert\mathbf{d}_{i}\rVert_{2}\frac{4\sqrt{2}\lVert\mathbf{x}\rVert_{2}}{\min(\lVert\mathbf{w}\rVert_{2},\lVert\mathbf{w}_{-i}\rVert_{2})},$
(24)

under the condition that $\mathbf{w}^{\top}\mathbf{w}_{-i}\leq 0$ (no
diametrical weight changes), where $\mathbf{w}_{-i}=\mathbf{w}-\mathbf{d}_{i}$
is the weight after removal of training instance $i$ and
$\mathbf{d}_{i}=(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{x}_{i}\frac{(y_{i}-\mathbf{w}^{\top}\mathbf{x}_{i})}{1-h_{ii}}$.

###### Proof.

For a linear scoring function
$f(\mathbf{x})=\mathbf{w}^{\prime\top}\mathbf{x}$ with given parameters
$\mathbf{w}^{\prime}$, under the squared $\ell_{2}$ norm constraint with
balance parameter $\lambda$, the optimal recourse action is given by
(Pawelczyk et al., 2022):

$\displaystyle\bm{\delta}\left(\mathbf{w}^{\prime}\right)=\frac{s-\mathbf{w}^{\prime\top}\mathbf{x}}{\lVert\mathbf{w}^{\prime}\rVert_{2}^{2}+\lambda}\cdot\mathbf{w}^{\prime}.$
(25)

Using Definition 2, we can express the total change in $\bm{\delta}$ as a path
integral over changes in $\mathbf{w}$, times the change
$\frac{\mathbf{D}\bm{\delta}}{\mathbf{D}\mathbf{w}}$ they entail:

$\displaystyle\Phi^{(2)}_{\mathbf{x}}$
$\displaystyle=\big{\lVert}\bm{\delta}_{\bm{1}}-\bm{\delta}_{\bm{\omega}}\big{\rVert}_{2}=\big{\lVert}\bm{\delta}\left(\mathbf{w}\right)-\bm{\delta}\left(\mathbf{w}_{-i}\right)\big{\rVert}_{2}$
(26)
$\displaystyle\leq\int_{0}^{1}\bigg{\lVert}\frac{\mathbf{D}\bm{\delta}}{\mathbf{D}\mathbf{w}}\left(\gamma\mathbf{w}+(1-\gamma)\mathbf{w}_{-i}\right)\bigg{\rVert}\lVert\mathbf{w}-\mathbf{w}_{-i}\rVert_{2}d\gamma,$
(27)

where $\frac{\mathbf{D}\bm{\delta}}{\mathbf{D}\mathbf{w}}$ denotes the
Jacobian, with the corresponding operator matrix norm. Defining
$\tilde{\mathbf{w}}\coloneqq\gamma\mathbf{w}+\left(1-\gamma\right)\mathbf{w}_{-i}$
and using
$\lVert\mathbf{w}-\mathbf{w}_{-i}\rVert_{2}=\lVert\mathbf{d}_{i}\rVert_{2}$,
we obtain

$\displaystyle\Phi^{(2)}_{\mathbf{x}}$
$\displaystyle\leq\lVert\mathbf{d}_{i}\rVert_{2}\int_{0}^{1}\bigg{\lVert}\frac{\mathbf{D}\bm{\delta}}{\mathbf{D}\mathbf{w}}\left(\tilde{\mathbf{w}}\right)\bigg{\rVert}_{2}d\gamma.$
(28)

Because of the form
$\bm{\delta}(\mathbf{w}^{\prime})=f(\mathbf{w}^{\prime})\mathbf{w}^{\prime}$,
where
$f(\mathbf{w}^{\prime})\coloneqq\frac{s-\mathbf{w}^{\prime\top}\mathbf{x}}{\lVert\mathbf{w}^{\prime}\rVert_{2}^{2}+\lambda}$
is a scalar function, its Jacobian has the form
$\frac{\mathbf{D}\bm{\delta}}{\mathbf{D}\mathbf{w}^{\prime}}=\mathbf{w}^{\prime}\left(\nabla
f(\mathbf{w}^{\prime})\right)^{\top}+f(\mathbf{w}^{\prime})\mathbf{I}$. We
will now derive a bound on the Jacobian’s operator norm:

$\displaystyle\bigg{\lVert}\frac{\mathbf{D}\bm{\delta}}{\mathbf{D}\mathbf{w}^{\prime}}\left(\tilde{\mathbf{w}}\right)\bigg{\rVert}_{2}$
$\displaystyle=\max_{\lVert\mathbf{a}\rVert=1}\bigg{\lVert}\frac{\mathbf{D}\bm{\delta}}{\mathbf{D}\mathbf{w}^{\prime}}\mathbf{a}\bigg{\rVert}_{2}=\max_{\lVert\mathbf{a}\rVert=1}\bigg{\lVert}\mathbf{w}^{\prime}\left(\nabla
f(\tilde{\mathbf{w}})\right)^{\top}\mathbf{a}+f(\tilde{\mathbf{w}})\mathbf{a}\bigg{\rVert}_{2}$
(29) $\displaystyle\leq\lVert\nabla
f(\tilde{\mathbf{w}})\rVert_{2}\lVert\tilde{\mathbf{w}}\rVert_{2}+\lvert
f(\tilde{\mathbf{w}})\rvert.$ (30)

Additionally, we know that for $s=0$, $\lvert
f(\mathbf{w}^{\prime})\rvert\leq\frac{\lVert\mathbf{x}\rVert_{2}\lVert\tilde{\mathbf{w}}\rVert_{2}}{\lVert\tilde{\mathbf{w}}\rVert_{2}^{2}}=\frac{\lVert\mathbf{x}\rVert_{2}}{\lVert\tilde{\mathbf{w}}\rVert_{2}}$.
The gradient is given by

$\displaystyle\lVert\nabla f(\tilde{\mathbf{w}})\rVert_{2}$
$\displaystyle=\bigg{\lVert}\frac{-(\lVert\tilde{\mathbf{w}}\rVert_{2}^{2}+\lambda)\mathbf{x}-2(s-\tilde{\mathbf{w}}^{\top}\mathbf{x})\tilde{\mathbf{w}}}{(\lVert\tilde{\mathbf{w}}\rVert_{2}^{2}+\lambda)^{2}}\bigg{\rVert}_{2}$
(31)
$\displaystyle\leq\frac{(\lVert\tilde{\mathbf{w}}\rVert_{2}^{2}+\lambda)\lVert\mathbf{x}\rVert_{2}+2(s+\lVert\tilde{\mathbf{w}}\rVert_{2}\lVert\mathbf{x}\rVert_{2})\lVert_{2}\tilde{\mathbf{w}}\rVert_{2}}{\lVert\tilde{\mathbf{w}}\rVert_{2}^{4}}$
(32)
$\displaystyle=\frac{3\lVert\mathbf{x}\rVert_{2}}{\lVert\tilde{\mathbf{w}}\rVert_{2}^{2}}$
$\displaystyle(\text{Using $\lambda\to 0$, $s=0$}).$ (33)

In summary,

$\displaystyle\bigg{\lVert}\frac{\mathbf{D}\bm{\delta}}{\mathbf{D}\mathbf{w}^{\prime}}\left(\tilde{\mathbf{w}}\right)\bigg{\rVert}_{2}\leq\frac{3\lVert\mathbf{x}\rVert_{2}}{\lVert\tilde{\mathbf{w}}\rVert_{2}^{2}}\lVert\tilde{\mathbf{w}}\rVert_{2}+\frac{\lVert\mathbf{x}\rVert_{2}}{\lVert\tilde{\mathbf{w}}\rVert_{2}}=\frac{4\lVert\mathbf{x}\rVert_{2}}{\lVert\tilde{\mathbf{w}}\rVert_{2}}.$
(34)

Because $\tilde{\mathbf{w}}$ is a line between $\mathbf{w}$ and
$\mathbf{w}_{-i}$, its norm is bounded from below by
$\lVert\tilde{\mathbf{w}}\rVert_{2}\geq\frac{1}{\sqrt{2}}\min(\lVert\mathbf{w}\rVert_{2},\lVert\mathbf{w}_{-i}\rVert_{2})\geq\frac{1}{\sqrt{2}}\left(\lVert\mathbf{w}\rVert_{2}-\lVert\mathbf{w}-\mathbf{w}_{-i}\rVert_{2}\right)=\frac{1}{\sqrt{2}}\left(\lVert\mathbf{w}\rVert_{2}-\lVert\mathbf{d}_{i}\rVert_{2}\right)$.
We can thus uniformly bound the integral and plug in the bound because of its
positivity,

$\displaystyle\Phi^{(2)}_{\mathbf{x}}$
$\displaystyle\leq\lVert\mathbf{d}_{i}\rVert_{2}\int_{0}^{1}\bigg{\lVert}\frac{\mathbf{D}\bm{\delta}}{\mathbf{D}\mathbf{w}}\left(\tilde{\mathbf{w}}\right)\bigg{\rVert}_{2}d\gamma$
(35)
$\displaystyle\leq\lVert\mathbf{d}_{i}\rVert_{2}\int_{0}^{1}\frac{4\sqrt{2}\lVert\mathbf{x}\rVert_{2}}{\min(\lVert\mathbf{w}\rVert_{2},\lVert\mathbf{w}_{-i}\rVert_{2})}d\gamma$
(36)
$\displaystyle=\lVert\mathbf{d}_{i}\rVert_{2}\frac{4\sqrt{2}\lVert\mathbf{x}\rVert_{2}}{\min(\lVert\mathbf{w}\rVert_{2},\lVert\mathbf{w}_{-i}\rVert_{2})},$
(37)

which completes the proof. ∎

###  A.3 Calculating Recourse Outcome Instability for k Deletions is NP-hard

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 $f$ 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 as follows:

$\displaystyle\max_{q_{i}\in\\{0,1\\}}\sum_{i=1}^{n}v_{i}q_{i}\text{ s.t. }$
$\displaystyle\sum_{i=1}^{n}y_{i}q_{i}\leq W,$ (38)

where the problem considers $n$ fixed items $(v_{i},y_{i})_{i=1\ldots n}$ with
a value $v_{i}$ and knapsack weight $y_{i}>0$, and $W$ is a fixed weight
budget. The optimization problem consists of choosing the items that maximize
the summed values but have a 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 choose any $k>\frac{W}{\min{y_{i}}}$ 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 we 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 is a classifier
function:

$\displaystyle
f_{\bm{\omega}}(\mathbf{x})\coloneqq\left\\{\begin{array}[]{ll}\sum_{i=1}^{n}v_{i}(1-\omega_{i}),&\sum_{i=1}^{n}y_{i}(1-\omega_{i})\leq
W\\\ 0,&\text{else}\\\ \end{array}\right..$ (41)

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 $\mathbf{q}=(\mathbf{1}-\bm{\omega})$.

###  A.4 Auxiliary Theoretical Results

We state the following classic result by Miller Jr (1974) without proof.

######  Theorem 1.

(Leave-One-Out Estimator, Miller Jr (1974)) Define $(\mathbf{x}_{i},y_{i})$ as
the point to be removed from the training set. Given the optimal weight vector
$\mathbf{w}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\mathbf{Y}$
which solves for a linear model under mean-squared-error loss, the leave-one-
out estimator is given by:

$\mathbf{w}-\mathbf{w}_{-i}=(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{x}_{i}\frac{(y_{i}-\mathbf{w}^{T}\mathbf{x}_{i})}{1-\mathbf{x}_{i}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{x}_{i}}=(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{x}_{i}\frac{(y_{i}-\mathbf{w}^{T}\mathbf{x}_{i})}{1-h_{ii}}=:\mathbf{d}_{i}.$

We restate the analtical solution for the NTK weights in case of a single
deletion from Zhang & Zhang (2021).

######  Theorem 2.

(Leave-One-Out weights for NTK models, Zhang & Zhang (2021)) Let
$\mathbf{w}_{\text{NTK}}=\big{(}\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})+\lambda\mathbf{I}_{n}\big{)}^{-1}\mathbf{Y}$
be the weight for the NTK model on the full data Kernel model, where
$\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})$ is the NTK matrix evaluated on
the training data points:
$[\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})]_{ij}=K^{\infty}(\mathbf{x}_{i},\mathbf{x}_{j})$.
Then, the NTK model that would be obtained when removing instance $i$, could
be equivalently described by

$f_{\text{NTK}}^{-i}\left(\mathbf{x}\right)=\mathbf{K}^{\infty}(\mathbf{x},\mathbf{X})^{\top}\mathbf{w}_{\text{NTK},-i}=\mathbf{K}^{\infty}(\mathbf{x},\mathbf{X})^{\top}\left(\big{(}\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})+\lambda\mathbf{I}_{n}\big{)}^{-1}-\frac{1}{q_{-ii}}{\bm{q}}_{-i}{\bm{q}}_{-i}^{\top}\right)\mathbf{Y}$

where ${\bm{q}}_{-i}$ is the $i$-th column of the matrix
${\bm{Q}}^{-1}=\big{(}\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})+\beta\mathbf{I}_{n}\big{)}^{-1}$,
and $q_{-ii}$ is its $i$-th diagonal element of this inverse.

###### Proof.

We begin by introducing some notation. Define:

$\displaystyle{\bm{Q}}$
$\displaystyle=\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})+\beta\mathbf{I}_{n}$
(42) $\displaystyle{\bm{R}}$
$\displaystyle=\mathbf{K}^{\infty}(\mathbf{X}_{-i},\mathbf{X}_{-i})+\beta\mathbf{I}_{n-1},$
(43)

then the analytical NTK model when considering the dataset with one instance
$\mathbf{x}_{i}$ removed is given by

$\displaystyle
f_{\text{NTK}}^{-i}\left(\mathbf{x}\right)=\mathbf{K}^{\infty}(\mathbf{x},\mathbf{X}_{-i})^{\top}{\bm{R}}^{-1}\mathbf{Y}_{-i},$
(44)

where $\mathbf{X}_{-i}$ denotes the data matrix with row $i$ missing and
$\mathbf{Y}_{-i}$ 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, we can assume the $i$ is the last point in the
dataset (otherwise, we just permute the data set accordingly). Therefore, we
can write the matrix ${\bm{Q}}$ in block form:

$\displaystyle{\bm{Q}}=\begin{bmatrix}{\bm{R}}&\mathbf{K}^{\infty}(\mathbf{x}_{i},{\bm{X}})\\\
\mathbf{K}^{\infty\top}(\mathbf{x}_{i},{\bm{X}})&\mathbf{K}^{\infty}(\mathbf{x}_{i},\mathbf{x}_{i})\\\
\end{bmatrix}\coloneqq\begin{bmatrix}{\bm{R}}&{\bm{q}}_{i}\\\
{\bm{q}}_{i}^{\top}&q_{ii}\\\ \end{bmatrix}$ (45)

Through the block matrix inversion formula (see for example Csató & Opper
(2002) (eqn. 52)) we can write ${\bm{Q}}$’s inverse as

$\displaystyle{\bm{Q}}^{-1}=\begin{bmatrix}{\bm{R}}^{-1}+\gamma^{-1}{\bm{R}}^{-1}{\bm{q}}_{i}{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}&\gamma^{-1}{\bm{R}}^{-1}{\bm{q}}_{i}\\\
\gamma^{-1}{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}&\gamma^{-1}\\\ \end{bmatrix}$ (46)

with $\gamma=q_{ii}-{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}{\bm{q}}_{i}$.

We denote the $i$-th (and last) column of ${\bm{Q}}^{-1}$ as
${\bm{q}}_{-i}=\begin{bmatrix}\gamma^{-1}{\bm{R}}^{-1}{\bm{q}}_{i}\\\
\gamma^{-1}\end{bmatrix}$ and the $i$-th and last diagonal element of the
inverse as $q_{-ii}=\gamma^{-1}$. 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 $\mathbf{K}^{\infty}(\mathbf{X}_{-i},\mathbf{X}_{-i})$
in the analytical solution and the weight for the point deleted will have a
value of zero, i.e.,

$\displaystyle\left(\big{(}\mathbf{K}^{\infty}(\mathbf{X},\mathbf{X})+\beta\mathbf{I}_{n}\big{)}^{-1}-\frac{1}{q_{-ii}}{\bm{q}}_{-i}{\bm{q}}_{-i}^{\top}\right)\mathbf{Y}$
$\displaystyle=\left({\bm{Q}}^{-1}-\frac{1}{q_{-ii}}{\bm{q}}_{-i}{\bm{q}}_{-i}^{\top}\right)\mathbf{Y}$
(47) $\displaystyle=\begin{bmatrix}{\bm{R}}^{-1}\mathbf{Y}_{-i}\\\
0\end{bmatrix}.$ (48)

To show this, we plug in the inversion formula ${\bm{Q}}^{-1}$ from equation
46 into equation 47 and using $q_{-ii}=\gamma^{-1}$:

$\displaystyle\left({\bm{Q}}^{-1}-\frac{1}{q_{-ii}}{\bm{q}}_{-i}{\bm{q}}_{-i}^{\top}\right)\mathbf{Y}$
(49)
$\displaystyle=\left(\begin{bmatrix}{\bm{R}}^{-1}+{\bm{R}}^{-1}{\bm{q}}_{i}{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}&\gamma^{-1}{\bm{R}}^{-1}{\bm{q}}_{i}\\\
\gamma^{-1}{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}&\gamma^{-1}\\\
\end{bmatrix}-\frac{1}{\gamma^{-1}}\begin{bmatrix}\gamma^{-1}{\bm{R}}^{-1}{\bm{q}}_{i}\\\
\gamma^{-1}\end{bmatrix}\begin{bmatrix}\gamma^{-1}{\bm{R}}^{-1}{\bm{q}}_{i}\\\
\gamma^{-1}\end{bmatrix}^{\top}\right)\begin{bmatrix}\mathbf{Y}_{-i}\\\
Y_{i}\end{bmatrix}$ (50)
$\displaystyle=\left(\begin{bmatrix}{\bm{R}}^{-1}+\gamma^{-1}{\bm{R}}^{-1}{\bm{q}}_{i}{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}&\gamma^{-1}{\bm{R}}^{-1}{\bm{q}}_{i}\\\
\gamma^{-1}{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}&\gamma^{-1}\\\
\end{bmatrix}-{\gamma}\begin{bmatrix}\gamma^{-2}{\bm{R}}^{-1}{\bm{q}}_{i}{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}&\gamma^{-2}{\bm{R}}^{-1}{\bm{q}}_{i}\\\
\gamma^{-2}{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}&\gamma^{-2}\\\
\end{bmatrix}\right)\begin{bmatrix}\mathbf{Y}_{-i}\\\ Y_{i}\end{bmatrix}$ (51)
$\displaystyle=\begin{bmatrix}{\bm{R}}^{-1}+\gamma^{-1}{\bm{R}}^{-1}{\bm{q}}_{i}{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}-\gamma^{-1}{\bm{R}}^{-1}{\bm{q}}_{i}{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}&\gamma^{-1}{\bm{R}}^{-1}{\bm{q}}_{i}-\gamma^{-1}{\bm{R}}^{-1}{\bm{q}}_{i}\\\
\gamma^{-1}{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}-\gamma^{-1}{\bm{q}}_{i}^{\top}{\bm{R}}^{-1}&\gamma^{-1}-\gamma^{-1}\\\
\end{bmatrix}\begin{bmatrix}\mathbf{Y}_{-i}\\\ Y_{i}\end{bmatrix}$ (52)
$\displaystyle=\begin{bmatrix}{\bm{R}}^{-1}&\mathbf{0}\\\
\mathbf{0}^{\top}&0\\\ \end{bmatrix}\begin{bmatrix}\mathbf{Y}_{-i}\\\
Y_{i}\end{bmatrix}=\begin{bmatrix}{\bm{R}}^{-1}\mathbf{Y}_{-i}\\\
0\end{bmatrix}.$ (53)

Therefore, we have equivalence between equation 44 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 ReLU network. First, see the paper
by Jacot et al. Jacot et al. (2018) for the original derivation of the neural
tangent kernel.

A closed-form solution for two-layer ReLU networks. From (Zhang & Zhang, 2021;
Du et al., 2019, Assumption 3.1) we obtain the definition of the Kernel matrix
$\mathbf{K}^{\infty}$ (termed Gram matrix in the paper Du et al. (2019)) for
ReLU networks:

$\displaystyle\mathbf{K}^{\infty}_{ij}=\mathbf{K}^{\infty}(\mathbf{x}_{i},\mathbf{x}_{j})$
$\displaystyle=\mathbb{E}_{\mathbf{w}\sim\mathcal{N}\left(0,\mathbf{I}\right)}\left[\mathbf{x}_{i}^{\top}\mathbf{x}_{j}\mathbb{I}\left\\{\mathbf{w}^{\top}\mathbf{x}_{i}\geq
0,\mathbf{w}^{\top}\mathbf{x}_{j}\geq 0\right\\}\right]$
$\displaystyle=\mathbf{x}_{i}^{\top}\mathbf{x}_{j}\mathbb{E}_{\mathbf{w}\sim\mathcal{N}\left(0,\mathbf{I}\right)}\left[\mathbb{I}\left\\{\mathbf{w}^{\top}\mathbf{x}_{i}\geq
0,\mathbf{w}^{\top}\mathbf{x}_{j}\geq 0\right\\}\right]$
$\displaystyle=\mathbf{x}_{i}^{\top}\mathbf{x}_{j}\frac{\pi-\text{arcos}\left(\frac{\mathbf{x}_{i}^{\top}\mathbf{x}_{j}}{\lVert\mathbf{x}_{i}\rVert\lVert\mathbf{x}_{j}\rVert}\right)}{2\pi}.$

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.

##  Appendix 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 labels. On the Admission data set (in the
classification setting), a counterfactual is 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 a
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 a
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
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 an 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 ANN model, we use the infinitesimal jackknife approximation
to calculate the probitively expensive 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 a 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 as follows: when the $\ell_{0}$ regularization
strength (i.e., $\eta$) is not strong enough, then the importance weights for
the $k$-th removal with $k>5$ 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 $\ell_{0}$
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 15 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 the results of this strategy for the SCFE
recourse method. We see that this strategy increases the robustness of 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.

(a) Admission

(b) Heloc

(c) Compas

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

(a) Admission (Greedy)

(b) Admission (SGD)

(c) Heloc (Greedy)

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

(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 and reran the removal algorithm on the remaining
training set. Results were obtained by Greedy optimization. The dotted lines
indicate the random baselines. (a) Admission (Greedy) Figure 7: Measuring the
tradeoff between recourse outcome instability and the number of deletion
requests for the Admission data set for a neural network regression model. We
used the critical points identified for the NTK model to invalidate the
recourses identified by a wide 2-layer ReLU network with 10000 hidden nodes.
Results were obtained by Greedy optimization. The dotted lines indicate the
random baselines.

##  Appendix C Implementation Details

###  C.1 Details on Model Training

We train the classification models using the hyperparameters given in Table 1.
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 17 and 22, we
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, we slightly adjust Algorithm 22 to
optimize the right metric from Definition 2.

###  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 or second counterfactual
to be the counterfactual assigned to the given input. Across all recourse
methods the success rates lie above 95%, i.e., 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 $\lambda\to 0$. Note that the default
implementations use early stopping once a feasible recourse has been
identified.

Model | Parameters
---|---
Linear Regression | OLS, no hyperparameters.
NTK Regression |  $\beta=2$ (Admission), $\beta=5$ (other data sets)
Logistic Regression | L2-Regularization with $C=1.0$
Kernel-LSSVM | Gaussian Kernel with $\gamma=1.0$ (see Cawley & Talbot (2004))
ANN | 2-Layer, 30 Hidden units, Sigmoid, $\alpha=10$ (L2-Regularization)
Table 1: Model hyperparameters used in this work

###  C.3 Details on the $\ell_{0}$ Regularizer

Since an $\ell_{0}$ regularizer is computationally intractable for high-
dimensional optimization problems, we have to resort to approximations. One
such approximation approach was recently suggested by Yamada et al. (2020).
The underlying idea consists of converting the combinatorial search problem to
a continuous search problem over distribution parameters. To this end, recall
our optimization problem from the main text:

$\displaystyle\bm{\omega}^{*}=\operatorname*{arg\,max}_{\bm{\omega}\in\\{0,1\\}^{n}}~{}m(\bm{\omega})-\eta\cdot\lVert\bm{1}-\bm{\omega}\rVert_{0}.$
(54)

We will now introduce Bernoulli random variables $Z_{i}\in\\{0,1\\}$ with
corresponding parameters $\pi_{i}$ to model the individual $\omega_{i}$.
Instead of optimizing the objective above with respect to $\bm{\omega}$ we
will optimize with respect to distribution parameters $\bm{\pi}$:

$\displaystyle\bm{\pi}^{*}=\operatorname*{arg\,max}_{\bm{\pi}}~{}m(\mathbf{Z}(\bm{\pi}))-\eta\cdot\lVert\bm{1}-\mathbf{Z}(\bm{\pi})\rVert_{0}.$
(55)

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:

$\displaystyle\tilde{Z}_{i}=\max(0,\min(1,\mu_{i}+\epsilon_{i})),$ (56)

where $\epsilon_{i}=\mathcal{N}(0,\sigma^{2})$, resulting in the following
optimization problem:

$\displaystyle\bm{\mu}^{*}=\operatorname*{arg\,max}_{\bm{\mu}}~{}m(\tilde{\mathbf{Z}}(\bm{\mu}))-\eta\cdot\lVert\bm{1}-\tilde{\mathbf{Z}}(\bm{\mu})\rVert_{0}.$
(57)

At inference time, the optimal weights are then given by
$\tilde{Z}_{i}^{*}=\max(0,\min(1,\mu_{i}^{*}))~{}\forall i\in[n]$. To obtain
discrete weights, we take the argmax over each individual $\tilde{Z}_{i}$.

###  C.4 Details on the Jackknife Approximation

Required: Model: $f_{\mathbf{w}(\bm{1})}$; Matrix of Recourses:
$\check{\mathbf{X}}_{\bm{1}}\in\mathbb{R}^{q\times d}$; $d$: input dimension;
$q$ number of recourse points on test set; $n$: # train points; $M$: max #
deleted train points; $s$: invalidation target

$\bm{\omega}^{(0)}=\bm{1}_{n}$ $\triangleright$ All training instances present

for $m=1:M$ do

$\bm{\omega}^{(m)}\leftarrow\bm{\omega}^{(m-1)}$

$\tilde{\textbf{Y}}=\mathbf{0}_{n\times q}$ $\triangleright$ Recourse outcomes

$\bm{J}=\mathbf{0}_{n\times q}$ $\triangleright$ Invalidations present

$S^{(m)}\leftarrow\left\\{i~{}\middle|~{}\bm{\omega}_{i}^{(m)}\neq 0\right\\}$
$\triangleright$ Set of train instances present at iteration $m$

for $i\in S^{(m)}$ do

$\mathbf{w}^{(i)}_{\text{new}}=\texttt{update\\_w}(\bm{\omega}^{(m)}_{-i})$
$\triangleright$ $\bm{\omega}^{(m)}_{-i}$ has additionally set weight $i$ to
0.

$\triangleright$ Use analytical or IJ solution for $\mathbf{w}(\bm{\omega})$

$\tilde{\textbf{Y}}[i,:]=f_{\mathbf{w}^{(i)}_{\text{new}}}(\check{\mathbf{X}}_{\bm{1}})$
$\triangleright$ New recourse outcomes

$\bm{J}[i,:]=\mathbb{I}(\tilde{\textbf{Y}}[i,:]<s)$ $\triangleright$
Invalidation present

end for

index $\leftarrow{}$ $\operatorname*{arg\,max}_{i\in
S^{(m)}}\lVert\mathbf{J}[i,:]\rVert_{1}$ $\triangleright$ Find point that
leads to highest invalidation

$\bm{\omega}^{(m)}[\text{index}]=0$ $\triangleright$ Remove training point

end for

return: $\bm{\omega}^{(M)}$ $\triangleright$ data weights indicating $M$
removals

Algorithm 1 Greedy recourse outcome invalidation

When the model parameters $\mathbf{w}$ are a function of the data weights by
solving equation 1 we can approximate $\mathbf{w}(\bm{\omega})$ using the
infinitesimal Jackknife (IJ) without having to optimize equation 1 repeatedly
(Jaeckel, 1972; Efron, 1982; Giordano et al., 2019b; a):

$\displaystyle\mathbf{w}_{\text{IJ}}(\bm{\omega})=\mathbf{w}_{\bm{1}}-\mathbf{H}_{\bm{1}}^{-1}\mathbf{G}_{\bm{\omega}-\bm{1}},$
(58)

where $\mathbf{G}$ and $\mathbf{H}_{\bm{1}}$ are the Jacobian and the Hessian
matrices of the loss function with respect to the data weights evaluated at
the optimal model parameters $\mathbf{w}$, i.e.,
$\mathbf{G}_{\bm{\omega}-\bm{1}}=\frac{1}{n}\sum_{i=1}^{n}(\omega_{i}-1)\cdot\frac{\partial\ell(f_{\mathbf{w}}(\mathbf{x}_{i}),y_{i})}{\partial\mathbf{w}}$
and
$\mathbf{H}_{\bm{1}}=\frac{1}{n}\sum_{i=1}^{n}\frac{\partial^{2}\ell(f_{\mathbf{w}}(\mathbf{x}_{i}),y_{i})}{\partial\mathbf{w}\partial\mathbf{w}^{\top}}$.
Note that this technique computes the Hessian matrix $\mathbf{H}_{\bm{1}}$
only once. Using this Jackknife approximation, the Jacobian term
$\mathbf{G}_{\bm{\omega}-1}$ becomes an explicit function of the data weights
which makes the Jackknife approximation amenable to optimization.

Required: Model: $f_{\mathbf{w}(\bm{1})}$; Matrix of Recourses:
$\check{\mathbf{X}}_{\bm{1}}\in\mathbb{R}^{q\times d}$; $d$: input dimension;
$q$ number of recourse points on test set; $n$: # train points; $M$: max #
deleted train points; $s$: invalidation target

$\bm{\mu}^{(1)}=\bm{1}_{n}$ $\triangleright$ Mu are soft data weights that are
opimized.

for $m=1:\text{Step}$ do $\triangleright$ Perform $Step$ number of updates.

$\delta{-}\text{loss}{=}0.0$

for $k=1:K$ do $\triangleright$ Use $K$ Monte-Carlo Samples for the
approximation

Sample
$\bm{\epsilon}_{k}^{(m)}\sim\mathcal{N}\left(0,\sigma^{2}\mathbf{I}_{n}\right)$

$\bm{\omega}_{k}^{(m)}=\max\left(0,\min\left(1,\bm{\mu}^{(m)}+\bm{\epsilon}_{k}^{(m)}\right)\right)$
$\triangleright$ Sample (soft) data weights as in Yamada et al. (2020)

$\mathbf{w}^{(m)}_{k,\text{new}}=\texttt{update\\_w}(\bm{\omega}^{(m)}_{k})$
$\triangleright$ Compute model weights from data weights either analytically
or with IJ

$l^{(m)}_{k}=\text{sigmoid}\left(f_{\mathbf{w}^{(m)}_{k,\text{new}}}(\check{\mathbf{X}}_{\bm{1}})-s\right)$
$\triangleright$ Predict with new weights and compute soft invalidation.

$\delta{-}\text{loss}=\delta{-}\text{loss}+\lVert l^{(m)}_{k}\rVert_{1}$
$\triangleright$ Add up soft inval. loss

end for

$r^{(m)}=\sum_{i=1}^{n}\Phi\left(\frac{1-(\bm{\mu}^{(m)})_{i}}{\sigma}\right)$
$\triangleright$ Sparsity Regularizer from Yamada et al. (2020)

$\bm{\mu}^{(m+1)}=\bm{\mu}^{(m)}+\gamma\nabla_{\bm{\mu}^{(m)}}\left(\frac{\delta{-}\text{loss}}{D}+\lambda
r^{(m)}\right)$ $\triangleright$ Grad. Descent with lr. $\gamma$

end for

removed_ind = argsort$(\bm{\mu}^{(\text{Step}+1)})$ $\triangleright$ Sort
indices ascendingly

$j=0$

$\bm{\omega}=\bm{1}_{n}$

while $j<M$ do $\triangleright$ Binarize and fulfil max number M

$\bm{\omega}$[removed_ind[j]]= 0

$j=j+1$

end while

return: $\bm{\omega}$ $\triangleright$ data weights indicating $M$ removals

Algorithm 2 SGD recourse outcome invalidation