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

arXiv: https://arxiv.org/abs/2208.14137 · HTML: https://mlsanity.com/paper/2208.14137/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 70 references that are in the map.
- First posted on arXiv 30 Aug 2022.

## Builds on (most cited first, 30 of 47)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks](https://mlsanity.com/paper/1911.04933/) (2019)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [A Benchmark for Interpretability Methods in Deep Neural Networks](https://mlsanity.com/paper/1806.10758/) (2018)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018)
- [Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives](https://mlsanity.com/paper/1802.07623/) (2018)
- [Approximate Data Deletion from Machine Learning Models](https://mlsanity.com/paper/2002.10077/) (2020)
- [Interpretable Counterfactual Explanations Guided by Prototypes](https://mlsanity.com/paper/1907.02584/) (2019)
- [Model-Agnostic Counterfactual Explanations for Consequential Decisions](https://mlsanity.com/paper/1905.11190/) (2019)
- [Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from Input-Output Observations](https://mlsanity.com/paper/2003.02960/) (2020)
- [Multi-Objective Counterfactual Explanations](https://mlsanity.com/paper/2004.11165/) (2020)
- [DeltaGrad: Rapid retraining of machine learning models](https://mlsanity.com/paper/2006.14755/) (2020)
- [Learning Model-Agnostic Counterfactual Explanations for Tabular Data](https://mlsanity.com/paper/1910.09398/) (2019)
- [Preserving Causal Constraints in Counterfactual Explanations for Machine Learning Classifiers](https://mlsanity.com/paper/1912.03277/) (2019)
- [Counterfactual Explanations Can Be Manipulated](https://mlsanity.com/paper/2106.02666/) (2021)
- [Towards Robust and Reliable Algorithmic Recourse](https://mlsanity.com/paper/2102.13620/) (2021)
- [A Consistent and Efficient Evaluation Strategy for Attribution Methods](https://mlsanity.com/paper/2202.00449/) (2022)
- [Getting a CLUE: A Method for Explaining Uncertainty Estimates](https://mlsanity.com/paper/2006.06848/) (2020)
- [CARLA: A Python Library to Benchmark Algorithmic Recourse and Counterfactual Explanation Algorithms](https://mlsanity.com/paper/2108.00783/) (2021)
- [A Distributional Framework for Data Valuation](https://mlsanity.com/paper/2002.12334/) (2020)
- [Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking](https://mlsanity.com/paper/1706.06691/) (2017)
- [On Counterfactual Explanations under Predictive Multiplicity](https://mlsanity.com/paper/2006.13132/) (2020)
- [Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS](https://mlsanity.com/paper/2009.10683/) (2020)

## Built on by (most cited first, 20 of 20)

- [In-Context Unlearning: Language Models as Few Shot Unlearners](https://mlsanity.com/paper/2310.07579/) (2023)
- [Machine Unlearning Fails to Remove Data Poisoning Attacks](https://mlsanity.com/paper/2406.17216/) (2024)
- [On the Privacy Risks of Algorithmic Recourse](https://mlsanity.com/paper/2211.05427/) (2022)
- [Robust Counterfactual Explanations in Machine Learning: A Survey](https://mlsanity.com/paper/2402.01928/) (2024)
- [MultiDelete for Multimodal Machine Unlearning](https://mlsanity.com/paper/2311.12047/) (2023)
- [MU-Bench: A Multitask Multimodal Benchmark for Machine Unlearning](https://mlsanity.com/paper/2406.14796/) (2024)
- [Achieving Diversity in Counterfactual Explanations: a Review and Discussion](https://mlsanity.com/paper/2305.05840/) (2023)
- [Towards Bridging the Gaps between the Right to Explanation and the Right to be Forgotten](https://mlsanity.com/paper/2302.04288/) (2023)
- [Time Can Invalidate Algorithmic Recourse](https://mlsanity.com/paper/2410.08007/) (2024)
- [Interval Abstractions for Robust Counterfactual Explanations](https://mlsanity.com/paper/2404.13736/) (2024)
- [Learning-Augmented Robust Algorithmic Recourse](https://mlsanity.com/paper/2410.01580/) (2024)
- [Engineering the Law-Machine Learning Translation Problem: Developing Legally Aligned Models](https://mlsanity.com/paper/2504.16969/) (2025)
- [Reinforcement Learning for Durable Algorithmic Recourse](https://mlsanity.com/paper/2509.22102/) (2025)
- [Towards Non-Adversarial Algorithmic Recourse](https://mlsanity.com/paper/2403.10330/) (2024)
- [I Prefer not to Say: Protecting User Consent in Models with Optional Personal Data](https://mlsanity.com/paper/2210.13954/) (2022)
- [Adapting to Change: Robust Counterfactual Explanations in Dynamic Data Landscapes](https://mlsanity.com/paper/2308.02353/) (2023)
- [Why am I Still Seeing This: Measuring the Effectiveness Of Ad Controls and Explanations in AI-Mediated Ad Targeting Systems](https://mlsanity.com/paper/2408.11910/) (2024)
- [Efficiently Verifiable Proofs of Data Attribution](https://mlsanity.com/paper/2508.10866/) (2025)
- [On the Trade-offs between Adversarial Robustness and Actionable Explanations](https://mlsanity.com/paper/2309.16452/) (2023)
- [Beyond Uniform Deletion: A Data Value-Weighted Framework for Certified Machine Unlearning](https://mlsanity.com/paper/2511.06794/) (2025)

## Abstract (arXiv)

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.