  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.
