PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithmic Recourse in the Wild: Understanding the Impact of Data and Model Shifts

Kaivalya Rawal, Ece Kamar, Himabindu Lakkaraju

arXiv:2012.11788v3cs.LGcs.AI

TL;DR

Recourse algorithms are commonly considered without accounting for changes to the underlying model, although model updates and distribution shifts occur in practice. This paper analyzes recourse under such shifts theoretically and experimentally. It finds a cost–invalidation tradeoff and that updates across several shift types can potentially invalidate recourses generated by state-of-the-art algorithms.

  • Problem

    Prior research has not systematically assessed whether algorithmic recourses remain reliable when models are updated because of data distribution shifts.

    Source: §1 · pp. 1–2

  • Method

    The paper theoretically analyzes recourse invalidation under model updates and experimentally studies synthetic and real-world datasets with several distribution shifts.

    Source: §1 · p. 2

  • Results

    Across temporal, geospatial, and data-correction shifts, model updates can potentially invalidate recourses from state-of-the-art algorithms, including causal recourse algorithms.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The findings expose problems with current recourse generation and emphasize the need to rethink its design and development.

    Source: §1 · p. 2

    The theoretical analysis assumes model perturbations have zero expected value and that q1 and q2 are drawn from the same unknown distribution.

    Source: §3.3 · p. 4

Abstract

from arXiv · show

As predictive models are increasingly being deployed to make a variety of consequential decisions, there is a growing emphasis on designing algorithms that can provide recourse to affected individuals. Existing recourse algorithms function under the assumption that the underlying predictive model does not change. However, models are regularly updated in practice for several reasons including data distribution shifts. In this work, we make the first attempt at understanding how model updates resulting from data distribution shifts impact the algorithmic recourses generated by state-of-the-art algorithms. We carry out a rigorous theoretical and empirical analysis to address the above question. Our theoretical results establish a lower bound on the probability of recourse invalidation due to model shifts, and show the existence of a tradeoff between this invalidation probability and typical notions of "cost" minimized by modern recourse generation algorithms. We experiment with multiple synthetic and real world datasets, capturing different kinds of distribution shifts including temporal shifts, geospatial shifts, and shifts due to data correction. These experiments demonstrate that model updation due to all the aforementioned distribution shifts can potentially invalidate recourses generated by state-of-the-art algorithms. Our findings thus not only expose previously unknown flaws in the current recourse generation paradigm, but also pave the way for fundamentally rethinking the design and development of recourse generation algorithms.

1 Introduction

The introduction argues that reliable recourse must remain valid when decision-making models are updated, a problem that prior work has not systematically evaluated under data distribution shifts. The paper combines theoretical analysis with experiments to show a cost–invalidation tradeoff and potential invalidation across several shift types.

1 Introduction

  • Recourse tools aim to explain negative decisions and identify changes that could produce a desired prediction.Prior approaches include local counterfactual explanations for affected individuals.Source: §1 · p. 1
  • Invalid recourses can harm affected individuals and undermine the credibility of the decision-making entity that issued them.The concern is whether an entity will honor a recourse when a person reapplies after implementing its recommendations.Source: §1 · pp. 1–2
  • Prior research largely leaves unresolved whether recourses remain robust when models are updated because of distribution shifts.The introduction notes that other work on recourse spuriousness and causal approaches did not explicitly address distribution shifts.Source: §1 · p. 2
  • The paper proves a tradeoff between recourse cost and invalidation risk, and establishes a non-zero lower bound on invalidation probability under distribution shifts.These theoretical findings motivate experiments on real-world datasets.Source: §1 · p. 2
  • Model updates under data distribution shifts can potentially invalidate recourses from state-of-the-art algorithms across temporal, geospatial, and data-correction shifts.The experiments span synthetic and real-world datasets in criminal justice, education, and credit scoring, and include causal recourse algorithms.Source: §1 · p. 2

2 Related Work

Related work studies explainability, distribution shifts, and recourse as largely separate areas. The paper positions its focus on recourse robustness to model updates within that gap and reviews common recourse categories and approaches.

2 Related Work

  • Prior work on distribution shifts and recourse has largely developed separately, leaving recourse behavior under distribution shifts as an open topic.Related work also covers how distribution shifts affect classifier accuracy, uncertainty, interpretability, and fairness.Source: §2 · p. 2
  • Recourse generation has also used tree ensembles, feature-importance measures, latent-space perturbations, SAT solvers, genetic algorithms, determinantal point processes, and growing spheres.The review presents these as examples among a wider range of approaches.Source: §2 · p. 2
  • This paper uses counterfactual explanation, actionable recourse, and contrastive explanation interchangeably for finding a positively classified point from a negatively classified one.The definition is scoped to a black-box binary classifier.Source: §2 · p. 2
  • Generic approaches include gradient-based distance minimization and integer programming restricted to feature values observed in the data.The latter restriction is described as one way of ensuring actionability.Source: §2 · p. 3
  • Recourse methods are grouped as sparse counterfactuals, data support counterfactuals, and a causal counterfactual subcategory.The taxonomy distinguishes methods that promote sparsity from those that promote support from the data distribution; causal counterfactuals use causal data-support probabilities.Source: §2 · p. 3

3 Theoretical Analysis

The theoretical analysis formalizes recourse generation under model updates, establishes a trade-off between recourse cost and invalidation, and develops a strategy for deriving invalidation lower bounds.

3.1 Preliminaries

  • Sparse counterfactuals search using a cost function, whereas data-support recourses restrict candidates to points found in the data distribution.The paper describes Euclidean distance as a common cost for sparse recourses.Source: §3.1 · p. 3

3.2 Our Setup and Assumptions

  • The setup compares recourses from a model trained on one data sample with their predictions under a retrained model using the same model class and hyperparameters.The fraction of original recourses classified negatively by the updated model is the invalidation percentage.Source: §3.2 · pp. 3–4

3.3 The Cost vs Invalidation Trade-off

  • Lower-cost recourses have higher expected invalidation probabilities, so cost-minimizing algorithms favor recourses more vulnerable to model updates.The stated trade-off runs in both directions: lower invalidation probabilities imply higher recourse costs.Source: §3.3 · p. 5

3.4 Lower Bounds on Recourse Invalidation Probabilities

  • The analysis models sparse-counterfactual search as a Markov Decision Process and uses recourse-distribution assumptions to derive invalidation lower bounds.In the described search, each step depends on the previous iteration rather than the entire search history.Source: §3.4 · p. 5

Appendix.

The appendix characterizes recourse distances for linear models and derives invalidation probabilities under parallel model perturbations. It also states when the lower bound extends to nonlinear models.

Appendix

  • For linear classifiers, recourse distances from the decision boundary follow an exponential distribution for continuous data or a geometric distribution for ordinal data.The stated forms are f(l) = ρ·e^(−ρl) and f(l) = (1 − ρ)^(l−1)·ρ, respectively.Source: Appendix · p. 5
  • For linear models, invalidation probabilities under a parallel perturbation are 1 − e^(−ρδm) for continuous data and 1 − (1 − ρ)^δm for ordinal data.These expressions are stated for a constant perturbation δm between the models.Source: Appendix · p. 6
  • For nonlinear models under a constant parallel perturbation, the invalidation lower bound is achieved exactly when both models are linear.The appendix also gives lower-bound expressions for continuous and ordinal data.Source: Appendix · p. 6

4 Experimental Analysis

Experiments show that real-world distribution shifts can invalidate recourses across methods, while controlled tests find that invalidation generally increases with drift but not universally. The paper also identifies a cost–robustness trade-off for sparse counterfactual recourses and calls for methods that better withstand shifts.

4 Experimental Analysis

  • Experiments test cost-optimized, in-distribution, and causal recourses across temporal, geospatial, and data-correction shifts in criminal justice, education, and credit.Table 1 summarizes recourse invalidation proportions for the different shifts.Source: §4 · pp. 6–7, Table 1 · p. 7
  • On the temporal bail-data shift, most models exceed 95% accuracy, yet invalidation varies between methods and reaches all SVM recourses generated by CFE.Causal recourse was not tested because the underlying causal distribution was unknown.Source: §4 · p. 8
  • On the geospatial school-data shift, minimum invalidation is 30%; increasing model accuracy does not remove the observed invalidation.Some AR cases have undefined invalidation proportions because no recourses were generated; causal recourse was unavailable without a structural causal model.Source: §4 · p. 8
  • For data correction, SVM shows 100% invalidation with AR but 0% with CFE.The passage describes data correction as a shift that can occur when decision makers improve training data and redeploy models.Source: §4 · p. 8
  • In synthetic tests, invalidation generally increases with drift but is not universal: negative predictor shifts are robust, while other cases reach up to 100% invalidation.The figure caption reports that all models have accuracy above 99%.Source: §4 · pp. 8–9, Figure 3 · p. 9
  • Across real-world distribution shifts, recourses from state-of-the-art methods can be invalidated, including causally generated recourses.The experiments indicate that invalidation is not confined to a particular model type or recourse-generation algorithm.Source: §4 · p. 8, §5 · p. 9

5 Conclusion

  • For sparse counterfactual recourses, the theory finds a trade-off between minimizing cost and reducing invalidation, with a non-zero lower bound on invalidation probability.Theoretical examination of invalidation for data-support and causal recourse methods remains future work.Source: §5 · p. 9
  • The authors propose developing shift-robust recourse strategies, potentially by iteratively examining recourses during model training so highly vulnerable ones are not prescribed after deployment.This is presented as a future direction.Source: §5 · p. 9

A Theoretical Analysis

The analysis frames recourse generation for users of a black-box binary classifier and distinguishes negatively and positively classified users and the set of recourses. It describes recourse methods as searches from an instance toward a positively classified alternative, guided by cost or data support.

A.1 Preliminaries

  • The setup considers a black-box binary classifier trained on real-world users and the recourse returned for each user by an algorithm.Source: §A.1 · p. 13
  • The notation separates negatively classified users, positively classified users, and the set of recourses.Source: §A.1 · p. 13
  • Recourse methods search from an instance toward a positively classified alternative, with sparse methods using a cost function and data-support methods restricting alternatives to likely data points.The described sparse-method cost is usually an L1 or L2 distance; Ustun et al. [2019] use linear programming heuristics to optimize data-support recourses.Source: §A.1 · p. 13

A.2 The Cost vs Invalidation Trade-off

The section analyzes how model perturbations affect the invalidation risk of sparse counterfactual recourses. It establishes a trade-off: recourses with lower costs have higher invalidation probabilities, while more expensive recourses have lower probabilities.

A.2 The Cost vs Invalidation Trade-off

  • The analysis treats cost as Euclidean distance for sparse counterfactuals and models the updated classifier as a perturbation of the original model.The comparison considers two candidate recourses for the same data point.Source: §A.2 · p. 13
  • Lower-cost recourses have higher expected invalidation probabilities, while higher-cost recourses have lower probabilities under the updated model.Source: §A.2 · p. 13
  • The expected invalidation probability is modeled as a monotonically increasing function of a recourse’s distance from the updated decision boundary.The derivation assumes a zero-mean model perturbation and equal expected offsets for the compared recourses.Source: §A.2 · p. 14
  • Recourse cost and invalidation probability vary inversely: lower invalidation risk entails higher cost, and higher risk entails lower cost.Source: §A.2 · p. 15

A.3 Lower Bounds on Recourse Invalidation Probabilities

The section derives invalidation lower bounds by modeling sparse-recourse search as a Markov process and characterizing recourse distances from classifier boundaries. For parallel linear models it gives exact probabilities, and for parallel nonlinear models the linear case attains the lower bound.

A.3 Lower Bounds on Recourse Invalidation Probabilities

  • The lower-bound analysis first models counterfactual search as an MDP and uses hypothesized recourse distributions to derive invalidation bounds.Source: §A.3 · p. 15
  • Sparse-recourse search is Markovian and can be represented as an MDP, with counterfactuals as states, feature changes as actions, and positive predictions as terminal states.The described transition probabilities are 0 or 1, and actions reaching a terminal state receive reward 1.Source: §A.3 · pp. 15–16
  • Under a linear classifier, recourse distances from the classifier hyperplane follow an exponential distribution for continuous data and a geometric distribution for discrete data.The derivation relies on the memoryless property of the search process and an unrestricted search proceeding along the hyperplane normal.Source: §A.3 · p. 16
  • For parallel linear models, invalidation probabilities are 1 − e^(−ρδm) for continuous data and 1 − (1 − ρ)^δm for categorical data.Source: §A.3 · pp. 16–17
  • For parallel nonlinear models, the invalidation lower bound is achieved exactly when both models are linear.Source: §A.3 · p. 17

B.1 Compute Details and Licenses

The experiments used a single computer without a GPU, and the bail dataset was proprietary while the other datasets were public.

B.1 Compute Details and Licenses

  • The final results table can be generated in approximately four hours on an i-7 8th-generation processor with 16 GB of RAM and no GPU.Source: §B.1 · p. 17
  • The bail dataset is proprietary; the other datasets are public-domain datasets.Source: §B.1 · p. 17

B.2 Datasets Overview

The dataset overview reports total and negative-class counts, identifying negatively labeled points as the cases for which recourses are sought.

B.2 Datasets Overview

  • Table 2 summarizes each dataset by its total number of points and its number of negative-class points.The passage does not provide the individual dataset counts.Source: Table 2 · p. 18
  • The negatively labeled points are the cases a perfect classifier should identify as negative.Source: Table 2 · p. 18
  • Recourses are sought for the negatively labeled points in each dataset.Source: Table 2 · p. 18

B.3 Results

The results report potential recourse invalidation across temporal, geospatial, and data-correction shifts, with different accuracy patterns across the settings.

B.3 Results

  • Despite similarly high accuracies for M1 and M2 on D1 and D2, the Bail temporal shift shows significant invalidation for AR and CFE.Source: Table 3 · p. 18
  • For the Schools geospatial shift, M1 remains high-performing on D2, while M2 performs worse on D1; recourses are sometimes invalidated for AR and CFE.Source: Table 4 · p. 18
  • For German-credit data-correction shifts, model performance is usually slightly worse after the shift, and recourses are sometimes invalidated for AR, CFE, and Causal methods.Source: Table 5 · p. 19
Loading 2012.11788v3…