On the Adversarial Robustness of Causal Algorithmic Recourse

Ricardo Dominguez-Olmedo, Amir-Hossein Karimi, Bernhard Schölkopf

Introduction

Standard algorithmic recourse provides individuals with actionable steps to reverse unfavorable AI decisions (e.g., "increase savings by $5,000 to get a loan"). However, these recommendations are often "fragile." A minor, unrelated change in circumstances—like a slight drop in working hours—can invalidate the advice because standard methods typically find the minimum-cost change, placing the individual exactly on the decision boundary. This paper addresses this instability by introducing a framework for adversarially robust causal recourse.

Adversarially Robust Recourse

The authors shift from standard optimization to a robust minimax formulation. Instead of targeting a single point, they define a "counterfactual uncertainty set"—a neighborhood of plausible individuals around the person seeking recourse.

Conceptual illustration of robust vs. non-robust recourse actions.

Key to this approach is the use of Structural Causal Models (SCMs) to define these neighborhoods. Unlike simple distance-based balls, causal uncertainty sets account for how features co-vary (e.g., income affecting savings). For linear models, this robust recourse is equivalent to finding standard recourse on a classifier with a shifted acceptance threshold. For neural networks, a gradient-based iterative algorithm is used to satisfy the most "difficult" individual in the uncertainty set.

The Actionable Locally Linear Regularizer (ALLR)

Beyond generating robust paths, the authors propose that models should be trained to be "recourse-friendly." They introduce the Actionable Locally Linear Regularizer (ALLR), which encourages models to be locally linear and rely on actionable features (e.g., savings) rather than unactionable ones (e.g., age). This reduces the burden on the user to find stable recourse.

Empirical Results

The framework was evaluated on datasets including COMPAS, Adult, and South German Credit. A key finding is that the "cheapest" recourse is mathematically proven to be the most brittle.

Empirical fragility of standard recourse across various datasets.

Standard recourse methods were found to be invalidated by perturbations as small as $10^{-6}$. In contrast, the proposed robust generation method maintained validity under significant uncertainty ($\epsilon = 0.1$). Furthermore, training with ALLR significantly increased the availability of robust recourse—up to 100% in some cases—with minimal impact on predictive accuracy (usually less than 3%).

Conclusion

This work highlights the inherent fragility of minimum-cost algorithmic recourse and provides a causal, robust alternative. By combining robust optimization with causal modeling and model regularization, AI systems can provide more reliable and stable paths for individuals to improve their outcomes.

Summary updated

BibTeX
@inproceedings{dominguezolmedo2022adversarial,
  author = {Ricardo Dominguez-Olmedo and Amir-Hossein Karimi and Bernhard Schölkopf},
  title = {{On the Adversarial Robustness of Causal Algorithmic Recourse}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=H3VoYEDYN-X},
}
Figure