Towards Robust and Reliable Algorithmic Recourse
Authors: Sohini Upadhyay
Shalmali Joshi
Himabindu Lakkaraju
Venue: NeurIPS 2021 Poster (2021)
Keywords: Algorithmic Recourse
Counterfactual Explanations
Explainability

Abstract: As predictive models are increasingly being deployed in high-stakes decision making (e.g., loan approvals), there has been growing interest in post-hoc techniques which provide recourse to affected individuals.  These techniques generate recourses under the assumption that the underlying predictive model does not change. However, in practice, models are often regularly updated for a variety of reasons (e.g., dataset shifts), thereby rendering previously prescribed recourses ineffective.To address this problem, we propose a novel framework, RObust Algorithmic Recourse (ROAR), that leverages adversarial training for finding recourses that are robust to model shifts. To the best of our knowledge, this work proposes the first ever solution to this critical problem. We also carry out theoretical analysis which underscores the importance of constructing recourses that are robust to model shifts: 1) We quantify the probability of invalidation for recourses generated without accounting for model shifts. 2) We prove that the additional cost incurred due to the robust recourses output by our framework is bounded. Experimental evaluation on multiple synthetic and real-world datasets demonstrates the efficacy of the proposed framework.


Towards Robust and Reliable Algorithmic Recourse
Sohini Upadhyay" Harvard University supadhyay8g haraaardddee... edu
Shalmali Joshi" Harvard University shalmali@sess harvard.
Himabindu Lakkaraju
Harvard University h1 hlakkarajudhbs harvard. hwwp:auwwbbbbbaha.eeeeeee
Abstract
As predictive models are increasingly being deployed in high-stakes decision mak- ing (e.g., loan approvals), there has been growing interest in post-hoc techniques which provide recourse to affected individuals. These techniques generate re- courses under the assumption that the underlying predictive model does not change. However, practice. models are often regularly updated for a variety of reasons (e.g., dataset shifts), thereby rendering previously prescribed recourses ineffective. To address this problem, we propose novel framework, RObust Algorithmic Recourse (ROAR), that leverages adversarial training for finding recourses that are robust to model shifts. To the best of our knowledge, this work proposes the first ever solution to this critical problem. We also carry out theoretical analysis which underscores the importance of constructing recourses that are robust to model shifts: 1) We quantify the probability of invalidation for recourses generated without accounting for model shifts. 2) We prove that the additional cost incurred due to the robust recourses output by our framework is bounded. Experimental evaluation on multiple synthetic and real-world datasets demonstrates the efficacy of the proposed framework.
Introduction
Over the past decade, machine learning (ML) models are increasingly being deployed to make a variety of highly consequential decisions ranging from bail and hiring decisions to loan approvals. Consequently, there is growing emphasis on designing tools and techniques which can provide recourse individuals who have been adversely impacted by predicted outcomes [30]. For example, when an individual is denied a loan by a predictive model deployed by bank, they should be provided with reasons for this decision, and also informed about what can be done reverse When providing a recourse to an affected individual, it is absolutely critical to ensure that the corresponding decision making entity (e.g.. bank) is able to honor that recourse and approve any re-application that fully implements the recommendations outlined in the prescribed recourse Wachter et al. [31.
Several approaches in recent literature tackled the problem of providing recourses by generating local (instance level) counterfactual explanations/ 31 26 12 21 [8]. For instance, Wachter et al. 31 pro- posed gradient based approach which finds the closest modification (counterfactual) that result in the desired prediction. Ustun et al. [26] proposed an efficient integer programming based approach obtain actionable recourses in the context of linear classifiers. There has also been some recent research that sheds light on the spuriousness of the recourses generated by counterfacttall/oonttsiiie explanation techniques [31 26 and advocates for causal approaches 1
All the aforementioned approaches generate recourses under the assumption that the underlying predictive models do not change. This assumption, however, may not hold in practice. Real world
"Equal contribution
"Note that counterfactual explanations contrastive explanations and recourse 26 are used interchangeably in prior literature. Counterfactuallconttssii explanations serve as a means to provide recourse to individuals with unfavorable algorithmic decisions. We use these terms interchangeably to refer to the notion introduced and defined by Wachter al. 31
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

settings are typically rife with different kinds of distribution shifts (e.g, temporal shifts) 122] In order to ensure that the deployed models are accurate despite such shifts, these models are periodically retrained and updated. Such model updates, however, pose severe challenges to the validity of recourses because previously prescribed recourses (generated by existing algorithms) may no longer be valid once the model is updated. Recent work by Rawal et al. [24] has, in fact, demonstrated empirically that recourses generated by state-of- taall-ofthhealloorthmms are readily invalidated in the face of model shifts resulting from different kinds of dataset shifts (e.g., temporal, geospatial, and data correction shifts). Their work underscores the importance of generating recourses that are robust to changes in models i.e., model shifts. particularly those resulting from dataset shifts. However, none of the existing approaches address this problem.
In this work, we propose a novel algorithmic framework, RObust Algorithmic Recourse (ROAR) for generating instance level recourses (counterfactual explanations) that are robust to changes in the underlying predictive model. To the best of our knowledge, this work makes the first attempt at generating recourses that are robust to model shifts. To this end, we propose a novel minimax objective that can be used to construct robust actionable recourses while minimizing the recourse costs. Second, we propose set of model shifts that captures our intuition about the kinds of changes in the models to which recourses should be robust. Next, we outline an algorithm inspired by adversarial training to optimize the proposed objective. We also carry out theoretical analysis to establish the following results: i) we quantify the probability of invalidation for recourses generated without accounting for model shifts, and ii) we derive upper bound the relative increase in the costs incurred due to robust recourses (proposed by our framework) to the costs incurred by recourses generated from existing algorithms. Our theoretical results further establish the need for approaches like ours that generate actionable recourses that are robust to model shifts.
We evaluated our approach ROAR on real world data from financial lending and education domains, focusing on model shifts induced by the following kinds of distribution shifts data correction shift, temporal shift, and geospatial shift. We also experimented with synthetic data to analyze how the degree of data distribution shifts and consequent model shifts affect the robustness and validity of the recourses output by our framework as well as the baselines. Our results demonstrate that the recourses constructed using our framework, ROAR, are substantially more robust (67 100%) to changes in the underlying predictive models compared to those generated using state-of-the-arr recourse finding technqiues. We also find that our framework achieves such high degree of robustness without sacrificing the validity of the recourses w.r.t. the original predictive model or substantially increasing the costs associated with realizing the recourses.
2 Related Work
Our work lies at the intersection of algorithmic recourse and adversarial robustness. Below, discuss related work pertaining to each of these topics.
Algorithmic recourse As discussed in Section I several approaches have been proposed to con- 21 18 3
14 15 77. These approaches can be broadly characterized along the following dimensions 29 the level of access they require to the underlying predictive model (black box vs. gradients), if and how they enforce sparsity (only small number of features should be changed) in counterfactuals, if counterfactuals are required to lie on the data manifold or not, if underlying causal relationships should be accounted for when not, whether the output should be multiple diverse counterfactuals
struct algorithmic recourse for predictive models 31 26
12
generating counterfactuals or just a single counterfactual. While the aforementioned approaches have focused on generating instance level counterfactuals, there has also been some recent work on generating global summaries of model recourses which can be leveraged to audit ML methods [23). More recently, Rawal et al. 24 demonstrated that recourses generated by state-of-the-a art algorithms are readily invalidated due to model shifts resulting from different kinds of dataset shifts. They argued that model updation very common place in the real world, and it is important to ensure that recourses provided to affected individuals are robust to such updates. Similar arguments have been echoed in several other While there has been some recent work that explores the construction of other kinds of explanations (feature attribution and rule based explanations) that are robust to dataset shifts [66. our work makes the first attempt at tackling the problem of constructing recourses that are robust model shifts.
recent works 28 13 20
2

---

Adversarial Robustness The techniques that we leverage in this work are inspired by the adversar- ial robustness literature. Wachter et al. were the first remark on similarities between counterfactual generation and adversarial attacks, but did not leverage this connection to develop robust recourse
[I]] It now well established that MI. models are vulnerable to adversarial attacks [T0] 2 The adversarial training procedure was recently proposed as a defense against such attacks 19 32]
This procedure optimizes a minimax objective that captures the worst-case loss over a given set of perturbations to the input data. At high level, it is based on gradient descent; at each gradient step, solves an optimization problem to find the worst-case perturbation, and then computes the gradient at this perturbation. In contrast, our training procedure optimizes minimax objective that captures the worst-case over a given set of model perturbations (thereby simulating model shift) and generates recourses that are valid under the corresponding model shifts. This training procedure is novel and possibly of independent interest.
3 Our Framework: RObust Algorithmic Recourse
In this section, we detail our framework, RObust Algorithmic Recourse (ROAR). First, we introduce some notation and discuss preliminary details about the algorithmic recourse problem setting. We then introduce objective function, and discuss how to operationalize and optimize it efficiently.
3.1 Preliminaries
Let us assume we given a predictive model M : X' +,, where X' C R is the feature space, and y is the space outcomes. Let y = {0. 1 where 0 and 1 denote an unfavorable outcome (e.g., loan denied) and a favorable outcome (e.g., loan approved) respectively. Let E X be an instance which received a negative outcome i.e., M(x) = O. The goal here is to find a recourse for this instance x ie., determine
of changes that can be made to x: in order reverse the negative outcome. The problem of finding a recourse for x involves finding a counterfactual x' = x + for which the black box outputs a positive outcome i.e., M(x') = M(x +
There are, however, a few important considerations when finding the counterfactual x' + c. First, it is desirable minimize the cost (or effort) required to change x to x'. To formalize this, let us consider a cost function c: X' x X + IR.. - an instance x'. In practice, some of the commonly used cost functions are & or & distance (31, log-percentile shift [26). and costs learned from pairwise feature comparisons input by end users (23 Furthermore, since recommendations change features such as gender or race would be unactionable. it is important to restrict the search for counterfactuals in such a way that only actionable changes are allowed. Let A denote the set of plausible or actionable counterfactuals.
c(x, x') denotes the cost (or effort) incurred in changing
Putting it all together, the problem of finding a recourse for instance æ for which M(xx) = 0 can be formalized as:
arg min c(a,x') S.I. M(x'= =1
(I)
æ'EA
Eqn. captures the generic formulation leveraged by several of the state-of-the-art recourse finding algorithms. Typically, most approaches optimize the unconstrained and differentiable relaxation of Eqn. [ which is given below:
x'
= arg min (MM z'EA
(2)
where e y R. denotes a differentiable loss function (e.g., binary cross entropy) which ensures that gap between M(x') and favorable outcome is minimized, and A >> 0 is a trade-off' parameter.
3.2 Formulating Our Objective
As can be seen from Eqn. [ state-of-the-art recourse finding algorithms rely heavily on the assumption that the underlying predictive model M does not change. However, predictive models deployed in the real world often get updated. This implies that individuals who have acted upon previously prescribed recourses are no longer guaranteed a favorable outcome once the model is updated. To address this critical challenge, we propose a novel minimax objective function which generates counterfactuals that minimize the worst-case loss over plausible model shifts. We arrived at this approach after considering the following alternatives: (a) Update the predictive model as desired but ensure that individuals who were previously prescribed recourse will still be guaranteed favorable outcome. (b)
3

---

Update the predictive model while including constraints to ensure that previously offered recourses are still valid. Note that both of these scenarios would potentially incur huge monetary losses to relevant stakeholders (e.g, banks), hurting the adoption of these approaches. In case (a), banks may be required to guarantee credit to customers that are potentially not creditworthy under the new model and thereby risk losing money. In case (b), access to model training is assumed. Furthermore, training a predictive model under these constraints may be suboptimal and not reflective of the current data distribution, thereby accruing larger errors under the shifted population. There are incentives for stakeholders such as banks to adopt such practices which could potentially lead to huge monetary losses. While the optimal approach may vary on case by case basis, we propose our method to avoid the aforementioned pitfalls outlined in cases (a) and (b).
To formalize our proposed approach, let A denote the set of plausible model shifts and let Ma denote a shifted model where & e A. Our objective function for generating robust recourse x" for a given instance can be written as:
x" arg min max (Ms(2")) >c(x,
E"EA
where cost function c and loss function I are as defined in Section 3.1.
Choice of A Predictive models deployed in the real world are often updated regularly to handle data distribution shifts [22]. Since these models are updated regularly, it likely that they undergo small (and not drastic) shifts each time they are updated. To capture this intuition, we consider the following two choices for the set of plausible model shifts A:
A = =(0 E IR" 6min S 6, S δmaz Vi E {1-..n3).
A (ō RT ||01155 8maz}
where p 2 1. Note that perturbations E A can be considered as operations either on the parameter space or the gradient space of M. While the first choice of A presented above allows to restrict model shifts within a small range, the second choice allows us to restrict model shifts within a nolm-ball. Alternate formulations of the first include incorporating domain knowledge set 6min and 6men per feature. These kinds of shifts can effectively capture small changes to both parameters (e.g., weights of linear models) as well as gradients. Next, we describe how optimize the objective in Eqn. 3 and construct robust recourses.
3.3 Optimizing Our Objective
While our objective function, the choice of A and the perturbations å E A we introduce in Section 3 3.2 are generic enough handle shifts to both parameter space as well the gradient space of any class of predictive models M, we solve our objective for a linear approximation f of M. The procedure that we outline here remains generalizable even for non-linear models because local behavior of a given non- non-linear model can be approximated well by fitting local linear model [25]. Note that such approximations have already been explored by existing algorithmic recourse methods [26] 23 Let the linear approximation, which we denote by be parameterized by E W. We make this parametrization explicit by using a subscript notation: fu. We consider model shifts represented by perturbations to the model parameters operationalized as additive perturbations ó E A to w. We will represent the resulting shifted classifier by fw+s. Our objective function (Eqn. 3) can now be written in terms of this linear approximation as:
W. In the case of linear models, these can be
x arg min max ((f") 1) Ac(x,x")
(4)
x"EA SEA
Notice that the objective function defined in Equation 4 is similar to that of adversarial training [19 However, in our framework, the perturbations are applied to model parameters as opposed to data samples. These parallels help motivate the optimization procedure for constructing recourses that are robust to model shifts. We outline the optimization procedure that we leverage to optimize our minimax objective (Eqn. 4 in Algorithm T
Algorithm| proceeds in an iterative manner where we first find a perturbation 8 E A that maximizes the chance of invalidating the current estimate of the recourse x". and then we take appropriate gradient steps on x" to generate valid recourse. This procedure is executed iteratively until the objective function value (Eqn. converges.

---

Algorithm Our Optimization Procedure
Input: x s.t. fw((x) = 0, fw, À > 0, A, learning rate > 0.
Initialize x² x = repeat
ary A ((fm+o(("))
9 = [llw+ss 1) + ac(x",00 x0)
x" og
until convergence
Return
4 Theoretical Analysis
Here carry out theoretical analysis to shed light on the benefits of our framework ROAR. More specifically: 1) We quantify the probability that recourses generated without accounting for model shifts likely to be invalidated. 2) We prove that the additional cost incurred due to the robust recourses output by our framework bounded.
We first characterize how recourses that do not account for model shifts (i.e., recourses output by state-of-the-art algorithms) fare when true model shifts can be characterized as additive shifts model parameters. Specifically, we quantify the likelihood that recourses generated without accounting for model shifts will be invalidated (even if they lie the original data manifold), under certain conditions.
Theorem 1. For given instance (N, E), let x' be the recourse that lies on the original data manifold (conditioned on the event that M(x') > 0.5) and is obtained without accounting for model
shifts. Let Σ DDT Then, for some true model shift 8, such that, pw+88'p
P
and DVDU
VDDWwll
2e V
2 erfel
v2||u++]|1 ), for 3 2 1, the probability that x' is invalidated on
(w++5)
fw+s is at least: /// gaussian error function.
2e VB-1 exp
4/D6w1 erfel
(w488) where erfe is the complementary /2[[=+]]]|
Proof Sketch. Under the assumption that x' ~ (u,, E), recourse is invalid under model shift if is valid under the original model and invalid under the shifted model. This allows us define the region where z' can be invalidated:
Ω = (a':wTa 0 (w + 5) 50}
The probability that x' invalidated can be obtained by integrating over Ω under the PDF of N(,, E).
We can then transform z' and correspondingly Ω. to simplify this integration over I-dimensional Gaussian random variable. That is,
= 1
C2
1 s
P(x is invalidated)
ds
(5)
((2m)
2
where Ω2 {s: (2),
-w" and C2 [VDUW
- (w+8)
(VD(U(+))]
The above quantity can be represented difference in the Gaussian error function allowing to exactly quantify the invalidation probability under our assumptions. Using the lower bounds on the complementary gaussian error function [9] from Chang al. [5), we obtain our lower bound. To derive
(w" 2)
2 erfe(- (w++)) y [ v-[ mainly to confirm that the lower bound on the first term still dominates the second term. Both conditions restricts the types of shift for which the bound can be derived. Note that / can be optimized away improve the lower bound. Detailed proof provided the Appendix. Discussion about other distributions (c.g., Bernoulli, Uniform, Categorical) is included in the Appendix.
the lower bound, we add an extra condition that v 2c -
exp
D
5

---

Next we characterize how much more costly recourses can be when they are trained to be robust model perturbations or model shifts. In the following theorem, we show that the cost of robust recourses is bounded relative to the cost of recourses that do not account for model shifts.
Theorem 2. Let x: E X, and x where is distribution such that [a μ < oc, where X is a metric space (X, d)--)) and d X X Rt. Let d _ l and assume that (X,d) has bounded diameter D = supz,x'EA d(z,x') Let recourses obtained without accounting for model shifts and constrained to the manifold be denoted by x' ~ v, and robust recourses be denoted by z". Let ô > O be the shift that maximizes Eq. for sample æ corresponding x". Further assume that the ROAR objective (Equation) 3) is convex in x" for a fixed 6. For l Liog (the cross-entropy loss), some 0 < 1/ & 1, w.h.h.p (1 7)), we have that:
1 1
D2 2
log (1)
c(a",x) c(
A ||0 8|| Exlexp oww + 8)
(6)
Proof Sketch. By definition, any recourse x' generated without accounting for model shifts will have a higher loss for Equation compared to the robust recourse x" (note that finding the global minimizer not guaranteed by Algorithm[]]
Using this insight, and convexity in x' for fixed 6, we can bound the cost difference between the robust and non-robust recourse by I-Lipschitz function (i.e. the logistic function):
c(a", .) c(x',x) S m|Il + 81|
log (1 + exp (w + 6)"x²}
Assuming a bounded metric on X', we can upper bound the RHS using Lemma 2 from van Handel (27) which gives us our bound. Detailed proof including special cases when v Gaussian, provided in the Appendix.
This result suggests that the additional cost of recourse is bounded by the amount of shift admissible in Equation 3 Note that Theorem 2 applies for general distributions so long as the mean is finite, which is the case for most commonplace distributions like Gaussian, Bernoulli, Multinomial etc. While Theorem [ demonstrates the probability that a recourse will be invalidated for Gaussian distributions, we refer the reader to the Appendix B. for discussion of other distributions, e.g. Bernoulli, Uniform, Categorical.
5 Experiments
Here we discuss the detailed experimental evaluation of our framework, ROAR. First, we evaluate how robust the recourses generated by our framework are model shifts caused by real world data distribution shifts. We also assess the validity of the recourses generated by our framework w.r.t. the original model, and further analyze the average cost of these recourses. Next, using synthetic data, we analyze how varying the degree (magnitude) of data distribution shift impacts the robustness and validity of the recourses output by our framework and other baselines.
5.1 Experimental Setup
Real world data We evaluate our framework on model shifts induced by real world data distribution shifts. To this end, we leverage three real world datasets which capture different kinds of data distribution shifts, namely, temporal shift, geospatial shift, and data correction shift 24 Our first dataset is the widely used and publicly available German credit dataset [8] from the UCI repository. This dataset captures demographic (age, gender), personal (marital status), and financial (income, credit duration) details of about 1000 loan applicants. Each applicant is labeled as either a good customer bad customer depending on their credit risk. Two versions of this dataset have been released, with the second version incorporating corrections to coding errors in the first dataset [II]. Accordingly, this dataset captures the data correction shift. Our second dataset is the Small Business Administration (SBA) case dataset [17]. This dataset contains information pertaining to 2102 small business loans approved by the state of California during the years of 1989 2012, and captures temporal shifts in the data. It comprises of about 24 features capturing various details of the small businesses including zip codes, business category (real estate vs. rental vs. leasing), number of jobs created, and financial status of the business. It also contains information about whether a business

---

has defaulted on loan or not which we consider as the class label. Our last dataset contains student performance records of 649 students from two Portuguese secondary schools, Gabriel Pereira (GP) and Mousinho da Silveira (MS) B 6), and captures geospatial shift. It comprises of information about the academic background (grades, absences, access to internet, failures etc.) of each student along with other demographic attributes (age, gender). Each student is assigned class label of above average or not depending on their final grade.
Synthetic data We generate a synthetic dataset with 1K samples and two dimensions to analyze how the degree (magnitude) of data distribution shifts impacts the robustness and validity of the recourses output by our framework and other baselines. Each instance z is generated as follows: First, randomly sample the class label y E {0, 1) corresponding to the instance Conditioned upon the value of y,. we then sample the instance x as: x N (My: Myy. We choose μi = [-2,- -2 and
[41 = [+2, +2]", and Σg = Σ1 = 0.5I where μoo Eg and μ4,, Σι denote the means and covariance of the Gaussian distributions from which instances in class 0 and class are sampled respectively.
A scatter plot of the samples resulting from this generative process and the decision boundary of a logistic regression model fit to this data are shown in Figure Ta In our experimental evaluation, consider different kinds of shifts to this synthetic data:
(a) Original data & MM
(b) Mean shift
(c) Variance shift
(d) Mean & Variance shift
Figure I: Synthetic data and examples of model shift. From left to right we have (a) original synthetic
dataset, (b) shifted data and decision boundary after mean shift, (c) shifted data and decision boundary after variance shift, and (d) shifted data and decision boundary after mean and variance shift
(i) Mean shift: To generated shifted data, we leverage the same approach as above but shift the mean of the Gaussian distribution associated with class i.e., x ~ N( Σ,,) where 116 - po + [ax, 0J and μ4 = H1- Note that we only shift the mean of one of the features of class O so that the slope of the decision boundary of a linear model we fit to this shifted data changes (relative to the linear model fit on the original data), while the intercept remains the same. Figure lb shows shifted data with 1.5.
(ii) Variance shift: Here, we leverage the same generative process as above, but instead of shifting the mean, we shift the variance of the Gaussian distribution associated with class 0 i.e., i.c., N (H,, Xg) where M = (1 + 3)Σn and Σ Σ for some increment B E RR The net result here is that the intercept of the decision boundary of a linear model we fit to this shifted data changes (relative to the linear model fit on the original data), while the slope remains unchanged. Figure Ic shows shifted data with
3.
(ii) Mean and variance shift: Here, we change both the mean and variance of the Gaussian distri- bution associated with class 0 simultaneously (Figure Tcp. It can be seen that there are noticeable changes to both the slope and intercept of the decision boundary compared to Figure la
Predictive models We generate recourses for a variety of linear and non-linear models: deep neural networks (DNNs), SVMs, and logistic regression (LR). Here, we present results for a 3-layer DNN and LR: remaining results are included in the Appendix. Results presented here are representative of those for other model families.
Baselines We compare our framework, ROAR, the following state-of-the-an baselines: (i) counterfactual explanations (CFE) framework outlined by Wachter et al. [31]. (ii) actionable recourse (AR) in linear classification 226 and (iii) causal recourse framework (MINT) proposed by Karimi et al. [14]. While CFE leverages gradient computations to find counterfactuals, AR employs a mixed integer programming based approach to find counterfactuals that are actionable. The MINT framework operates on top of existing approaches for finding nearby counterfactuals. We use the MINT framework on top of CFE and ROAR and refer to these two approaches as MINT and ROAR- MINT respectively. As the MINT framework requires access to the underlying causal graph,
7

---

experiment with MINT and ROAR-MINT only on the German credit dataset for which such a causal graph available.
Cost functions Our framework, ROAR, and all the other baselines we use rely on a cost function that measures the cost (or effort) required to act upon the prescribed recourse. Furthermore, our approach as well as several other baselines require the cost function to be differentiable. So, we consider two cost functions in our experimentation: ε distance between the original instance and the counterfactual, and a cost function learned from pairwise feature comparison inputs (PFC) [3 26 23 PFC uses the Bradley-Tere to the cost required to act upon the prescribed recourse for any given instance x. For more details on this cost function, please refer to Rawal and Lakkaraju [23] In our experiments, follow the same procedure as Rawal and Lakkaraju [23] and simulate the pairwise feature comparison inputs.
model to map pairwise feature comparison inputs provided by end users
Setting and implementation details We partition each of our synthetic and real world datasets into two parts: initial data (D1) and shifted data (D2). In the case of real world datasets, D1 and D2 can be logically inferred from the data itself - c.g., in case of the German credit dataset, we consider the initial version of the dataset as D₁ and the corrected version of the dataset as Dg. In the case of synthetic datasets, we generate D2 and D2 as described earlier where D2 is generated by shifting D1 (See "Synthetic data" in Section (5.1).
We use 5-fold cross validation throughout our real world and synthetic experiments. On D1. we use 4 folds to train predictive models and the remaining fold to generate and evaluate recourses. We repeat this process times and report averaged values of our evaluation metrics. We leverage D2 only to train the shifted models M2. More details about the data splits, model training, and performance of the predictive models are included in the Appendix.
We use binary cross entropy loss and the Adam optimizer to operationalize our framework, ROAR. Our framework, ROAR, has the following parameters: the set of acceptable perturbations A (defined in practice by dmaa) and the tradeoff parameter X. In our experiments on evaluating robustness real world shifts, we choose dmas= 0.1 given that continuous features are scaled to zero mean and unit variance. Furthermore, in each setting, we choose the À that maximizes the recourse validity of M1 (more details in Section 5.1 "Metrics" and Appendix). In case of our synthetic experiments where we assess the impact of the degree (magnitude) of data distribution shift, features are not normalized, so we do grid search for both &aa and X. First, we choose the largest &maz that maximizes the recourse validity of M1 and then set À in a similar fashion (more details in Appendix). We set the parameters of the baselines using techniques discussed in the original works 31, 14 26 and employ a similar grid search approach if unspecified.
Following the precedents set forth in 26 and 23 we adapt AR and ROAR to non-linear models by first generating local linear approximations of these models using LIME 255 We refer to these variants AR-LIME and ROAR-LIME respectively.
Metrics. We consider two metrics in our evaluation: 1) Arg Cost is defined as the average cost incurred to act upon the prescribed recourses where the average is computed over all the instances for which a given algorithm provides recourse. Recall that we consider two notions of cost in our experiments - L distance between the original instance and the counterfactual, costs learned from pairwise feature comparisons (PFC) (See "Cost Functions" in Section 5.1. 2) Validity is defined as the fraction of instances for which acting upon the prescribed recourse results in the desired prediction. Note that validity is computed w.r.t. a given model.
5.2 Robustness to real world shifts
Here, we evaluate the robustness of the recourses output by our framework, ROAR, as well as the baselines. A recourse finding algorithm can be considered robust if the recourses output by the algorithm remain valid even if the underlying model has changed. To evaluate this, we first leverage our approach and other baselines to find recourses of instances in our test sets w.r.t. the initial model Mj. We then compute the validity of these recourses w.r.t. the shifted model M2 which has been trained on the shifted data. Let us refer to this as M2 validity. The higher the value of M2 validity, the more robust the recourse finding method. Table I shows the M2 validity metric computed for different algorithms across different real world datasets.
can be seen that recourse methods that use our framework, ROAR and ROAR-MINT, achieve the highest M2 validity across all datasets. In fact, methods that use our framework do almost twice as
8

---

Correction
Temporal Shi
Cnocgooinl Shi
Model
Cost
Recourse
Avg Cos
MM. Valddy
M, Validiy
Ang Cost
M. Validiy
MG Validiy
Avg Cos
MM Validay
M, Validiy
CHH
=012
1,00 0.00
0.27
1:0 0100
0.09
8.37
0.73
0,98
0.00
L.1
ROAR
AR
3.13
0.85
0014
0.32
1,00 0.00
1,00 1: 1,00
0.94
0.08
0.21
3.14
1.50
1 0.25
0.25
0.9 1. 0.01
1000
+ 0,00
0.16
0.02 0.98
0.06
10.88
5.29
0.28
1.67
1.00 L 0,00
1,00
0.00
0.43
0.67 1. 0.19
0.14
MINT
4.73
1.56
1.00
1 0.00
0.93
0.07
NA
NA
NA
NA
NA
NA
LR
BOARMMNT
CPE
0.0%
6.77
0.35
1.00=
1.00 + 0.00
1,00
0.00
0.24
NA
NA
NA
NA
NA
NA
0.10
AK
0.09
1,30 0.00
0.27
DOC
100
+ 0.00
0U9
0.05
0.32 003
1.00
0.00
0.24
0.33
PLC
RONK
0.36 = 0.08
1,00 =: 0.00
1.00
=: 0.00
0.44 + 0.12
099 + CL00
0.98 =: 0.01
1.20 = 0.00
1.00 a 0.00
0.91
E 0.07 NA
MINT
1,00
L15
1.00 1 0.00
0.95
0,08
NA
NA
NA
NA
NA
MONR-MENT
1.25
1,00 0.00
NA
NA
CPE
0.55
1,00
0.00
0.05
3.78
1:00
0.00
0.09
1000
0.71
1,00
0.00
DAS 0.09
LIME
0.38
0.15
0.16 1: 0.10
0.31
0.06
1.39
1 0.13
0.59
0.11
0.65
0.17
9.02
L.77
0.76
0.06
0.83
1. 0.10
LI
ROAR-LIME
L.83
0.19
0.78 1 0.06
0.72
0.10
4,50
1 0.24
0.98
1 1.002
0.97
0.02
21,05
3.58
1.00
0.00
0.97 1 0.03
MINT
2.24 1.25
0.81
0,022
0.11
NA
NA
NA
NA
NA
NA
NN
CRE
0.06 0.02
8.59
0.90
1,00 1 0.00
0.03
0.31
0.12
0.19 1 D06
1:0
1 100
0.50
0.13
0.45
0.0
1.00
0.00
1 0.14
AR-LIME
0.06 0.03
0.49 + 0.11
0.56
0.15
0.11
+ D.0
0.54
+ 0.08
0.62
+00 0.12
0.78 -
-015
0.84
= 0.06
0.52 + 0.11
PFC
ROAR-L
0.64
0.08
0.85 + 0.07
0.82 1,05
0.37
+ 0.07
0.99 + 0.01
0.99 + 0.0
1.66
0.21
1.00
= 0.00
1.97 + 0.04
MINT
0.60
0.07
0.15
NA
NA
NA
MONR-MINT
0.60
0.91 0.04
0.34
NA
NA
NA
NA
Table I: Avg Cost, M₁ (original) validity, and Ma (shifted model) validity of recourses across different real world datasets. Recourses that leverage our framework ROAR are more robust (higher M2 validity) compared to those generated by existing baselines.
good compared to other baselines on this metric, indicating that ROAR based recourse methods are quite robust. After ROAR, MINT is the next best performing baseline with respect M2 validity. This may be explained by the fact that MINT accounts for the underlying causal graphs when generating recourses.
We also assess if the robustness achieved by our framework is coming at a cost i.e., by sacrificing validity on the original model or by increasing avg cost. Table shows the results for the same. can be seen that ROAR based recourses achieve higher than 95% Mi validity in all but two settings. We compute the avg cost of the recourses output by all the algorithms on various datasets and find that ROAR typically has a higher avg cost (both under & and PFC cost functions) compared to CFE and AR baselines. As demonstrated through additional experiments in the Appendix, these relatively higher costs are expected given our Theorem 2 upper bound on ROAR cost. However, overall, MINT and ROAR-MINT seem to exhibit the highest avg costs and are the worst performing algorithms according to this metric. Since non-causal recourse methods assume independent features, and do not have to adhere to the underlying causal structure when finding counterfactuals, they can generate relatively lower cost counterfactuals even if those counterfactuals may not correspond to realistic data instances. This is likely one of the key reasons why we observe higher average costs in the causal recourse methods.
5.3 Impact of the degree of data distribution shift on recourses
Po00-LIPS LIPS
MARK-UM
1.0
0.2
Verkanoe
Shift
Cra 1000
sode- LIPe
0.2 0.6
Figure 2: Impact of the degree of data distribution shift validity of recourse: DNN classifier with l cost function (top row), DNN classifier with PFC cost function (bottom row); Validity of the recourses generated by all methods drops degree (magnitude) of the shift increases; The drop in the validity is much smaller for our method ROAR-LIME compared to other baselines.
9

---

Here, we assess how different kinds of distribution shifts and the magnitude of these shifts impact the robustness of recourses output by our framework and other baselines. To this end, we leverage our synthetic datasets and introduce mean shifts, variance shifts, and combination shifts (both mean and variance shifts) of different magnitudes by varying a and 3 (See "Synthetic data" in Section 5. We then leverage these different kinds of shifted datasets to construct shifted models and then assess the validity of the recourses output by our framework and other baselines w.r.t. the shifted models.
We generate recourses using our framework and baselines CFE and AR for different predictive models (LR, DNN) and cost functions (f distance, PFC). Figure 2 captures the results of this experiment for DNN model both with & distance and PFC cost functions. Results with other models are included in the Appendix. It can be seen that the x-axis of each of these plots captures the magnitude of the dataset shift, and the y-axis captures the validity of the recourses w.r.t. the corresponding shifted model. Standard error bars obtained by averaging the results over 5 runs are also shown.
can be seen that the magnitude of the distribution shift increases, validity of the recourses generated by all the methods starts dropping. This trend prevailed across mean, variance, and combination (mean and variance) shifts. It also be seen that the rate at which validity of the recourses generated by our method, ROAR-LIME, drops is much smaller compared to that of other baselines CFE and AR-LIME. Furthermore, our method exhibits the highest validity compared to the baselines as the magnitude of the distribution shift increases. CFE seems to be the worst performing baseline and the validity of the recourses generated by CFE drops very sharply even at small magnitudes of distribution shifts.
Conclusions & Future Work
We proposed a novel framework, RObust Algorithmic Recourse (ROAR), to address the critical but under-explored issue of recourse robustness to model updates. To this end, we introduced novel minimax objective to generate recourses that are robust to model shifts, and leveraged adversarial training to optimize this objective. We also presented novel theoretical results which demonstrate that recourses without accounting for model shifts are likely to be invalidated, underscoring the necessity of ROAR. Furthermore, we also showed that the additional cost incurred by robust recourses generated by ROAR are bounded. Extensive experimentation with real world and synthetic datasets demonstrated that recourses using ROAR are highly robust to model shifts induced by range of data distribution shifts. Our work also paves the way for further research into techniques for generating robust recourses. For instance, it would be valuable further analyze the tradeoff between recourse robustness and cost to better understand the impacts to affected individuals. Other interesting future directions include non-linear extensions that leverage novel local linear approximation methods that improve on LIME (33
Acknowledgements
We would like thank the anonymous reviewers for their insightful feedback. This work is supported in part by the NSF awards #IIS-20084 and 2049990, and research awards from the Harvard Data Science Institute, Amazon. Bayer, and Google. SJ would like to acknowledge the support of the Center for Research on Computation and Society (CRCS) at the Harvard John A. Paulson School of Engineering and Applied Sciences. The views expressed are those of the authors and do not reflect the official policy or position of the funding agencies.
References
[1] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, pages 274-283. PMLR, 2018
[2] Anish Athalye, Logan Engstrom, Andrew llyas, and Kevin Kwok. Synthesizing robust adver- sarial examples. In International conference on machine learning, pages 284-293, PMLR, 2018.
[3] Solon Barocas, Andrew D. Selbst, and Manish Raghavan. The hidden assumptions behind counterfactual explanations and principal reasons. Proceedings of the 2020 Conference on Fairness, Accountability, and Transpurency, Jan 2020. doi: 10.1 145/3351195.33778888 URL. org//0.1145/3355611 http: //dx:///x..o doi. fooi.org/11..o 111/100..111//// 1et.o1115/33110000 03555/3333109633338330
10

---

[4] Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopadhyay. Adversarial attacks and defences: A survey. arXiv preprint arXiv:1810.00069, 2018.
[5] Scok-Ho Chang, Pamela C Cosman, and Laurence B Milstein. Chernoff-type bounds for the gaussian error function. IEEE Transactions on Communications, 2011.
[6] Cortez and A. Silva. Using data mining to predict secondary school student performance, A. Brito and J. Teixeira Eds., Proceedings of 5th FUture BUsiness TEChnology Conference, 2008.
[7] Amit Dhurandhar, Tejaswini Pedapati, Avinash Balakrishnan, Pin-Yu Chen, Karthikeyan Shan- mugam, and Ruchir Puri. Model agnostic contrastive explanations for structured data, 2019.
[8] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:://rrcci ics.uci. edi.mmmmmmm
[9] JWL Glaisher. Liv. on a class definite integrals.-pan ii. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 1871.
[10] lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint 1rXiv:1412..5777 2014.
[11] U Grömping. South german credit data: Correcting a widely used data set. Reports in Mathematics, Physics and Chemistry, Department Beuth University of Applied Sciences Berlin, 2019.
[12) Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Model-agnostic counter- factual explanations for consequential decisions, 2019.
[13] Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: definitions, formulations, solutions, and prospects. arXiv preprint arXiv:2010.04050, 2020.
[14] Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counterfactual explanations to interventions. arXiv preprini arXiv:2002.06211 2020.
[15] Amir-Hossein Karimi, Julius von Kügelgen, Bernhard Schölkopf, and Isabel Valera. Algo- rithmic recourse under imperfect causal knowledge: a probabilistic approach. arXiv preprint arXiv:2006.cm 06831, 2020.
[16] Himabindu Lakkaraju, Nino Arsov, and Osbert Bastani. Robust and stable black box explana- tions, 2020.
[17] Min Li, Amy Mickel, and Stanley Taylor. "should this loan be approved or denied?": A large
dataset with class assignment guidelines. Journal of Statistics Education, 26(1):55 66, 2018. doi: 10.1080/1069 898.888888 2018. 14334442. URLhttta::///
wwg//0. /tt.attt::////....////////////// http:///aaa..ao//...0000//111999 2018 1434342
[18] Arnaud Van Looveren and Janis Klaise. Interpretable counterfactual explanations guided by prototypes, 2019.
[19] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018. URL http:tts////poreiiieee wttp://www.eeeeoooo////ddttttdt
[20] Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. On counterfactual explanations under predictive multiplicity, 2020.
[21] Rafael Poyiadzi, Kacper Sokol, Raul Gantos-Rodriguez Tijl De Bie, and Peter Flach. Face: Fea- sible and actionable counterfactual explanations. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, AIES '20, page 344-350, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 978 7781440371100 100. doi: 10. 10.1 10.1145/375627.3755550. URL
https://dol.org/100
3375850
[22] Stephan Rabanser, Stephan Günnemann, and Zachary Lipton. Failing loudly: An empirical study of methods for detecting dataset shift. In Advances in Neural Information Processing Systems, pages 1396-14000 2019.
[23] Kaivalya Rawal and Himabindu Lakkaraju. Beyond individualized recourse: Interpretable and interactive summaries of actionable recourses. Advances in Neural Information Processing Systems, 33, 2020.
11

---

[24] Kaivalya Rawal, Ece Kamar, and Himabindu Lakkaraju. Can i still trust you?: Understanding the impact of distribution shifts on algorithmic recourses. arXiv preprint arXiv:2012.11788,
2020.
[25] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should i trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135-1 144, 2016.
[26] Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse linear classification. Proceedings of the Conference Fairness, Accountability, and Transparency FAT* '19, 2019. doi: 10.1 10.1145/3285560.3338 32875666. URRLhttp:///// //tp:://dxx doi www..o........ 1145//287560.32888
[27] Ramon van Handel. Probability in high dimension. Technical report, PRINCETON UNIV NJ, 2014.
[28] Suresh Venkatasubramanian and Mark Alfano. The philosophical basis of algorithmic recourse. In Proceedings of the 2020 Conference on Fairness, Accountabilityy and Transparency, pages 284-293, 2020.
[29] Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning: A review. arXiv preprint arXiv:2010. 10596, 2020.
[30] Paul Voigt and Axel Von dem Bussche. The eu general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 10:3152676, 2017.
[31] Sandra Wachter, Brent D. Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. CoRR, abs/ 0ts//711..0033 2017.
URL http::/arxivv httt:://arrii.oorraaa//111.1.. 003999
[32] Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pages 5286-5295.
PMLR, 2018.
[33] Xingyu Zhao, Xiaowei Huang, V. Robu, and D. Flynn. Baylime: Bayesian local interpretable model-agnostic explanations. UAI, abs/2012.03058, 2021.
12


Reviews:
[{"review_id": "wOR-WhhB9Pf", "reviewer": "Reviewer_efp6", "summary": "The paper proposes a method to construct recourses that are valid under worst case additive model shifts for linear models and applied to non-linear ones with LIME. The paper analyzes these robust recourses theoretically but not for the given algorithm. I think the paper overall is of great quality but it lacks in novelty in particular because of related work that shares the exact same problem formulation and experimental setup (see [25] as authors cite).  The algorithmic recourse problem is also of limited practical applicability, and thinking about robust (but much less realistic) recourses, does not help address the problems that help make algorithmic recourse more practically applicable. The proposed algorithm to solve the problem which is the main contribution of the paper is not analyzed theoretically, and empirical evidence do not discuss Theorem 2 which talks about the average cost of the recourses. \nI think the paper is borderline primarily because of how similar it is to prior work. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The paper proposes a method to construct recourses that are valid under additive model shifts for linear models and applied to non-linear ones with LIME. The observation that recourses are invalidated with model shifts has been deeply explored in prior work that the authors reference heavily, moreover, the formulation of the problem and the experimental setup mimic exactly that of the related work [25]. Thus the main novelty here is the contribution of a method and worst-case formulation to obtain recourses. They also provide theoretical analysis for these robust recourses (but crucially not those obtained by the algorithm). I think there is limited novelty in the paper in terms of formulation and experiments and the nature of the approach, but it is an interesting combination of ideas. \n\nQuality: The experimental results are clear and very well compared to the baselines and well as the theoretical results are well argued for. However I have some important notes on Theorem 1 which caused a lot of confusion for me, notably how x' is sampled independently. Furthermore, I am a bit uneasy about the increase in avg cost in the experiments and the lack of experimental discussion about it. See comments below for more details. \n\nClarity: The paper is very well written and easy to follow.\n\nSignificance: I think the lesson that recourses become invalidated when models change has already been discussed, so this paper tries to solve that problem with a worst case approach and propose a straightforward gradient method. I haven't seen practical uses for algorithmic recourse yet, nor are any cited (please prove me wrong on this point if I am mistaken). So deriving robust recourses with this approach that has no stated guarantees does not address practical or theoretical challenges that need to be solved first. I am not convinced from the point of average cost that the robustness guaranteed is worth future validity, from the empirical point of view, from the theoretical perspective Th2 is a nice guarantee. The empirical setup is also borrowed from prior work, so that researchers can look at older papers for this kind of setup. \n\nLimitations: 1) no guarantees on algorithm, 2) no empirical discussion of Theorem 2 and the increase in average cost, 3) limited form of model shifts that apply only to linear models. \n\nComments:\n\nExtension to multiclass? \n\nCan we define recourses in terms of probabilistic model? I.e. a recourse of \\delta is that that increases the probability of a positive outcome by \\delta, or sequential recourses that can be thought of as a curriculum for the individual.  That I think is a much more useful practical definition.\n\nSupposedly as designers we control the model and have historical data on our users and recourses, why not update the model constrained by the fact that old recourses must still hold? This is arguably a cleaner approach that avoids worst case thinking. However, it makes a further assumption that we control the model, but this is reasonable in a lot of settings.\n\nThe choice of delta: clear typo of using n in definition? It is not written elsewhere that M’s weights are a single vector in R^p. The shifts are very limited, even for linear models, I would at least expect \\delta_{min} and \\delta_{max} to depend on each feature, is that extension easy to do? \n\nThere is a big assumption of approximating a non-linear model by a linear one locally, I am not sure how much weight I put on the validity of LIME explanations. \n\nAlgorithm 1 is an algorithm on the individual level, and so can be run independently which is nice.\n\nIn theorem 1, I don't understand what does it mean for x’ to lie on the original data manifold. In parentheses it is written that x’ is sampled from a normal distribution, the same as that of x, is that sampling independent? If so, then it is not possible that x’ is a recourse as x’ is only a function of x (which can be random, but the theorem says “THE” recourse which implies it is a deterministic map to add to the confusion). In the proof it is not clear how x’ is initially obtained, because if x’ is a recourse then it is a given that w^Tx’ >0! But you add that as a condition in \\omega.  \n\nThere is no analysis to the performance of the given algorithm, as section 4 assumes to be able to fully solve the optimization problem. I would like to see some argumentation for why the algorithm performs well theoretically.\n\nIn table 1, M1 and M2 validity results are very promising, but the lack of discussion on what does the increase in average costs imply is a bit unsettling. I would have liked to see in the experiments what is the lower limit on costs to achieve this high of M1&M2 validity, without context, I am unsure how bad the increase in avg cost is. Figure 2 helps tell me that the increase in avg cost is not too high because with a mean shift of 1, validity becomes very low, so that x’ was not on the extremes. I would have liked to see visual examples in the synth setting of original points x and recourses x’ for the different methods to understand what is happening. \n\n\n---------------- \nPost response: I have read the authors response, the authors have given good responses to some of the concerns I had, my recommendation however remains a weak accept ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is limited discussion to how realistic the recourses suggested in the paper can be applied in practice. There is limited proof that if we take a recourse from any of the datasets, then that recourse establishes a route for an individual to change their discussion, or how can they accomplish that change. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "dmobVPkM4db", "reviewer": "Reviewer_aXPK", "summary": "This paper proposes an algorithm for the automatic generation of counterfactual examples, that are robust to a certain amount of model shift, e.g., by retraining. The probability of invalidation of counterfactuals and the cost of robust counterfactuals are analyzed theoretically and the algorithm is evaluated on 3 tabular real-world and on synthetic data sets.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The formulation of the Counterfactual problem under predictive multiplicity is already discussed in the literature (see for example Pawelcyzk). Nevertheless, the proposed method for generating robust counterfactual examples under model shift is novel, so this work advances the state-of-the-art. \n\nWhile the evaluation results show that the method leads to more robust counterfactuals, the evaluation was conducted on relatively small datasets (with 1000, 2102, 649 lines respectively). Benchmarking on a larger dataset (e.g., Give Me Some Credit, 150k lines) would additionally highlight the scalability of the method. The synthetic dataset evaluation supports the findings, but the setup is very simple. (Maybe cut the synthetic data part for more real data set experiments). \n\nUnfortunately, the theory part has some issues. In general, the theorems only consider very special cases (linear classifier and simple exponential-family distributions) and implications for the actual methodology are not clear. Furthermore, the interpretation of the theoretic results is missing. The derived quantities are not explained or put into context. There are some theoretical problems that should be clarified by the authors (see below). In general, even if the derivation was correct, the unintuitive condition (no interpretation given) and the appearance of the beta value (which should be optimized out), makes it hard to see the implication of Theorem 1. \n\nThe bound in the second theorem linearly grows with the diameter of the dataset D, so the order of magnitude is the same as using a plain Lipschitz bound if c is Lipschitz-continuous. There are also some points in the derivation, which should be clarified. \n\nTheorem 1:\n1. $x'$ is assumed independent of the decision boundary; this is not realistic.\n2. What is the meaning of $\\beta$? Can it be maximized?\n\nTheorem 2:\n1. $\\delta$ is the worst case for each counterfactual (this is a coupled min max problem, so it is not enough to solve each problem on its own!)  which can be very different for $x'$ and $x''$. If you assume the same $\\delta$ for both cases, your argument is not valid.\n2. In equation 33 onwards, it should be clearly marked, that the result is only valid with probability 1-$\\eta$\n3. The bounds that lead to equation 34 are not valid in general. Assume a Dirac distribution (or very narrow normal distribution, i.e. around zero). Then $E_\\mu[log(1+exp(-z))] = log(2)$ but $E_\\mu[z]=0$\n\n\nThe acronym \"ROAR\" is already taken and might be misleading (see https://research.google/pubs/pub47088/).\n\nIn conclusion, I find the paper is well written and addresses a relevant problem, but the theory part needs further consideration before it is ready for publication.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors mention some limitations, e.g., higher counterfactual costs, but there could be discussion on additional limitations, e.g. that the argmax problem in Algorithm 1 may not be accurately solved in general, which may prevent convergence and on the computational cost that come with the proposed aproach or a general solution.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "LAjBgKaoqqb", "reviewer": "Reviewer_Xovy", "summary": "This paper deals with the robustness of algorithmic recourse options given to users by common methods in the field, as models get updated over time. In particular, unlike previous works, this one proposes a solution that aspires to withstand distributional shifts in training data over time, space, correction to measurements, etc. The proposed solution, ROAR, is inspired by adversarial training. The work also introduces a lower bound on probability of invalidation of recourse options of models trained normally, as well as upper bound the added cost the output of ROAR might incur. Finally, the authors compare the performance of ROAR, as well as to a causal version of ROAR (combined with Karimi et al.'s MINT) to those of existing popular methods, and offer a sensitivity analysis, demonstrating on a synthetic dataset the effect of distributional shifts on validity of recourse options.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper seems overall novel to me, bearing great similarity to Rawal et al. (https://arxiv.org/abs/2012.11788v2), but being the more complete work of the two, promising greater contribution to the literature in my opinion. The proposed method and theoretical results seem like a good start to deal with the problem of algorithmic recourse and its validity over model updates.\n\nStrengths:\n1. Novel method proposed to deal with a recently identified possible concern in a relevant and impactful area of study.\n2. Initial theoretical foundation proposed is interesting.\n\nWeaknesses:\n1. Choices in method and experimental setting could be discussed and justified more carefully (I'll include suggestions below). \n\nQuestions to authors:\n1. (minor) in section 2, you quickly describe your connection to other works on adversarial robustness. It seems to me Wachter et al. 2017 were of the first to mention the connection between counterfactual explanations (precursor to algorithmic recourse) and adversarial examples. Might be worth mentioning that connection briefly. \n2. (minor) line 126 - the objective function seems to directly relate to a classification setting, yet you write after it \"denotes a differentiable loss function (e.g., mean squared error loss...\"; why not just name binary cross entropy directly?\n3. Section 3.2, choice of \\Delta -- both here and in the following, the authors consider shifts in terms of *small* perturbations to parameter space or gradient of the model. What is *small* in this context? Can we bound it? what if not all shifts can be described in terms of additive perturbations of this kind? Can we demonstrate the additivity in parameters space or gradients following the shifts demonstrated in real world data in the experiment section?\n4. line 165-6 - \"in our framework, the perturbations are applied to model parameters as opposed to data samples\". It is not immediately clear to me why one should choose to apply the perturbations in this case on the models rather than data samples. While I can see why it's reasonable, could the authors explain their choice more? I may have missed the point.\n5. line 179-80 - \"...when the model shifts can be characterized as additive shifts to model parameters\". Similar to the question above -- can all perturbations occurring as a consequence of distribution shifts be characterized as additive shifts?\n6. Section 5.1, Real world data - from the description of the SBA dataset and the student performance dataset it wasn't clear to me whether the distributional shifts as proposed would be quite enough to be called \"temporal\" and \"geospatial\" shifts, respectively. what is the temporal shift exactly for SBA? It doesn't seem like there were 2 different periods of collection, but a single continuous one? Not entirely clear to me what would be the data for M1 vs M2 without further discussion. As for the student performance dataset, are two collection points into schools in the same country reflect enough variation? Would be interesting to see what both these examples mean in terms of actual shifts occurring in model parameters/gradient, as well as in terms of variables, covariance matrices, etc. to get a better sense of what such shifts mean in practice.\n7. Discussion of Karimi et al. and causal methods in the experimental section - first, the authors only compare results to MINT and MINT-ROAR for the German credit score, citing the fact that only this dataset \"has an existing DAG\" via Karimi et al. However, this DAG of the German credit dataset is also not official or appeared with the original dataset. It was proposed by Karimi et al. as a conjecture, which the authors of this work could have done with the other remaining dataset in this section if they wanted to achieve a more comprehensive comparison. On a related but different point, in line 344-45, the authors state \"MINT and ROAR-MINT seem to exhibit highest avg costs.... likely because adhering to the causal graph incurs additional cost\"; this is almost a tautological sentence, just repeating the experimental result, without attempting to provide any explanation of why that might happen. I believe one possible hypothesis could be that recommending interventions on nodes in the root or close to root nodes in a causal graph might incur additional costs to downstream features, as the effect needs to be propagated through the DAG. Non-causal methods would assume independence of features, thus no downstream propagation of intervention effects, and only \"local\" cost to intervened nodes would appear, although this is very likely unrealistic.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not discuss limitation of their work, or much of its societal impact. Even the proposed future work citing \"tradoff between recourse robustness and cost to better understand impact...\" has been already somewhat done in this work, and its sister manuscript Rawal et al. However, given that most of the work deals and is motivated clearly by societal impact of algorithmic decision-making/decision-support systems, I believe its impact in this area is overall positive.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The expert reviewers for the most part appreciated the paper and were largely positive. There were many important issues raised but the reviewers felt the authors responded appropriately and suggested a reasonable path to addressing these within the scope of this review process. The authors are expected to carefully address the points raised by reviewers in a final version, including as they outlined in their response. This includes the points raised by about the theory and assumptions as well as justifying choices in the model -- the answers from the reviewers were adequate and they need to be incorporated into the paper.
Decision: Accept (Poster)