# Coverage-Validity-Aware Algorithmic Recourse

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2023.

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

- [Robust Counterfactual Explanations in Machine Learning: A Survey](https://mlsanity.com/paper/2402.01928/) (2024)
- [Counterfactual Explanations for Model Ensembles Using Entropic Risk Measures](https://mlsanity.com/paper/2503.07934/) (2025)
- [A Geometric Unification of Distributionally Robust Covariance Estimators: Shrinking the Spectrum by Inflating the Ambiguity Set](https://mlsanity.com/paper/2405.20124/) (2024)
- [RecourseBench: A Modular Framework for Reproducible Algorithmic Recourse Evaluation](https://mlsanity.com/paper/2606.16113/) (2026)

## Abstract (arXiv)

Algorithmic recourse emerges as a prominent technique to promote the explainability, transparency, and ethics of machine learning models. Existing algorithmic recourse approaches often assume an invariant predictive model; however, the predictive model is usually updated upon the arrival of new data. Thus, a recourse that is valid respective to the present model may become invalid for the future model. To resolve this issue, we propose a novel framework to generate a model-agnostic recourse that exhibits robustness to model shifts. Our framework first builds a coverage-validity-aware linear surrogate of the nonlinear (black-box) model; then, the recourse is generated with respect to the linear surrogate. We establish a theoretical connection between our coverage-validity-aware linear surrogate and the minimax probability machines (MPM). We then prove that by prescribing different covariance robustness, the proposed framework recovers popular regularizations for MPM, including the ℓ2-regularization and class-reweighting. Furthermore, we show that our surrogate pushes the approximate hyperplane intuitively, facilitating not only robust but also interpretable recourses. The numerical results demonstrate the usefulness and robustness of our framework.