Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse
Authors: Martin Pawelczyk
Teresa Datta
Johan Van den Heuvel
Gjergji Kasneci
Himabindu Lakkaraju
Venue: ICLR 2023 poster (2023)
Keywords: Counterfactual explanations
algorithmic recourse
explainability

Abstract: As machine learning models are increasingly being employed to make consequential decisions in real-world settings, it becomes critical to ensure that individuals who are adversely impacted (e.g., loan denied) by the predictions of these models are provided with a means for recourse. While several approaches have been proposed to construct recourses for affected individuals, the recourses output by these methods either achieve low costs (i.e., ease-of-implementation) or robustness to small perturbations (i.e., noisy implementations of recourses), but not both due to the inherent trade-offs between the recourse costs and robustness. Furthermore, prior approaches do not provide end users with any agency over navigating the aforementioned trade-offs. In this work, we address the above challenges by proposing the first algorithmic framework which enables users to effectively manage the recourse cost vs. robustness trade-offs. More specifically, our framework Probabilistically ROBust rEcourse (PROBE) lets users choose the probability with which a recourse could get invalidated (recourse invalidation rate) if small changes are made to the recourse i.e., the recourse is implemented somewhat noisily. To this end, we propose a novel objective function which simultaneously minimizes the gap between the achieved (resulting) and desired recourse invalidation rates, minimizes recourse costs, and also ensures that the resulting recourse achieves a positive model prediction. We develop novel theoretical results to characterize the recourse invalidation rates corresponding to any given instance w.r.t. different classes of underlying models (e.g., linear models, tree based models etc.), and leverage these results to efficiently optimize the proposed objective. Experimental evaluation with multiple real world datasets demonstrates the efficacy of the proposed framework.

Published as a conference paper at ICLR 2023
PROBABILISTICALLY ROBUST RECOURSE: NAVIGATING THE TRADE-OFFS BETWEEN COSTS AND ROBUSTNESS IN ALGORITHMIC RECOURSE
Martin Pawelczyk's ; Teresa Datta', Johannes van-den-Heuvel' Gjergji Kasneci', Himabindu Lakkaraju UUniversity of Tübingen, Germany Harvard University, US
ABSTRACT
As machine learning models are increasingly being employed to make consequen- tial decisions in real-world settings, it becomes critical to ensure that individuals who are adversely impacted (e.g., loan denied) by the predictions of these models are provided with means for recourse. While several approaches have been proposed to construct recourses for affected individuals, the recourses output by robustness
these methods either achieve low costs (i.e., ease-of implemeetttiliiinnn to small perturbations (i.c., noisy implementations of recourses), but not both due to the inherent trade-off's between the recourse costs and robustness. Further- more, prior approaches do not provide end users with any agency over navigating the aforementioned trade-offs. In this work, we address the above challenges by proposing the first algorithmic framework which enables users to effectively man- age the recourse cost vs. robustness trade-off'.. More specifically, our framework Probabilistically ROBust rEcourse (PROBE) lets users choose the probability with which a recourse could get invalidated (recourse invalidation rate) if small changes are made to the recourse i.e., the recourse is implemented somewhat noisily. To this end, we propose novel objective function which simultaneously minimizes the gap between the achieved (resulting) and desired recourse invalidation rates, minimizes recourse costs, and also ensures that the resulting recourse achieves a positive model prediction. We develop novel theoretical results to characterize the recourse invalidation rates corresponding to any given instance w.r.t. different classes of underlying models (e.g., linear models, tree based models etc.), and leverage these results to efficiently optimize the proposed objective. Experimen- tal evaluation with multiple real world datasets demonstrates the efficacy of the proposed framework.
INTRODUCTION
Machine learning (ML) models are increasingly being deployed make variety of consequential decisions in domains such as finance, healthcare, and policy. Consequently, there is a growing emphasis on designing tools and techniques which provide recourse to individuals who have been adversely impacted by the predictions of these models (Voigt & Von dem Bussche, 2017). For example, when an individual is denied loan by a model employed by a bank, they should be informed about the reasons for this decision and what can be done to reverse it. To this end, several approaches in recent literature tackled the problem of providing recourse by generating counterfactual explanations (Wachter et al., 2018; Ustun al., 2019; Karimi et al., 2020a). which highlight what features need to be changed and by how much to flip a model's prediction. While the aforementioned approaches output low cost recourses that are easy to implement (i.e., the corresponding counterfactuals are close to the original instances), the resulting recourses suffer from severe lack of robustness as demonstrated by prior works (Pawelezyk et al., 2020b; Rawal et al., 2021). For example, the aforementioned approaches generate recourses which do not remain
"Corresponding author;

---

Published as a conference paper at ICLR 2023
h
h=1
h=1
XE
h 0
h=0
x
==0
(a) Low recourse cost and low recourse rohustness
(b) Medium recourse cost and medium recourse robustness
(c) High recourse cost and high recourse robustness
Figure 1: Pictorial representation of the recourses (counterfactuals) output by various state-of-the-ee recourse methods and our framework. The blue line is the decision boundary, and the shaded areas correspond to the regions of recourse invalidation. Fig. la shows the recourse output by approaches such as Wachter et al. (2018) where both the recourse cost as well as robustness are low. Fig. Ic shows the recourse output by approaches such as Sominguez-Olmedt recourse cost and robustness are high. Fig. lb shows the recourse output by our framework PROBE in response to user input requesting an intermediate level of recourse robustness.
et al. (2022) where both the
valid (i.e., result in a positive model prediction) if/when small changes are made to them (See Figure la). However, recourses are often noisily implemented in real world settings as noted by prior research (Björkegren et al., 2020). For instance, an individual who was asked to increase their salary by $500 may get promotion which comes with raise of $505 or even $499.95.
Prior works by Upadhyay et al. (2021) and Dominguez-Olmett address some of the aforementioned challenges and generate robust recourses. While the former constructed recourses that are robust to small shifts in the underlying model, the latter constructed recourses that robust to small input perturbations. These approaches adapted the classic minimax objective functions commonly employed in adversarial robustness and robust optimization literature to the setting of algorithmic recourse, and used gradient descent style approaches optimize these functions. In an attempt to generate recourses that are robust to either small shifts in the model or small input perturbations, the above approaches find recourses that are farther away from the underlying model's 's decision boundaries (Tsipras et al., 2018; Raghunathan et al., 2019), thereby increasing the recourse costs i.e., the distance between the counterfactuals (recourses) and the original instances. Higher cost recourses are harder to implement for end users as they are farther away from the original instance vectors (current user profiles). Putting it all together, the aforementioned approaches generate robust recourses that are often high in cost and are therefore harder to implement (See Figure Ic), without providing end users with any say in the matter. In practice, each individual user may have different preference for navigating the trade-off's between recourse costs and robustness e.g., some users may be willing to tolerate additional cost to avail more robustness to noisy responses, whereas other users may not.
et al. (2022) proposed methods to
In this work, we address the aforementioned challenges by proposing a novel algorithmic framework called Probabilistically ROBust rEcourse (PROBE) which enables end users effectively manage the recourse cost vs. robustness trade-offs by letting users choose the probability with which a recourse could get invalidated (recourse invalidation rate) if small changes are made to the recourse i.e. the recourse is implemented somewhat noisily (See Figure lb). To the best of our knowledge, this work is the first to formulate and address the problem of enabling users navigate the trade- offs between recourse costs and robustness. Our framework can ensure that resulting recourse is invalidated at most r% of the time when noisily implemented, where is provided input by the end user requesting recourse. To operationalize this, we propose a novel objective function which simultaneously minimizes the gap between the achieved (resulting) and desired recourse invalidation rates, minimizes recourse costs, and also ensures that the resulting recourse achieves positive model prediction. We develop novel theoretical results to characterize the recourse invalidation rates corresponding to any given instance w.r.t. different classes of underlying models (e.g., linear models, tree based models etc.), and leverage these results to efficiently optimize the proposed objective.
We also carried out extensive experimentation with multiple real-world datasets. Our empirical analysis not only validated our theoretical results, but also demonstrated the efficacy of our proposed framework. More specifically, found that our framework PROBE generates recourses that not
2

---

Published as a conference paper at ICLR 2023
only three times less costly than the recourses output by the baseline approaches (Upadhyay et al., 2021; Serninguuz-Olmeede et al., 2022), but also more robust (See Table 1). Further, our framework PROBE reliably identified low cost recourses at various target recourse invalidation rates in case of both linear and non-linear classifiers (See Table 1 and Figure 4). On the other hand, the baseline approaches were not only ill-suited to achieve target recourse invalidation rates but also had trouble finding recourses in case of non-linear classifiers.
2 RELATED WORK
Algorithmic Approaches to Recourse. As discussed earlier, several approaches have been proposed in literature to provide recourse to individuals who have been negatively impacted by model predic- tions (Tolomei et al., 2017: Laugel et al., 2017: Wachter al., 2018: Ustun et al., 2019; Van Looveren & Klaise, 2019; Pawelczyk et al., 2020a; Mahajan et al., 2019; Mothilal et al., 2020; Karimi et al., 2020a; Rawal & Lakkaraju, 2020; Karimi et al., 2020b; Dandl al., 2020; Antorán et al., 2021; Spooner et al., 2021). These approaches can be roughly categorized along the following dimensions (Verma et al., 2020): type of the underlying predictive model (e.g., tree based vs. differentiable classi- fier), whether they encourage sparsity in counterfactuals (i.c., only small number of features should be changed), whether counterfactuals should lie on the data manifold and whether the underlying causal relationships should be accounted for when generating counterfactuals, All these approaches generate recourses assuming that the prescribed recourses will be correctly implemented by users.
Robustness of Algorithmic Recourse. Prior works have focused on determining the extent to which recourses remain robust to the choice of the underlying model (Pawelczyk et al., 2020b; Black et al., 2021; Pawelezyk al., 2023), shifts changes in the underlying models (Rawal et al., 2021; Upadhyay et al., 2021), or small perturbations to the input instances (Artelt et al., 2021; Dominguez-OImee Olmedo al., 2022: Slack al., 2021). To address these problems, these works have primarily proposed adversarial inimax objectives to minimize the worst-case loss over a plausible set of instance perturbations for linear models to generate robust recourses (Upadhyay et al., 2021; Dominguez-Olmede et al., 2022), which are known to generate overly costly recourse suggestions.
In contrast to the aforementioned approaches our work focuses on user-driven framework for navigating the trade-offs between recourse costs and robustness to noisy responses by suggesting a novel probabilistic recourse framework. To this end, we present several algorithms that enable us to handle both linear and non-linear models (e.g., deep neural networks, tree based models) effectively. resulting in better recourse cost/nnalidatiion rate tradcoff's compared to both Upadhyay et al. (2021) and Dominguez-Olmedo et al. (2022).
3 PRELIMINARIES
Here, we first discuss the generic formulation leveraged by several state-of-the-ar recourse methods including Wachter et al. (2018). We then define the notion of recourse invalidation rate formally.
3.1 ALGORITHMIC RECOURSE: GENERAL FORMULATION
Notation Let h X + y denote a classifier which maps features x E X s IRd to labels y. Let )²= 10, where 0 and 1 denote an unfavorable outcome (e.g., loan denied) and favorable outcome (e.g., loan approved), respectively. We also define is (x)==(f(( (x(())) where f=X' - TR is a differentiable scoring function (e.g., logit scoring function) and g IR Y an activation function that maps logit scores to binary labels. Throughout the remainder of this work we will use g(u) I[u> > g]. where a decision rule in logit space. W.L.o.g. we will set 0
Counterfactual (CF) explanation methods provide recourses by identifying which attributes to change for reversing an unfavorable model prediction. Since counterfactuals that propose changes features such as gender are not actionable, we restrict the search space to ensure that only actionable changes are allowed. Let A denote the set of actionable counterfactuals. For given predictive model h and predefined cost function de Rd - R., the problem of finding a counterfactual explanation x + 6 for instance x Rdd is expressed by the following optimization problem:
X arg min ((((x'),)) 1)) X xx,)'), xEA
3

---

Published as a conference paper at ICLR 2023
where À 2 0 is trade-off parameter, and f(.-)) is the mean-squared-eeror (MSE) loss.
The first term on the right- hand-side ensures that the model prediction corresponding to the counter- factual ie.. hxx') is close to the favorable outcome label 1. The second term encourages low-cost recourses; for example, Wachter al. (2018) propose & or lg distances to ensure that the distance between the original instance and the counterfactual X is small.
3.2 DEFINING THE RECOURSE INVALIDATION RATE
In order to enable end users to effectively navigate the trade-offs between recourse costs and ro- bustness, we let them choose the probability with which a recourse could get invalidated (recourse invalidation rate) if small changes are made to i.e., the recourse is implemented somewhat noisily, To this end, we formally define the notion of Recourse Invalidation Rate (IR) in this section. We first introduce two key terms, namely, prescribed recourses and implemented recourses. A prescribed recourse is recourse that was provided to an end user by some recourse method (e.g.. increase salary by $500). An implemented recourse corresponds to the recourse that the end user finally implemented (e.g., salary increment of $505) upon being provided with the prescribed recourse. With this basic terminology in place. now proceed formally define the Recourse Invalidation Rate (IR) below.
Definition 1 (Recourse Invalidation Rate). For given classifier h, the recourse invalidation rate corresponding to the counterfactual X x ôg output by recourse method E is given by:
A Ee [+({)) - h(*E** +E ].
CF class
class response
where the expectation is taken with respect to a random variable e with probability distribution which captures the noise in human responses.
Leen Decied
Since the implemented recourses do not typ- ically match the prescribed recourses Xg (Björkegren et al., 2020), add to model the noise human responses. As we primarily compute recourses for individuals x such that Mxx) = O, the label corresponding to the coun- terfactual is given by =xx===1 and therefore A [0. For example. the following cases help understand our recourse invalidation rate metric better: When A=0, then the prescribed recourse and the recourse implemented by the user agree all the time; when A-0.5, the pre- scribed recourse and the implemented recourse agree half of the time, and finally, when A=1
Age: 34
Yeatly income: $52000
Loan amount: $20000
+0pen cedit lines
Savings: $5000
+330 59 days late payments:
Debtt ratio: 0.8
# Dependents::
Acceptod
Recourse suggestions
Invilisate targh ra
Irraliationn trgek r-22
bapel 0,10
ratto
-02 Bebtiabo
Ogen credit
-41000 Savinng
+6 132000 Yourly
Low rast
Medaze oestind
High costand righ
Figure 2: Practical view navigating the then the prescribed recourse and the recourse cost/robustness tradeoff for a credit loan example. implemented by the never agree. To illustrate our ideas, will our IR measure with Gaussian probability distribution (i.e., e ~ (O, I²))) to model the noise in human responses.
4
OUR FRAMEWORK: PROBABILISTICALLY ROBUST RECOURSE
Below we present our objective function, which is followed by discussion on how to operationalize efficiently.
4.1 RECOURSE INVALIDATION RATE AWARE OBJECTIVE
The core idea is find recourse x whose prediction any point y within some set around x belongs to the positive class with probability 1 1-r- r. Hence, our goal to devise an algorithm that reliably guides the recourse search towards regions of low invalidation probability while maintaining low cost recourse (see Fig. 2 for practical example). For a fixed model, our objective reads:
L = > R(x':o01)) xxe(((x)). 8)) Xx,
(3)
4

---

Published as a conference paper at ICLR 2023
where is the target score for the input o(" max(0, A(x':01)= r) with being the target IR, o") is the recourse invalidation rate from equation 1, A1 to X3 are the balance parameters, and de quantifies the distance between the input and the prescribed recourse. To arrive at a output probability of 0.5, the target score for f(x for a sigmoid function is 8 0, where the score corresponds to 0.5 probability for y 1.
The new component is a Hinge loss encouraging that the prescribed recourse has a low probability of invalidation, and the parameter o² is the uncertainty magnitude and controls the size of the neighbourhood in which the recourse has to be robust. The middle term encourages the score at the prescribed recourse f(x) to be close to the target score s, while the last term promotes the distance between the input x and the recourse X to be small.
In practice, the choice of r depends on the risk-aversion of the end-user. If the end-user is not confident about achieving 'precision landing', then a rather low invalidation target should be chosen (i.e., r 0.5).
4.2
OPTIMIZING THE RECOURSE INVALIDATION RATE AWARE OBJECTIVE
In order for the objective in equation 3 to guide us reliably to- wards recourses with low target invalidation rate r, we need approximate the invalidation rate A(x') any x' R However, such an approximation becomes non-trivial since the recourse invalidation rate, which depends on the clas- sifier h, is generally non- non-differentiable since the classifier l(x)= [(](x) E) defined in Section involves indi- cator function acting on the score f. To circumvent this issue, we derive a closed-form expression for the IR using local approximation of the predictive model f. The procedure suggested here remains generalizable even for non-linear models since the local behavior of given non-linea model can often be well approximated by fitting locally linear model (Ribeiro et al., 2016; Ustun et al., 2019).
Algorithm 1 PROBE
Input: s.t. f(x) < <0, 0², X>
a. 0r>0 0
Init.: x' =x;
Compute Á(x') > from Theorem
while A(x') and f(x) 0 do
Å @llsedFormIB(f.oo xx)
> from Theorem
x =x' a Vx Vx [ A)
D Opt. equation
end while
Return: x x
Theorem 1 (Closed-Fome Recourse Invalidation Rate). A first-order approximation Å to the recourse invalidation rate A in equation 2 under Gaussian distributed noise in human responses ~ N NO,,1l) given by:
f(XE)
-
(4)
( f(EE)
where & is the CDF of the univariate standard normal distribution N(, 1), [(xx) denotes the logit score at ig which is the recourse output by a recourse method E. and h(*g) E (0,
All theoretical proofs along with the proof to the above proposition can be found in Appendix D. In Algorithm 1, we show pseudo-code of our optimization procedure. Using gradient descent update the recourse repeatedly until the class label flips from 0 to 1 and the IR Á is smaller than the targeted invalidation rate r. In essence, the result in Theorem serves as our regularizer since it steers recourses towards low-invalidation regions. For example, when /xxx) (0)= = This means that the prescribed recourse and the recourse implemented by the user agree 50% of the time. On the other hand, when fxx) + co, then Å-0 since 1-11, which means that the prescribed recourse and the recourse implemented by the user always agree. Figure 3 demonstrates how PROBE finds recourses relative to standard low-cost algorithm (Wachter et al., 2018).
) = O, then Á = 0.5 since
We now leverage the recourse invalidation rate derived Theorem to show how the recourses output by Wachter al. (2018) be made more robust. Pawelczyk et al. (2022) provide a closed-fom solution for the recourse output by Wachter et al. (2018) w.r.t. the special case of a logistic regression classifier when de
Xx
x'1 ||2 and the MSE-loss is used. This solution takes the following form:
(x)),, where is the target logit score. More specifically, to arrive at the desired class with probability of 0.5, the target score for sigmoid function is 0, where the logit corresponds to a 0.5 probability for y The next statement quantifies the IR of recourses output by Wachter et al. (2018).
Xwachter (s) = x [x)]
5

---

Published as a conference paper at ICLR 2023
Proposition (Exact Recourse IR). For logistic regression, consider the recourse output by Wachter al. (2018); &wachter X 1
(x)
fx)). Then the recourse invalidation rate is given by:
A Waaharr (*x -1 f
8
(5)
where s is the target logit score.
A recourse generated by Wachter et al. (2018) such that ((WWachr = 0 will result in A 0.5. To obtain recourse that is more robust to noisy responses from users, i.e., A - 0, the decision maker can choose a higher logit target score of s' > 2 0 since this decreases the recourse invalidation rate, i... A (Xwachner ()) > A (xWactuer( ss))) The next statement makes precise how s should be chosen to achieve desired robustness level.
Corollary 1. Under the conditions of Proposition 1, choosing s, = - (0)(x)))1--11111 guarantees a recourse invalidation rate of r, i.e., A(SWachter (5, I2 =r.
On extensions to general noise distributions, and tree-based classifiers. In Appendix A we present extensions our framework to obtain (i) reliable recourses for general noise distributions and (ii) tree-based classifiers. These two cases pose non- non-trivial difficulties the recourse invalidation rate is generally non-differentiabbe As for the more general noise distributions, we develop a Monte-Carlo approach in appendix 1. which relies required to obtain a Monte-Carlo estimate of the invalidation rate. For tree-based classifiers, we develop a closed-form solution for the recourse invalidation rate (see Theorem 2).
differentiable approximation of the indicator function
4.3 ADDITIONAL THEORETICAL RESULTS
1.5 Invalidation 0.35
1.5
Invalidation
FROME
FSORE
In this section, we leverage the recourse in- validation rate expression derived in the pre- vious section to theoretically show i) that an additional cost has to be incurred to generate robust recourses in the face of noisy human responses, and ii) we derive a general up- per bound the IR which is applicable any valid recourse provided by any method with the underlying classifier being differ- entiable model.
6.5
Iepur
8.5
Inpue
-8.
-1.
Figure 3: Navigating between high and low invalida- tion recourses. The circles around PROBE's recourses have radius 2o, i.c., this is the region where 95% of re- course inaccuracies fall when o² 0.05. For instance, on the left we set an invalidation target of r = 0.35, i.e., 35% of the recourse responses would fail under spherical inaccuracies e ~ ~N00, 0.05- I).
Next, we show that there exists a trade- off between robustness to noisy human re- sponses and cost. To this end, we fix the target invalidation rate r, and ask what costs are needed to achieve fixed level
Propusition 2 (General Cost of Recourse). For a linear classifier, let r (0, and let xg = x + ög be the output produced by some recourse method E such that h(x=) = 1. Then the cost required to is:
achieve a fixed invalidation target
|5 w
(1))(1-))-c).
where
f(x) is constant, and 0 is the cosine of the angle between V fxx) and ög- o-]v/(x)1a
From Proposition 2, we see that the target invalidation rate decreases as the recourse cost increases for given uncertainty magnitude o², To make this more precise the next statement demonstrates the cost-robustness tradeoff.
Proposition 3 CCosstRRbsssnesss Tradeoff). Under the same conditions in Proposition 2, we have a(--)) w (1+)((1-)] > 0, i.e. an infinitesimal increase in robustness (i.e., - r)) increases the cost of recourse by _ x -(--((1-)))
a| a
Now, we derive a general upper bound on the recourse invalidation rate. This bound is applicable to any method E. that provides recourses resulting in positive outcome.

---

Published as a conference paper at ICLR 2023
Proposition 4 (Upper Bound). Let &g be the output produced by some recourse method E such that h(xg)= = Then, upper bound on from equation 4 is given by:
A(xE;O s
w
|V |
[vf(xx)l=
where
f(x) ~]V/(x)]=" òg xx-xEx and 0 is the cosine of the angle between V fxx and åg.
The right term in the inequality entails that the upper bound depends on the ratio of the & and lo-nomms of the recourse action d5 provided by recourse method E. The higher the f ratio of the recourse actions, the tighter the bound. The bound is tight when |ō assumes minimum value i.c. | 1 since at least one feature needs to be changed to flip the model prediction.
5 EXPERIMENTAL EVALUATION
We now present our empirical analysis. First, we validate theoretical results the recourse invalidation rates across various recourse methods. Second, we study the effectiveness PROBE at finding robust recourses in the presence of noisy human responses.
Rerl-World Data and Noisy Responses. Regarding real-world data, we use the same data sets as provided in the recourse and counterfactual explanation library CARLA (Pawelezyk al., 2021). The Adult data set Dua & Graff (2017) originates from the 1994 Census database, consisting of 14 attributes and 48, 84,842 instances. The class label indicates whether an individual has an income greater than 50,000 USD/year. The Give Me Some Credit (GMC) data set
(2011) is a credit scoring data set, consisting of 150,000 observations and 11 features. The class label indicates if the corresponding individual will experience financial distress within the next two years (Sirious is 1) or not. The COMPAS data set Angwin et al. (2016) contains data for more than 10,000 criminal defendants in Florida. It is used by the jurisdiction to score defendant's likelihood of re-offending. The class label indicates the corresponding defendant high or low risk for recidivism. All the data sets were normalized so that & [O, 1]d. Across all experiments, add noise E to the prescribed recourse Xg, where E ~ ~N 0². I) and o² 0.01.
Methods. We compare the recourses generated by PROBE to four differrnnt baseline methods which aim to generate low-cost recourses using fundamentally different principles: AR (-LIME) uses an integer-programminng baasad based objective Ustun al. (2019), Wachter
gradient-based objective (Wachter et al., 2018), DICE uses a diversity-basee objectve (Mothilal et al., 2020), and GS is based on random search algorithm (Laugel et al., 2017). Further, we compare with methods that use adversarial minmax objectives to generate robust recourse (Dominguez-Olmedo er al., 2022: Upadhyay et al., 2021). We used the recourse implementations from CARLA (Pawelezyk et al., 2021). Following Upadhyay et al. (2021), all methods search for counterfactuals over the same set of balance parameters e (0, 0.25, 0.5, 0.75, 1} when applicable.
Prediction Models. For all data sets, we trained both ReL.Ubbased NN models with 50 hidden layers (App. B) and logistic regerssion (LR). All recourses were generated with respect to these classifiers.
Measures. We consider three measures in our evaluation: 1) We measure the average cost (AC) required to act upon the prescribed recourses where the average taken with respect to all instances in the test set for which given method provides recourse. Since all our algorithms are optimizing for the E fn-ormm we use this as our cost measure. 2) We use recourse accuracy (RA) defined as the fraction of instances in the test set for which acting upon the prescribed recourse results in the desired prediction. 3) We compute the average IR across every instance in the test set. To do that, we sample 10,000 points from (N, o'I) for every instance and compute IR in equation 2. Then the average IR quantifies recourse robustness where the individual IRs are averaged over all instances from the test for which a given method provides recourse.
5.1 VALIDATING OUR THEORETICAL BOUNDS
Computing Bounds. We empirically validate the thcoretical upper bounds derived in Section 4.3. To do that, we first estimate the bounds for each instance in the test set according Proposition 4,
7

---

Published as a conference paper at ICLR 2023
Adal
Compas
GMC
Mocera
AR
Kachter
G1
PROBR
Wachtne
66
PROSE
AR
Machtar
G5
PR0BE
(t)
0.06
1.0
1.0
1.0
1.0
1.0
1.0
1.5
1.0
1.0
1.0
18
AIR (3)
0.5 0101
0.66
3:06-300
0.15-..1
0.31+
0:17-007
03-8:5
0.28 0.02
0.17-0006
0 0:45-000
0.24+ 0.01
AC 11
0.65 0.4
0.02
2:45
2.24
1.06
1.9 1.52
0.30.0.17
0.22
0.231.045
0.68 0.30
0.20
0.29. 0.31
3.00 0.55
1.0
MN
AIR
11,00 e.S
0,02
0.35 0.01
0.35 0.02
0.36 0
0.23 0..1
AE 01
Lib 0Z22
0.3 0.39
2:0 1.11
1. 0222
0.210.16
U.5 1154
0.2
0.20
0.122 0.00
(a) Comparing F PROBE to baseline recourse methods.
Adult
Compas
Measures
ROAR
ARAR
PROBE
RCAR
ARAR
PRORE
ROAR
ARAR
PROSF
RA(1)
1.0
1.0
1.0 0.31
1.0
0.59
1.0 0.28
1.0
1.0
1.0
LR
(1)
0.0 0.0
0.02=0.01
0.0
0.0
0.35
0.21
AC (1)
3.56 0.8
2.68 = 0.79
1.56 0.92
2,90 0.31
1.7
0.63
0:39
1.74 0.45
1.27 + 0.45
0.60 + 0.56
RA(1)
0.94
0.00
0.99
0.97
0.02
1.0
0.06
0.06
1.0
NN
(0)
0.0
0.51
0.35
0.06
0.46 0.0
0.333
0.3 0.21
0.45
0.25
(1)
1
L. 0.0"
1.43 0.49
6.41 1.07
0.02 1 0.0"
a 0.34
0.67 a 0.94
0.02 0.0"
(b) Comparing PROBE to adversarially robust recourse methods.
Table 1: Comparing PROBE to recourse methods from literature using recourse accuracy (RA), average recourse invalidation rate (AIR) for o² = 0.01 and average cost (AC) across different recourse methods. For PROBE, we generated recourses by setting r 0.35 and o² 0.01. (a): Recourses that use our framework PROBE are more robust compared to those produced by existing baselines. (b): Adversarially robust recourses are more costly than recourses output by PROBE. For ARAR and ROAR we set = 0.01. * Results with recourse accuracies less than 10% have not been considered.
Campaa
Carppe
100
Coox
(ubl X0
(54115)
ROAR
b-t 70
BOAR
F90186 Lnaid
AAXA
PRO
PROME
ARR2
(a) Logistic Regression
(b) Neural Network
Figure 4: Comparing PROBE to adversarially robust recourse methods using pareto plots that show the tradeoff between average costs and average invalidation rate (towards bottom left indicates a better performance). For PROBE, the invalidation target is r E {0.35, O.3, 0.25, 0.20, 0.15), and we generated recourses by setting o² e (0.005, 0.01, 0.015). The latter are used for ARAR and ROAR.
and compare them with the empirical estimates of the IR. The empirical IR, in turn, we obtain from Monte-Carlo estimates of the IR in equation 2; we used 10,000 samples to get stable estimate of IR.
Results, In Figure 5, we validate the bounds obtained in Proposition 4 for the GMC data sets. We relegated results for the Compas and Adult data set and other values of σ² to Appendix C. Note that the trivial upper bound value, which suggests that our bounds are meaningful. We observe that these upper bounds are quite tight, thus providing accurate estimates of the worst case recourse invalidation rates. is noteworthy that GS tends to provide looser bounds, since its recourses tend to have lower é ratios; for GS, its random search procedure increases the fy-norms of the recourse relative to the recourses output by other recourse methods. This contributes to a looser bound saying that the randomly sampled recourses by GS tend to provide looser worst-case IR estimates relative to all the other methods, which do use gradient information (e.g., Wachter, AR and P PROBE).
since A 1, and we see that our bounds usually lie well below this
5.2 EVALUATING THE PROBE FRAMEWORK
Results. Here, we evaluate the robustness, costs and recourse accuracy of the recourses generated by our framework PROBE relative to the baselines. We consider a recourse robust the recourse remains valid (i.e., results in positive outcome) even after small changes are made to it (i.e., humans implement it in a noisy manner). Table shows the average IR for different methods across different real world data sets and classifiers when o² = 0.01. Further, in Table 1a lowest invalidation rate across all real-world data sets and classifiers among the non-robust recourse methods, while PROBE provides the lowest cost recourses among the robust recourse methods (see
that PROBE has the
8

---

Published as a conference paper at ICLR 2023
GMC
Invalidation Rate
1.00
0.25
0.30
0.25
Empirical IR
Throreticd Bound
AK-LMME
Wachter
DICE
ROAR
AKAR
PROSE
Recourse Methods
Figure 5: Verifying the theoretical upper bound from Proposition on the logistic regression model. The red boxplots show the empirical recourse invalidation rates for AR ( (-LIME), Wachter, GS, DICE, ARAR the distribution of upper bounds evaluated by plugging in the corresponding quantities (i.c., o², w, etc.) into the bound. The results show no violations of our theoretical bounds. See appendix C for the full set of results.
0.01), ROAR (e 0.01) and PROBE (r 0.35, a² 0.01). The blue boxplots show
Table 1b). We also consider if the robustness achieved by our framework is coming at an additional cost i.e., by sacrificing recourse accuracy (RA) or by increasing the average recourse cost (AC). We compute AC of the recourses output by all the algorithms and find that PROBE usually has the highest or second highest recourse costs, while the RA at 100% across classifiers and data sets.
Finally, provide more detailed comparison between PROBE and the adversarially robust recourse methods ARAR and ROAR. To do so, we plot pareto frontiers in Figure which demonstrate the inher- ent tradeoffs between the average cost of recourse and the average recourse invalidation rate computed over all recousre seeking individuals for different uncertainty magnitudes x² c e (0.005, 0.01, 0.15). For ARAR and ROAR we expect see AIRs close to 0 (by construction). However, this is only the case for the linear classifiers. Moreover, ROAR provide recourses with up to 3 times higher cost relative our method PROBE. Note also that ARAR and ROAR have trouble finding recourses for non-linear classifiers, resulting in RA scores of around 5% in the worst case, while not being able to maintain low invalidation scores. This is likely due to the local linear approximation used by these methods. In summary, PROBE finds recourses for 100% of the test instances in line with the promise of having an invalidation probability at most r, while being less costly than ROAR and ARAR
Relegated results. The relegated experiments in Appendix C (i) demonstrate that baseline recourse methods are not robust to noisy human responses (Figures 8 9), (ii) verify that the targeted invalida- tion rates match the empirical recourse invalidation rates (Figures 13 15) and (iii) demonstrate the trade-off between recourse costs and robustness verifying Corollary 3 (Figures 16 17).
6 CONCLUSION
In this work, we proposed novel algorithmic framework called Probabilistically ROBust rEcourse (PROBE) which enables end users to effectively manage the recourse cost vs. robustness trade-offs by letting users choose the probability with which a recourse could get invalidated (recourse invalidation rate) if small changes are made to the recourse i.c., the recourse is implemented somewhat noisily. To the best of our knowledge, this work is the first to formulate and address the problem of enabling users to navigate the trade-offss between recourse costs and robustness. Our framework can ensure that a resulting recourse is invalidated at most r% of the time when it is noisily implemented, where is provided as input by the end user requesting recourse. To operationalize this, we proposed novel objective function which simultaneously minimizes the gap between the achieved (resulting) and desired recourse invalidation rates, minimizes recourse costs, and also ensures that the resulting recourse achieves a positive model prediction. We developed novel theoretical results to characterize the recourse invalidation rates corresponding to any given instance w.r.t. different classes of under- lying models (e.g., linear models, tree based models etc.), and leveraged these results to efficiently optimize the proposed objective. Experimental evaluation with multiple real world datasets not only demonstrated the efficacy of the proposed framework, but also validated our theoretical findings. Our work also paves the way for several interesting future research directions in the field of algorithmic recourse. For instance. it would be interesting build this work to develop approaches which can generate recourses that are simultaneously robust to noisy human responses, noise in the inputs, as well as shifts in the underlying models.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We would like thank the anonymous reviewers for their insightful feedback. This work is supported in part by the NSF awards #1IS-2008461 and #IIS-2049989, and research awards from Google, JP Morgan, Amazon, Bayer, Harvard Data Science Initiative, and D Institute at Harvard. HL would like to thank Sujatha and Mohan Lakkaraju for their continued support and encouragement. The views expressed here are those of the authors and not reflect the official policy or position of the funding agencies.
REFERENCES
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias:
There's software used across the country to predict future criminals. and it's biased against blacks, 2016.
Javier Antorán, Umang Bhatt, Tameem Adel, Adrian Weller, and José Miguel Hemmandez-Lobtoo. Getting a clue: A method for explaining uncertainty estimates. In International Conference on Learning Representations (ICLR), 2021.
André Artelt, Valerie Vaquet, Riza Velioglu, Fabian Hinder, Johannes Brinkrolf, Malte Schilling, and Barbara Hammer. Evaluating robustness of counterfactual explanations. arXivv2103.02354 2021.
Daniel Björkegren, Joshua E. Blumenstock, and Samsun Knight. Manipulation-prooo machine learning. arXiv:2004.0388 2020.
Emily Black, Zifan Wang, Matt Fredrikson, and Anupam Datta. Consistent counterfactuals for deep models. 1rXIv:2110.03109, 2021.
Vadim Borisov, Tobias Leemann, Kathrin Seßler, Johannes Haug. Martin Pawelczyk, and Gjergji Kasneci. Deep neural networks and tabular data: A survey. arXiv:2110.01889, 2021.
Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
Cristian Bucilua, Rich Caruana, and Alexandru Niculescu-Mizii, Model compression. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD), 2006.
Susanne DandI, Christoph Molnar, Martin Binder, and Bernd Bischl. Multi-objective counterfactual explanations. In International Conference on Parallel Problem Solving from Nature, pp. 448-469 Springer, 2020.
Pedro Domingos. Knowledge acquisition from examples via multiple models. In 14th International Conference on Machine Learning, pp. 98-106, 1997.
Ricardo Dominguez-Olmedo, Amir-Hossein Karimi, and Bernhard Schölkopf. On the adversarial robustness of causal algorithmic recourse. In International Conference on Machine Learning (ICML), 2022.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
Jerome H Friedman. Greedy function approximation: gradient boosting machine. Annals of statistics, pp. 1189-1232, 2001.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv:1503.02531, 2015.
Kaggle-Competitio. "give me some credit data 2011.
Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Model-agnostic counterfactual explanations for consequential decisions. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020a.
Amir-Hosseds Karimi, Julius Kügelgen, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse under imperfect causal knowledge: a probabilistic approach. In Conference on Neural Information Processing Systems (NeurIPS), 2020b.
10

---

Published as a conference paper at ICLR 2023
Thibault Laugel, Marie-Jeanne Lesot, Christophe Marsala, Xavier Renard, and Marcin Detyniecki. Inverse classification for comparison based interpretability in machine learning. arXiv preprint arXiv:1712.08443, 2017.
Ana Lucie, Harrie Oosterhuis, Hinda Haned, and Maarten de Rijke. Focus: Flexible optimizable counterfactual explanations for tree ensembles. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI); 2022.
Divyat Mahajan, Chenhao Tan, and Amit Sharma. Preserving causal constraints in counterfactual explanations for machine learning classifiers. arXiv preprint arXiv: 1912.03277, 2019.
Ramaravind K. Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*), 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. arXiv:1912.017000 2019.
Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. Learning model-agnostic counterfactual explanations for tabular data. In Proceedings of The Web Conference 2020 (WWW). ACM, 2020a.
Martin Pawelezyk, Klaus Broelemann, and Gjergji. Kasneci. On counterfactual explanations un- der predictive multiplicity. In Proceedings of the 36th Conference on Uncertainty Artificial Intelligence (UAI), pp. 809-818. PMLR, 2020b.
Martin Pawelczyk, Sascha Bielawski, Johan Van den Heuvel, Tobias Richter, and Gjergji Kasneci. Carla: A python library to benchmark algorithmic recourse and counterfactual explanation al- gorithms. In Advances Neural Information Processing Systems (NeurIPS) (Benchmark and Datasets Track), volume 34, 2021.
Martin Pawelczyk, Chirag Agarwal, Shalmali Joshi, Sohini Upadhyay, and Himabindu Lakkaraju. Exploring counterfactual explanations through the lens ofadversarial examples: A theoretical and empirical analysis. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
Martin Pawelczyk, Tobias Leemann, Asia Biega, and Gjergji Kasneci. On the Trade-Off between Actionable Explanations and the Right to be Forgotten. In International Conference on Learning Representations (ICLR), 2023.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-lear: Machine learning python. Journal of machine learning research, 2011.
Mary Phuong and Christoph Lampert. Towards understanding knowledge distillation, In International Conference Machine Learning (ICML). PMLR, 2019.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John C Duchi, and Percy Liang. Adversarial training can hurt generalization. arXiv preprint arXiv: 1906.00/900 2019.
Kaivalya Rawal and Himabindu Lakkaraju. Interpretable and interactive summaries ofactionable recourses. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
Kaivalya Rawal, Ece Kamar, and Himabindu Lakkaraju. Algorithmic recourse in the wild: Under- standing the impact of data and model shifts. arXiv:2012.11788, 2021.
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 (KDD), pp. 1135-1144, 2016.
Dylan Slack, Sophie Hilgard, Himabindu Lakkaraju, and Sameer Singh. Counterfactual explanations can be manipulated. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
11

---

Published as a conference paper at ICLR 2023
Thomas Spooner. Danial Dervovic, Jason Long, Jon Shepard, Jiahao Chen, and Daniele Magazzeni. Counterfactual explanations for arbitrary regression models. arXiv:2106.15212, 2021.
Gabriele Tolomei, Fabrizio Silvestri, Andrew Haines, and Mounia Lalmas. Interpretable predictions of tree-based ensembles via actionable feature tweaking. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD). ACM, 2017.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be odds with accuracy. arXiv preprint arXiv: /2/52, 2018.
Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorithmic recourse. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
Berk Ustun, Alexander Spangher, and Y. Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*), 2019.
Arnaud Van Looveren and Janis Klaise. Interpretable counterfactual explanations guided by proto-
types. arXiv preprint arXiv: 1907.02584, 2019.
Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning: A review. arXiv:2010.1000 10596, 2020.
Paul Voigt and Axel Von dem Bussche. The general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 10:3152676, 2017.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: automated decisions and the gdpr. Harvard Journal of Law Technology, 31(2), 2018.
12

---

Published as a conference paper at ICLR 2023
A EXTENSIONS TO OTHER NOISE DISTRIBUTIONS AND TREE BASED CLASSIFIERS
A.1 EXTENSIONS GENERAL NOISE DISTRIBUTIONS
A.1.1 A MONTE-CARLO APPROACH FOR GENERAL NOISE DISTRIBUTIONS
In section 4 we have introduced our PROBE framework, which enables us to guide the search for counterfactual explanations towards regions with a targeted low invalidation rate. Recall that the optimization procedure in Section 4 relied on a first-order approximation to the recourse in- validation rate under Gaussian distributed noisy human responses. In this section, we develop an algorithm that is agnostic the specifics of the parameterized noise distribution. To this end, we suggest Monte Carlo estimator of the recourse IR from Def. 1, i.e.
Algorithm 2 PROBE-MC
Input: f(x) < <
a,ar>> >
Init:: x' =x;
Compute (xc(x')
from
equation 11
while (MC > and f(x) do
Compute (x))
> from
equation 11
x' x
Vx Vx ,,,)) Opt. equation
end while Return: =
KK (1- 1-- 1x'+Ey +x))) K
ÂMC
(8)
A=1
We highlight that the estimator ÂMC allows for a flexible specification of various noise distributions, and thus does not depend specific distributional assumptions of ε. The following result suggests that we can estimate the IR A(x') desired precision using the Monte-Carlo estimator Âmc(x') (x').
The mean- laaaa-squaredernee error (MSE) between the true IR (xx) and the empirical Monte- Carlo estimate Amc(x') is upper bounded such that:
Proposition 5.
Eg [A((x)) - Âmc(x ()]] 4K
(9)
Since it is up to us to choose K, we can make the MSE arbitrarily small and reliably estimate the true invalidation rate A(x').
A.1.2 A DIFFERENTIABLE APPROXIMATION TO ÂMC
A problem with the estimator ÂMC is that it is not amenable to automatic differentiation re- quired for our gradient based algorithm to op- erate. This is due to the discontinuity at the threshold & introduced by the indicator function which, in turn, is applied to the logit score when computing the recourse invalidation rate (i.e., h(x) = [([(x) {) and see Definition 1). To mitigate this issue, we suggest to use a sigmoid function with appropriate temperature to ap- proximate the indicator at the threshold &
1.0
16
0.6
0.2
Figure 6: Differentiable approximations of the indi- cator function [[x:: > 0) using the sigmoid function S(y) Teexpl 9) evaluated at different tempera-
1 exp (x (10)
tures t E {1, 2, 10, 25, 100} when & = 0.
Therefore, oo the sigmoid S converges
to the indicator function [(x 2). We illustrate this behaviour in Figure 6 for different temperature levels ε 2,,2, 10, 25, 100) when the threshold is Ç Using the differentiable approximation the indicator function, we are now ready to state differentiable estimator for the recourse invalidation rate, which we can use to guide our gradient descent procedure to low recourse invalidation regions:
Σ 1 s(t(t f(x + =ew))
K
Á 0,t)
(11)
13

---

Published as a conference paper at ICLR 2023
A.2 EXTENSIONS TREE BASED CLASSIFIERS
The recourse literature commonly considers consequential decision problems which heavily rely on the usage of tabular data. For this data modality, ensembles of decision trees such as Random Forest (RF) (Breiman, 2001) or Gradient Boosted Boosted Decision Trees (GBDT) (Friedman, 2001) are considered among the state-of-the-art models (Borisov al., 2021). As consequence, some recourse methods were developed to find recourses for tree ensembles (Tolomei et al., 2017; Lucic et al., 2022) where the non- uon-differentiabliity prevents a direct application of the recourse objective in equation 1. To extend our method to tree-based classifiers, we also derive an IR expression for tree ensembles, and develop a method which computes low IR recourses for these models.
1.5
Zaxdon Fereet
Destad Tow
1.5
Beperade
1.5
Tappking Stes bniiedeeer
byua Mooes
10
Clas
14
Cane 0
10
1.0
-15
(a) Distilling a RF classifier (left) into a single tree (right). In the left panel, the RF classifier averages 30 decision trees, indicating that the final axis-aligned regions (not shown) complicated functions of all 30 decision trees.
(b) Computing recourse for the RF model (right) based on the hypercubes (left). The circle has radius 2ar, i.c., it shows the region where 95% of recourse inaccuracies fall when o² 0.025. The input has IR 0.5. The has IR 0.05.
Figure 7: Computing certified recourses on the 2d Moon data set (Pedregosa et al., 2011) for RF classifier. Figure a): Distilling a RF classifier (left panel) into a single decision tree (right panel) using knowledge distillation (Domingos, 1997). Figure b): Using the distilled tree, we form the hypercubes (left panel) required to compute IR according to Theorem 2. We then optimize equation to find certified recourses for the RF model (right panel).
Tree Ensemble Classifiers
An object of interest is the predicted output of a decision tree:
T(x) Σ cT(R) R).
(12)
RRT
where CT (R) 10 } is the constant prediction assigned in region R E RT for tree T. Moreover, decision forest is formed by a set of Mr decision trees, and forms the probabilistic output:
1 Mr Σ (x).
f (x)
(13)
MT
The predicted class of an input is formed via a vote by the trees where each tree assigns probability estimate to the input. That is, the predicted class is the one with highest mean probability estimate across the trees. After the trees combined, the multiple models form single model again (Domingos, 1997). Thus, the corresponding predicted class of equation 13 is given by:
F(x)= = Σ c=(R)) I)x,R),
(14)
RER
where cy cxR) {0, 1} is the constant prediction assigned in region R E Ry for the ensemble of trees F. Furthermore, note that for each ensemble, there is an active subset of ensemble- mnsemble-specific features SF S dd on which axis aligned splits took place. Finally, we note that this formulation is quite general as it subsumes a large class of popular tree-based models such as Random Forests (RF) and Gradient Boosted Decision Trees (GBDT).
A.3 THE RECOURSE IR FOR TREE ENSEMBLE CLASSIFIERS
Theorem 2 (IR for Tree-Enne Ensemble Classifiers). Consider the decision forest classifier in equation 14. The recourse invalidation rate under Gaussian distributed response inconsistencies e (N, T²T) is
14

---

Published as a conference paper at ICLR 2023
given by:
((EE 2)=
Σ
c5(R) π dg.(d
(15)
R
J6Sz
where
[ dg.((ān.)=
FE..
[j R
tES
②b
(16)
Jj
jj
and where 4 is the Gaussian CDE, Ej and I are the upper and lower points corresponding to feature j Sy that define the hypercube formed by region R.
Proof Sketch. The proof uses the insight that decision forest based on trees with axis-aligned splits partions the input space into hypercubes where the prediction is either O or 1. It then remains to evaluate Gaussian integrals subject to the constrains set by the hypercubes. The full proof is given in Appendix D.3.
Our proof of Theorem 2 assumed that the split points 15.1t and 5. corresponding to the tree-ensemble, are readily available. However, the hypereubes formed by the tree-ensemble, for which the prediction is constant, is function of all individual trees, and of how they are combined. Thus, the clear-cut division into hypecrubes present in each of the trees got lost the process of model averaging.
Model Distillation to Evaluate IR We suggest a solution this problem by using a technique called model distillation (Domingos, 1997; Bucilua et al., 2006; Hinton et al., 2015; Phuong & Lampert, 2019). In a nutshell: We wish to change the form of the model (to a simpler decision tree) while keeping the same knowledge (from our tree ensemble) (Hinton et al., 2015). Thus, the goal this technique is to distil the knowledge single, small (and interpretable) model. In case, the ensemble is formed by decision trees, and the target model a decision tree as well. Second, the method simple to operationalize: let be your complex model, and g denotes the simple model. Then we use our data (x;, y:). to train and validate the model h. The target model, however, is trained on samples from {x,, h(x;)))))))))))))( / to mimic the behaviour of the complex model. We refer to panels I to in Figure gain some intuition on how this technique works on a non-linear 2-dimensional data set.
larger model (possibly an ensemble) into a
B EXPERIMENTAL DETAILS
In this section, describe the hyperparameter choices and how the classification models were fitted. We have used CARLA's built-in funetionality to fit classifiers using PyTorch (Paszke et al., 2019) and treat all variables as continuous. We set Å₁ 2, A = 1 and search over A the usual way (Wachter et al., 2018). All models use a 80 20 train-test split for model training and evaluation. We evaluate model quality based on the model accuracy. All models are trained with the same architectures across the data sets:
Neural Network
Logistic Regression
Units Type
[Input dim., 50, 2]
[Input dim. 2] Fully connected N/A Softmax
Fully connected ReLU
Intermediate activations
Last layer activations
Softmax
Table 2: Classification model details
15

---

Published as a conference paper at ICLR 2023
Adult
COMPAS
Give Me Credit
Batch-size
NN
512
32
64
Logistic
512
32
64
Regression
Epochs
NN
50
40
30
Logistic
50
40
30
Regression
Learning rate
NN
0.002
0.002
0.001
Logistic
0.002
0.002
0.001
Regression
Table 3: Training details
Adult
COMPAS
Give Me Credit
Logistic Regression
0.83
0.84
0.92
Neural Network 0.85
0.85
0.93
Table Performance of models used for generating recourses
ADDITIONAL EXPERIMENTS
C.I ALGORITHMIC RECOURSE IN THE FACE OF NOISY HUMAN RESPONSES
In this Section show set of additional experiments. Since this work is the first to highlight and address the problem of recourse invalidation in the face of noisy human responses, we demonstrate in Figures and 9 that recourses generated by state-of-the-art approaches are, on average, invalidated up to 50% of the time when small changes are made to them. It is worth highlighting that the maximum invalidation scores can become as high as 61% %, which motivates the need for a recourse method that rightly controls the invalidation rate.
Adult
Compas
GMC
1,00
1.00
1.00
0.75
0.25
0.25
025
0.00
0.93
0.3
Wachiae
GS
DBCE
Kachiie
AX
Wactter
Explination
Explonatum Midacl
Explanatiom Madals
(a) o² 0.01
Adult
Compas
1.00
1,00
1.00
0.55
0.75
075
0.25
0.25
0.00
6000
0.00
Explination
Explarattan Modils
Explanation Madals
(b) o 0.025
Figure 8: Boxplots of recourse invalidation probabilities across sucessfully generated recourses X for logistic regression on three data sets. Recourses were generated by four different explanation methods (i.c.. AR, Wachter, and GS, DICE), which use different techniques (i.c.. integer programming, gradient search, random search, diverse recourse) to find minimum cost recourses. We perturbed the recourses by adding small normally distributed response inaccuracies N(O, 0² I) x.
16

---

Published as a conference paper at ICLR 2023
Adult
0.79
0.75
073
0.90
0.90
0.30
ARLLIME
Wadhic
GS
DICE
ARLLME
Wadiier
GB
DICE
ABLI
Wednee
DICE
Explinztion Model
Explaration Madel
Explanation Madel
0.01
Adult
Compas
GMC
Invaliiaalien
0.90
0.90
0.5
029
0.25
022
AR-LIMI
Wachie
GS
DKCT:
AB-UMI
Wachie
GS
I3C
ARLMM
CC Deplanation Madela
Wather
IKT
Explonatum Midell
Explanatum Midell
(b) o² 0.025
Figure 9: Boxplots of recourse invalidation probabilities across sucessfully generated recourses x for NN classifiers on three data sets. The recourses were generated by four different explanation methods (i.e.. AR, Wachter, and GS, DICE), which use different techniques (i.e., integer programming, gradient search, random search, diverse recourse) find minimum cost recourses. We perturbed the recourses by adding small normally distributed response inaccuracies e ~ NO, a² I) x.
C.2 MISSING FIGURES FROM THE MAIN TEXT
Below, we show the Figure that was missing from main text due to space constraints. keep plots below more readable, we have omitted DICE from them as both the bounds implied by DICE, the results on cost and the remaining measures are similar to the one by Wachter.
Compas
Invalidation Rate
1.00
Empirical IR
Theoretical Bound
0.75
0.50
0.25
0.00
AR-LIME
Wachter
DICE
ROAR
ARAR
PROBE
Recourse Methods
Logistic Regression
Compas
Invalidation Rate
1.00
0.75
0.50
0.25
Empirical IR
Theoretical Bound
0.00
AR-LIME
Wachter
GS
DICE
ROAR
ARAR
PROBE
Recourse Methods
(b) Neural Network
Figure 10: Missing figures from the main text (Compas).
17

---

Published as a conference paper at ICLR 2023
Adult
Invalidation Rate
1.00
Empirical IR
Theoretical Bound
0.75
0.50
0.25
0.00
PROBE
Recourse Methods
(a) Logistic Regression
Adult
Invalidation Rate
1.00
0.75
0.50
0.25
Empirical IR
Thcoretical Bound
0.00
AR-LIME
Wachter
DICE
ROAR
ARAR
PROBE
Recourse Methods
(b) Neural Network
Figure 11: Missing figures from the main text (Adult).
Adult
Recurss Metseds
Racouro Mechade
(a) Logistic Regression (Left), ANN (Right), 0.025
Compas
Compus
Thorndted Pareal
Theestaal
Wallin
BUALE
ARAA
ADADE
Recure Meinoda
DIC
200R
ABAR
PRCES
(b) Logistic Regression (Left), ANN (Right), o² 0.025
CMC
GMC
Theamtoo
ABAR
Rocauee Mecboda
(c) Logistic Regression (Left), ANN (Right), o² 0.025
Verifying the theoretical upper bound from Lemma for the logistic regression and artificial neural network classifiers on all data sets when r² = 0.025. The green boxplots show the empirical recourse IRs for AR (-LIME), Wachter, GS, and PROBE. The blue boxplots show the distribution of upper bounds, which we evaluated by plugging in the corresponding quantities (i.c., o², w, etc.) into the upper bound from Lemma 4. The results show no violations of our bounds.
Figure 12:
18

---

Published as a conference paper at ICLR 2023
Adali
Compo
CMC
A3
Nachtez
65
PRInE
AR.
Nachtez
65
FRODE
X3
Kachtez
65
FRODE
0.98
0.00-3.00
1.54004
0,62 0.43
2.6
2211
015-6.37
0.73
1025
029_0.27
1.4010.33
0.51
RA(1)
0.35
1.0
1.0
1.0
9.44
10
1.0
10
04
1.0
1.0
1.0
NN
AIR (2)
8.5 851-600
0.81
0.0
0.
0.5
6.22-.00
3.00
0264802
0.44-100
0.10..9
2.14 182
615-6.02
02.0.30
10-
02.016
6.31
Table 5: Recourse accuracy (RA), average recourse invalidation rate (AIR) for o² = 0.025 and average cost (AC) across different recourse methods. Recourses that use our framework PROBE are more robust compared to those produced by existing baselines. For PROBE, generated recourses by setting r = 0.35. Thus, the AIR should be at most 0.35, in line with our results.
C.3 VERIFYING THE VALIDITY OF THE EMPIRICAL. INVALIDATION RATE
In Figures 13, 14, and 15 show that the IRs of the recourses by framework be controlled setting to desired values.
3.45
045
Mazn Incuildation
Invaldation Uppo Tenget Viltac
Upper Trrget Velue
036
0.05
045
0.15
0.3)
0133
0.00
D03
015
0.23
C25
(C0
0.3
Invaliation Targes
Involitation Targeli
(a) LR
0.45
BJ5
Moan Incdisiaiion
Man Irvaldatoo
0.35
Upper Trrger Value
2.25
Upp Trige Wilee
035
0.75
2.5
6.15
023)
0.23
0.50
D23
0.20
0.2
0.33
Incalidtton Taegrr
Incelidation Bargeti
(b) NN
Figure 13: Verifying that the invalidation rate for our framework PROBE (blue line) is most equal to the invalidation target on the Adult data set for different o² (0.01. 0.025] across both classifiers. We compute the mean across every instance the test set. To do that, we sample 10,000 points from ~ (N, for every instance and compute IR in equation 2. Then the mean IR quantifies recourse robustness where the individual IRs are averaged over all instances from the test set. The shaded regions indicate the corresponding standard deviations.
C.4 DEMONSTRATING THE COST-ROBUSTNESS TRADEOFF
In Figures 16 and 17 we demonstrate that there exists a tradeoff between recourse costs and the robustness of recourse to noisy response.
C.5 DETAILED COMPARISON WITH ROAR AND ARAR
In this section we compare our method with two approaches that aim at generating robust algorithmic recourse in different settings. We further report results by DICE, which does not generate robust recourse. Thus, we PROBE the cost performance (i.e., AC) by DICE to serve lower bound, while its robustness performance would serve as an upper bound (i.e., AIR). Regarding the methods that suggest robust recourse refer to Upadhyay al. (2021) who proposed minimax objective to generate recourses that are robust to model updates (ROAR). while Dominguez-OInn Olmedo et al. (2022) use slight variation of this objective find recourses that are robust to uncertainty in the
19

---

Published as a conference paper at ICLR 2023
=000
125
0445
DA5
Mean Invoiiation
--- Moin Ervaldation
0.55
volue
0.35
Uppe Volne
Levalldaiione
0.5
0:25
0.15
0.15
216
D1B
Incalidttun Terge
Incalidaton Tanget
(a) LR
of
-003
-0.022
0.45
Mean Incolitation
Moon Inualdditio
0.55
tpper target
0.35
Upper tanger
0.25
0.23
0.35
0:15
026
806
Invalidation Taeget
Invalidation Target:
(b) NN
Figure 14: Verifying that the invalidation rate for our framework PROBE (blue line) is at most equal to the invalidation target r on the Compas data set for different o² {0.01, 0.025) across both classifiers. We compute the mean IR across every instance in the test set. To do that, we sample 10,000 points from ~ NN, for every instance and compute IR in equation 2. Then the mean IR quantifies recourse robustness where the individual IRs are averaged over all instances from the test set. The shaded regions indicate the corresponding standard deviations.
-0.01
025
0.45
DJ5
Moan Invoiiitiion
Moin Invaldation
0.35
larget Valua
0.36
Voloer
0.25
0:25
035
015
216
Incalidtunn Terger
Incalidatio Eonpet
(a) LR
ef -001
-0.025
Mean Incoliatiion
Moon Enutadattion
0.55
tpper Torget
Emealilation Rate
0:35
Utpe Trnger
Emalidatinn
0.25
0.25
0.35
015
226
806
Invalidatun Target
Incalidaton Target:
(b) NN
Figure 15: Verifying that the invalidation rate for our framework PROSE (blue line) is at most equal to the invalidation target r on the GMC data set for different o² {0.01, 0.025) across both classifiers. We compute the mean IR across every instance in the test set. To do that, we sample 10,000 points from N NOO, I² for every instance and compute IR in equation Then the mean IR quantifies recourse robustness where the individual IRs are averaged over all instances from the test set. The shaded regions indicate the corresponding standard deviations.
inputs (ARAR). Moreover, on a high-level, these objectives differ from our approach since the epsilon neighborhoods that PROBE constructs are probabilistic.
20

---

Published as a conference paper at ICLR 2023
Corrpo
Mer
1.5
0.5
0.35
Tegget
Figure 16: Trading off recourse costs against robustness by choosing the invalidation target r in our PROBE framework. We generated recourses by setting r e {0.20, 0.25, 0.30, 0.35.0.40) and a² = 0.01 for the logistic regression classifier.
21
Adull
21
Corpos
21
GMC
Col
1.5
033
375
0M
316
030
0.55
0.8
0.55
6.00
0.55
035
Invillattion Tanget
Insillation Tegeet
Inraldation Bager:
Figure 17: Trading off recourse costs against robustness by choosing the invalidation target r in our PROBE framework. We generated recourses by setting r {0.20, 0.25, 0.30, 0.35.0.40) and x² = 0.01 for the NN classifier.
Cost versus invalidation rate performances. The table shown below summarizes the performance comparison across the aforementioned methods, and Figures 18 and 19 provide Pareto plots, which demonstrate the tradeoff between the average costs measured in terms & norm and the average invalidation rate.
Discussion. The AIR for PROBE should be at most 0.35, in line with our results. For ARAR and ROAR, we should expect AIRs close to O, which only the case for the linear classifiers. Additionally, ARAR and ROAR provide recourses with up to 10 times higher cost relative our method PROBE. Note also that ARAR and ROAR have trouble finding recourses for non-linear classifiers, resulting in RA scores of around 5% in the worst case, while not being able to maintain low invalidation scores. This is likely due to the local linear approximation that needs to be used by these methods. For ARAR, only up to 5 percent of all recourse boundary), and for those identified recourses the average invalidation rate is close to random coin flip. In summary, PROBE. finds recourses for 100% of the test instances in line with the promise of having an invalidation probability of at most 0.35, while being substantially less costly than ROAR.
found (i.e., it only finds recourse with low cost to the decision
Adult
Compus
GMC
Mensures
ROAR
ARAR
PROBE
ROAR
ARAR
PROBE
ROAR
ARAR
PROBE
RA(1)
IR
AIR (1)
0.0
0.02 a 0.01
0.34 0.02
0.0 0.0
0.0
0.33 4 0.02
0.0 (.0
0.35 0.01
0.24 0.01
(1)
3.5
2.68 0.79
1.56 0.92
2.99 0.31
1.74
0.63 0.39
1.74 0.45
0.60 + 0.56
RA(1)
0.03
0.97
NN
AIR (1)
0.
0.51 a 0.0
0.35 0.01
0.01 + 0.06
0.46 = 0.0
0.333 + 0.02
0.3 4 0.21
0.45 0.01
0.25 + 0.03
(1)
3.39
0.01 0.0
1.43
6.41 1.07
0.12
0.33
0.67 0.91
0.02
0.47 + 0.21
Table 6: Recourse accuracy (RA), average recourse invalidation rate (AIR) for の² = 0.01 and average cost (AC) across different recourse methods. Recourses that use our framework FROBE provide a strong recourse-robustness tradeoff. For PROBE, we generated recourses by setting r = 0.35, 2² 0.01. For ROAR and ARAR, we generated recourses by setting & 0.01.
21

---

Published as a conference paper at ICLR 2023
Compas
GMC
Adult
Inv-alideti Iecliddttion Rate
Invalidation
0.3
Invafidation
82
0.
05
1.5
10
188
30
Costs (Ei)
Costs (Ei)
Costs (E1)
11000I (1-0300
PREEE (2-23))
PROCI (K-22)
ARAIL - ROAK
Figure 18: Pareto plots showing the tradeoff between average costs and average invalidation rate when the underlying model is linear. For PROBE, the invalidation target r (dotted line) is set to 0.3, and generated recourses by setting a² {0.005, 0.01, 0.015). and for ARAR and ROAR we set c e {0.005, 0.01.0.015) 0.015). Following the suggestion by Upadhyay et al. (2021), all re- course methods search for the optimal counterfactuals over the same set of balance parameters À e (0. 0.25. 0.5. 0.75. 1}.
Compas
GMC
Adult
Invalidation
03
Invalidation 12
Invalidation
22
21
Costs (F1)
Costs (f1)
Costs (Fi)
PRUSI (7.03))
PROIU (n-02)
ARAII
ROAR
Figure 19: Pareto plots showing the tradeoff between average costs and average invalidation rate when the underlying model is neural network. For PROBE, the invalidation target r (dooted line) is set to 0.35, and generated recourses by setting o² e (0.005, 0.01, 0.015). and for ARAR and ROAR we set E {0.005, 0.01, 0.015). Following the suggestion by Upadhyay et al. (2021), recourse methods search for the optimal counterfactuals over the same set of balance parameters Ae {0, (0,0.25,00 0.5, 0.75, 1}.
D PROOFS
D.1 PROOF OF PROPOSITION 5
Proposition 5. The mean-squared-error (MSE) between the true IR A(x') and the empirical Monte- Carlo estimate Âmc(x') is upper bounded such that:
Er
- (((Axx))~u((xx)))
(17)
4K
Proof. First, recall that the empirical Monte-Carlo estimator is given by:
K ÂMC (1- +ex)).
(18)
K k-1
Next, note Ea[1 - h(x' + +)] A(x'). Further, the mean-squared error between the nominal invalidation rate A(x') and the Monte-Cate estimate Âmc is given by:
E (A(x')) ÂMC) )] V. (AM))) E - A(x')²²,
(19)
which gives the harianai decomposition. We first compute the squared bias term:
Es - 2
1--EE[1-1 K- h(x =)]-
(20)
K
0,
(21)
where have used that the es are identically distributed. We now turn to the variance term for which we find the following expression:
1
Ve (AMC)= K2
K. WV/elll-e -(x++((++++++)-
K Ve[h(x+ s)].
(22)
22

---

Published as a conference paper at ICLR 2023
It remains to identify upper bound for Ve(h(x E)). Since h(x+ E) is binary, simple upper bound is given by:
Ve(h(x + E)) s 4"
(23)
Combining the expression for the squared bias and the upper bound on the variance yields the desired result.
D.2 PROOFS THEOREM 1, PROPOSITIONS AND COROLLARY
Theorem 1. A firt-order approximation å to the recourse invalidation rate A in equation 2 under Gaussian distribution E -N, capturing the noise in human responses is given by:
( f(Xg)
i(*;; Σ) 1
(24)
( EV f f(XE)
where & is the CDF of the univariate standard normal distribution (0, 1), f(xg) denotes the logit score at kg which is the recourse output by a recourse method E, and h(&g) E 10.
Proof. Let the random variable e follow a multivariate normal distribution, i.e., E (1s, Σ) The following result a well-known fact: v E ~ -V μ. vΣv") where v IRd, Let x denote the input sample for which we wish to find counterfactual Xg ōg. Recall from Definition 1 that have to evaluate:
Eg
h(xx)- - h(xE +)
(25)
CE class
class after response
1 Eg [x(8 +
where we have used that the first term a constant and evaluates 1 by the definition of counterfactual explanation. It remains evaluate the expectation: Eg [<[AE>>> + e) Next, we note that equation 25 can equivalently be expressed in terms of the logit outcomes:
A Eg [{{({))>)) > -
[[f(xE + E) >>>>>> 0]
[I- + >0]] -
(26)
CE class
class after perturbation
Again, interested in the second term, which evaluates
E- [<[ + +E)> o]] =0 0- f(x (0 +
1.1P f(xx [(x=+))20)
(27)
Next, consider the first-order Taylor approximation: f(xg + v f(Et) (x(x)) E. Hence, we know fx approximately follows (O (f EV (xE(E)) computed as follows:
NNw, the second term can be
P + +e) > s(x)) -V((E)
=P ((XE))V[((>)))
(28)
P
- -(xE) > V
(29)
[(xx)
/v[(x)) EV [V((EE)
[vS(xx)' (V [VS(F))
Mean Gaussian RV
Constant
f(xg)
Vf(EE) EV EV((EE
f(xg)
(30)
( EV (*x))
23

---

Published as a conference paper at ICLR 2023
where the last line follows due symmetry of the standard normal distribution (i.e., o
(u)).. Putting the pieces together, we have:
Ee[iff(E x) o]] =0 P
f(x +2)
<0 {(x=+)<<0)))
1.P f(xE +))
(31)
f(KE)
(32)
EV
Thus, we have:
f(xg)
A Á
(33)
V V (xx) VVV f(x))
which completes our proof. Note that this is equivalent to P [(EE + E) < <0). and thus
"counting" how often perturbations to ng sampled from .V, result in flips back to the undesired class.
Proposition 2. For linear classifier, let 1) and let Rg x Ög be the output produced by some recourse method É such that h(*g) = 1. Then the cost required to achieve a fixed invalidation target is given by:
|0 (1-
(34)
where == x-(Vf(x)lz is a constant, and is the cosine of the angle between the vectors fx) and ög.
f(x)
Proof. Under a logistic classifier, the result immediately follows by setting the expression from Theorem equal to r, using the identity fx(x) 0g w. (v)(x)l2 [8øl|2 where w is the cosine of the angle between the vectors V fx) and åg. and rearranging for |
Proposition 3. Under the same conditions as in Proposition 2, we have 06 a(1-)) o (1-r) > 0,
i.e., an infinitesimal increase in robustness (i.e.,1 - T) increases the cost of recourse by Φ (1-r)
Proof. We will compute the derivative of |6g|2 =- (1--) -c)) with respect 1 and show that it is positive for all (0, 1):
0
> >0
(35)
0 (1-r) r) W (( 100-1(1-1)) (1-r)
where @ is the probability density function (PDF) of the standard Gaussian distribution. Since the PDF must be positive, we have that o( h ((-r((1))) > 0, and we know that a,, > 0. Thus, the results follows.
Proposition 4. Let XE be the output produced by some recourse method É such that h h(xg) 1. Then, an upper bound on Å from equation is given by:
A(X;; o o01 s T ct
w [v)(2) |
(36)
[v](x)) V
f(x) where c= ox]v a constant, 8g = kg - x, and w > is the cosine of the angle between the
vectors V fx) and dg.
Proof. We start by noting the following basic inequality:
|z//2 / Vlllooo 2z|2-
24

---

Published as a conference paper at ICLR 2023
Going forward, will refer to these inequalities basic inequalities. Moreover, note that Ob is monotonic function. Thus, we have ((a)= S ((a') for a a'. Note that f(xz) N f(x) + fx)) gg.
Thus obtain the following approximation:
f(x) V[
=
(37)
[V((E)
Next, we will find upper bounds for the term the right: Before will do that, we will express the above expression more conveniently to highlight the impact of the counterfactual action óg more explicitly. To do that, note that V f Tō w- || fx) (2- 1102222 where w is the cosine of the angle between the vectors V f(() and og. Using E II, we obtain:
①b f(x) Vf(x) 8g
[Vf(x)]l2 w
1 c+
[f(x)))l -00111
(38)
where we defined constant <|V\/(x=]12 using quantities that will keep fixed in analysis, namely x, fx)) and a. Also note that x the factual input, and thus its logit score satisfies:
f(x)
f(x) < O. Since óg is valid perturbation, must have that 0 for the perturbation to change the class prediction.
Note that the following lower bound holds by the basic inequality stated above: w o | 2 Φ
[V](x)
[v](x)22 w 1ō
c+
(39)
vf(x))l2
[v](x))lz V18mlo
As consequence obtain the following upper bound the IR:
[Vf(x)l2 w. |8
Â s 1 c+
(40)
[f((x)]l2 a Víōgllo
as claimed.
Proposition 1. For the logistic regression classifier, consider the recourse output by Wachter et al. x- f=f(x)
(2018): &aacher (s) x
fxx). Then the recourse invalidation rate has the following
clomed-form:
(XXWacheer (s 11-1 (1) (o]lV](x)
(41)
where s is the target logit score.
Proof. Since we are in the linear case, we have: vx(xg) vf(x). Also, note that f(xg)
f(x) + ( 8g. Using Σ II, obtain the following exact expression:
A=1- f(x)+ (
(42)
xlvʃ(x)]1
From Pawelezyk et (2022), we have:
fx)
ô Waahter
[ fx(x).
(43)
Plugging equation 43 into equation 42 we obtain:
f(x) + vf(x) 55
1 +
(44)
xlV]((x]12 fllv
f(x)
8-
fxx
1 T
vf(x)
xlVx(x))l dx)v
f(x) 8- sx)
1 +
dlvf(x)l1 2
fllv
= +b
(45)
xlVs(x)]2
which concludes the proof.
25

---

Published as a conference paper at ICLR 2023
Corollary 1. Under the conditions of Proposition 1, choosing 8, =, -== guarantees a recourse invalidation rate of r. i.e., A Waachee 8,) I²
Proof. The result directly follows from plugging in s, 12 into the optimal recourse from Wachter from equation 43 and subsequently evaluating the recourse invalidation rate from equation
D.3 PROOF OF THEOREM 2
Proof. From Definition we know:
Forest
Egg F(xg) F(Xg + E)
(46)
class
class after response
1 Es [FxE +
(47)
remains to evaluate: Ee FXx + =
Using equation 14, we have:
Eg [((EE + E)] Ee
Σ
cx(R) I(xx + E R)
(48)
RER
Σ
c=(R)
E. [(xx tEE R)]
(Linearity of Expectation)
RERS
Σ cF(R). SR ply)dy
(p(y) = =N ~X{F,; o
1 (リı E )2
Σ c=(R)
exp
dys
R
jeSy R2 2To
2 of
(Since is independent Gaussian)
[ tE
G FE.
Σ
C=(R)
π
①b
R
joSs
Jj
Jj (Since is Gaussian)
Using our Definition of robustness, have
jj ēEJ
YR IE.
! Forest 1
Σ
cF(R)
II
+
(49)
ReR,
jeSx
0
0
which completes the proof.
26


Reviews:
[{"review_id": "Z2mwgtS0kz", "reviewer": "Reviewer_fDb4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "This work proposes a probabilistic framework for navigating the trade-off between cost and robustness in algorithmic recourse. More concretely, given a user-specified recourse invalidation rate, a loss function accounting for the invalidation rate, target score, and cost is minimized to find the suggested recourse. One challenge that arises when pursuing this approach is that a naive Monte Carlo approximation of the invalidation rate is non-differentiable. This is circumvented by taking a first-order approximation of the invalidation rate, which has a differentiable closed-form expression. The cost required to achieve a given invalidation rate is derived using this expression. Finally, an upper bound on the (approximate) invalidation rate is derived. The proposed approach is evaluated empirically across various real-world data sets, demonstrating its ability to find better points across the cost-invalidation rate Pareto front than existing approaches.", "summary_of_the_review": "This work proposes a framework for navigating the trade-off between cost and robustness in algorithmic recourse, a problem that is practically relevant and has not been addressed before. The proposed approach is technically sound. However, I have some concerns about its ability to explore this trade-off fully. Overall this paper is well executed. However, the technical novelty it provides seems limited. I am open to changing my score after the authors' rebuttal and discussion with my fellow reviewers.", "strength_and_weaknesses": "Strengths:\n1. The problem tackled by this problem is practically relevant and, to my knowledge, has not been addressed before.\n2. The proposed approach is technically sound overall.\n3. This paper is very well-written and easy to follow.\n4. The code the reproduce the experiments is available.\n\nWeaknesses: \n1. My main concern with the proposed approach is its ability to thoroughly explore the cost-invalidation rate Pareto front. From a multi-objective optimization perspective, this work proposes to use a particular scalarization. However, it is unclear if the entire Pareto front can be recovered by tweaking the parameters of this scalarization. I would like the authors to discuss this.\n2. I am not very familiar with the related literature, but the proposed approach seems to have little technical novelty.\n3. Is there any guidance to choose $\\lambda$ in practice? For example, how is $\\lambda$ set in the experiments described in Table 1?\n4. Noise in the empirical evaluation seems to be very low ($\\sigma^2 = 0.01$). How was this value chosen? The effect of the noise should be investigated more thoroughly. \n\nOther minor comments:\n1. The domain of $d_c$ should be $\\mathbb{R}^d\\times \\mathbb{R}^d$ instead of $\\mathbb{R}^d$.\n2. In the following line, \"...is the recourse invalidation rate from equation 1\", \"equation 1\" should be \"equation 2\".", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ot8onlcksJP", "reviewer": "Reviewer_ifQy", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "summary_of_the_paper": "In this paper, the authors give a framework, called PROBE (Probabilistically Robust Recourse), to address the problem of providing low cost recourse that is also robust. Prior work in this context focused on either achieving low recourse costs, that led to mechanisms that were very sensitive to input perturbations or small shifts in the prediction model considered; or mechanisms that were highly robust, but incur high recourse costs. Further, in real life, recourse mechanisms are implemented noisily, thus, there is a need to manage the trade-offs between recourse cost and robustness effectively. The authors address the latter in this paper. Towards this, they define the notion of invalidation rate (IR), which denotes the probability with which a recourse gets invalidated due to small changes in the recourse arising due to human error. A threshold for IR is chosen by users to navigate trade offs between cost and robustness. The authors propose a new objective, that adds a Hinge loss term along with the standard objective function to ensure that the output recourse has a low probability of being invalidated. The main algorithm proposed essentially performs a gradient descent, while considering an approximation to the value of IR at each time step. The authors also give general upper bounds for the value of IR given any recourse method. Finally, an extensive empirical analysis is performed, comparing costs and IR for PROBE and other existing frameworks. ", "summary_of_the_review": "Overall, I believe the contributions of this work are interesting to the Algorithmic Recourse community. The proposed framework is simple, cost effective, and powerful in terms of allowing users to choose the trade off parameter r. Following are a few line-by-line comments.\n\nMinor Comments:\n- Page 3: para 2, end of line 5: should be minimax\n- Page 3: equation (1), remove extra ‘)’ in term 1 of rhs\n- Page 4: equation (3), should it be R(x’; r , \\sigma^2 I)? Also, remove extra ‘)’ in the second term.\n- Page 4: last para, line 3, a output -> an output\n- Page 5: Sec 4.2 para 1, line 5, Section not referenced\n- Page 9: para 1, line 2, recousre -> recourse\n", "strength_and_weaknesses": "Strengths:\nThe main contribution of this paper is the notion of IR and how to find a good approximation to it efficiently; and the modified objective function to incorporate IR such that the output recourse not only has low cost but also low invalidation probability. I believe IR and the modified objective are of interest for developing low-cost robust recourse mechanisms. The extensive experimental results support the claims of the paper well.\n\nWeaknesses:\n1) How were the r values chosen for each dataset? A small description of this would be useful.\n2) Are there any convergence guarantees for PROBE? Is it guaranteed that the IR will be less than r eventually?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "K4c_knC5GQ", "reviewer": "Reviewer_WYC5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "1. The paper proposed a new user-driven algorithmic framework PROBE (Probabilistically Robust Recourse) that tackles two independently well-studied challenges in algorithmic recourse  -- (1) recourse cost, and (2) robustness under noisy human implementation. This is the first study where both recourse cost and robustness are simultaneously optimized. \n\n2. PROBE enables the end users to navigate the tradeoffs between recourse cost and robustness via an input parameter $r$ which is a user-defined upper-bound on the invalidation rate i.e., recourse can be invalidated at most $r$ percent of the time. Note that $r=1$ corresponds to high-risk and low recourse cost and $r=0$ is low-risk and high-cost recourse. \n\n3. The main contributions of this paper are (i) the definition of the recourse invalidation rate (IR) in Definition 1 and Equation (2) (ii) approximating the invalidation rates of any given instance w.r.t different underlying prediction models like linear models, non-linear models and tree-based models, etc. Thus, the paper efficiently implements the PROBE algorithm (1) using the closed form of approximated invalidation rates (Theorem 1). \n\n4. There are an extensive set of experiments conducted on multiple datasets comparing PROBE to existing algorithms that minimize recourse cost (Watcher, AR-LIME, DICE, and GS -- Figure 5) and robust algorithms (ROAR, ARAR - Figure 5). Their empirical evaluation using well-defined measures like \"recourse accuracy (RA)\", \"average recourse invalidation rate (AIR)\" and \"average cost (AC)\" show that PROBE generated recourses that are more robust than existing baselines (Table 1). Further, the empirical evaluation supported the theoretical upper bounds on IR in Proposition 3.  \n\n", "summary_of_the_review": "I believe the paper has studied an important problem and made strong technical contributions. The empirical evaluation is extensive and the results are inline with the theoretical analysis. The presentation of the paper in my opinion can be improved to help readability. ", "strength_and_weaknesses": "Strengths : \n1. The area of algorithmic recourse has a great impact and is an important problem to study. The current work addresses an important problem of managing the trade-off between two highly desired objectives (recourse cost and robustness). \n2. The definition of invalidation rate is characterized in a closed-form such that PROBE can be efficiently implemented. \n3. The empirical evaluation on multiple datasets showed no violation with the theoretical guarantees provided (Figure 5 and Proposition 3)\n\n\nWeaknesses : \n1. The convergence of the algorithm PROBE is not discussed. Since the optimization of the objective in Equation (3) in PROBE as discussed is being done via gradient descent, it would be interesting to compare the convergence of PROBE with existing baselines.\n2. The presentation of the paper can be improved in various places like (1) Referencing the proofs in the main paper. (2) Outline the additional experiment results in the appendix.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "2T2pILV4jr", "reviewer": "Reviewer_Fd93", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "The paper considers a model for providing counterfactual explanations that are both easily attainable (i.e., have low cost) and robust (i.e. if the recourse action is not implemented exactly - in other words is noisy - then the output will most likely not change). Due to a natural trade-off between these two criteria, prior work only considers optimizing one at the expense of the other. To my understanding, this paper gives the first result combining both in a controllable way. \n\nThe theoretical results of this paper are also accompanied by a validating suite of experiments.", "summary_of_the_review": "The proposed model and results seem like a interesting contribution to a practical problem. However, the clarity of the writing does not allow me to give a higher score, since I cannot really grasp some of the vital theoretical results of the paper.", "strength_and_weaknesses": "Strengths:\n\n1) The newly introduced model appears to be a very natural way to combine the two goals, i.e., low cost and robustness.\n2) The experiments seem validating enough.\n\nWeaknesses:\n\n1) The clarity in the presentation of the theoretical results is poor. In particular, Section 4.2 is very confusing. Upon reading the earlier sections, I was expecting a theorem that would clearly present the achieved algorithmic trade-off between the confidence parameter r and the cost of the counterfactual. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster