Simple Steps to Success: Axiomatics of Distance-Based Algorithmic Recourse

Jenny Hamer, Jake Valladares, Vignesh Viswanathan, Yair ZickarXiv 2023 · arXiv · OpenReview

Abstract

We propose a novel data-driven framework for algorithmic recourse that offers users interventions to change their predicted outcome. Existing approaches to compute recourse find a set of points that satisfy some desiderata—e.g., an intervention in the underlying causal graph, or minimizing a cost function. Satisfying these criteria, however, requires extensive knowledge of the underlying model structure, often an unrealistic amount of information in several domains. We propose a data-driven, computationally efficient approach to computing algorithmic recourse. We do so by suggesting directions in the data manifold that users can take to change their predicted outcome. We present Stepwise Explainable Paths (StEP), an axiomatically justified framework to compute direction-based algorithmic recourse. We offer a thorough empirical and theoretical investigation of StEP. StEP offers provable privacy and robustness guarantees, and outperforms the state-of-the-art on several established recourse desiderata.

Introduction

When an AI system makes a consequential decision—such as denying a mortgage or a graduate school application—the user naturally asks: "What can I do to change this?" This is the core challenge of algorithmic recourse.

Existing approaches often face significant practical hurdles. Some require "white-box" access to the model or a perfect "causal graph" of the environment, which is rarely available. Others are model-agnostic but frequently suggest "off-manifold" actions—recommendations that are mathematically valid within the model but practically nonsensical (e.g., suggesting a user decrease their credit score to obtain a loan due to training data artifacts). Furthermore, most methods provide a single "destination" point rather than a path, leaving users without guidance if they cannot achieve the full change in one step.

The StEP Framework

The researchers introduce StEP (Stepwise Explainable Paths), a model-agnostic framework that provides users with incremental, data-driven directions to change an algorithmic decision. StEP shifts the focus from finding a single destination point to identifying optimal directions.

Overview of the StEP framework: (a) the initial dataset with a Point of Interest (PoI), (b) generated recourse directions toward clusters of success, and (c) the resulting iterative stakeholder path to acceptance.

The StEP methodology follows a structured process:

  1. Clustering: StEP partitions the positively classified points in the training data into $k$ clusters, ensuring the identification of multiple distinct "paths to success."
  2. Direction Generation: For a rejected user (the Point of Interest), StEP calculates a direction vector toward each cluster. This vector is a weighted sum of the differences between the user’s current state and the "successful" points in that cluster.
  3. The "Volcano" Function: Weighting is managed by a function that prioritizes successful points closer to the user, ensuring the directions are grounded in local data density.
  4. Iterative Recourse: Instead of a one-shot recommendation, StEP is iterative. A user takes a step in a suggested direction, the model re-evaluates them, and if they remain rejected, StEP provides updated directions based on their new state.

Crucially, the authors prove that this specific method of calculating directions is the only approach that satisfies a set of six logical axioms (such as Shift Invariance and Positive Classification Monotonicity), providing a rigorous theoretical foundation.

Empirical Evaluation

StEP was evaluated using three standard benchmarks: Credit Card Default, Give Me Some Credit, and UCI Adult. It was compared against popular baselines including DiCE (optimization-based), FACE (graph-based), and C-CHVAE (generative model-based) across various models like Logistic Regression, Random Forests, and Deep Neural Networks.

Key Results

  • The "Goldilocks" Balance: StEP consistently found a sweet spot between diversity and effort. While DiCE produced diverse suggestions, they often required high user effort. FACE produced close suggestions but frequently failed to change the model's outcome. StEP maintained high success rates while keeping the "travel distance" low.
  • Efficiency: StEP is computationally lightweight, with complexity that scales linearly relative to the dataset size, unlike many optimization-based alternatives.
  • Robustness to User Interference: The framework remains effective even when users do not follow directions perfectly. In some cases, this stochasticity even helped users escape local minima in the decision boundary.

Discussion and Key Insights

StEP offers several advantages beyond simple recourse. By providing directions rather than fixed points, it grants users more agency; if a user manages to improve a different feature than the one suggested, StEP simply recalculates from the new position. Furthermore, by anchoring directions to real data clusters, it naturally avoids "impossible" feature combinations.

From a security perspective, StEP offers Privacy by Design. Because it relies on aggregate data (weighted sums) rather than individual points, it can be made differentially private by adding controlled Gaussian noise—a vital feature for financial or medical applications.

Limitations and Future Work

While robust, StEP's performance depends on the chosen distance metrics, particularly for categorical variables. Future work will investigate Group Fairness to ensure that recourse paths are equally accessible across different protected groups and explore handling more complex, "holey" data manifolds where simple directional vectors might face challenges.

Summary updated

Abstract

We propose a novel data-driven framework for algorithmic recourse that offers users interventions to change their predicted outcome. Existing approaches to compute recourse find a set of points that satisfy some desiderata -- e.g. an intervention in the underlying causal graph, or minimizing a cost function. Satisfying these criteria, however, requires extensive knowledge of the underlying model structure, often an unrealistic amount of information in several domains. We propose a data-driven, computationally efficient approach to computing algorithmic recourse. We do so by suggesting directions in the data manifold that users can take to change their predicted outcome. We present Stepwise Explainable Paths (StEP), an axiomatically justified framework to compute direction-based algorithmic recourse. We offer a thorough empirical and theoretical investigation of StEP. StEP offers provable privacy and robustness guarantees, and outperforms the state-of-the-art on several established recourse desiderata.
BibTeX
@misc{hamer2023simple,
  author = {Jenny Hamer and Jake Valladares and Vignesh Viswanathan and Yair Zick},
  title = {{Simple Steps to Success: Axiomatics of Distance-Based Algorithmic Recourse}},
  year = {2023},
  eprint = {2306.15557},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.15557},
}
Figure