Distributionally Robust Recourse Action
Authors: Duy Nguyen
Ngoc Bui
Viet Anh Nguyen
Venue: ICLR 2022 Submitted (2022)
Keywords: Algorithmic recourse
Robust optimization

Abstract: Recourse actions, also known as counterfactual explanations, aim to explain a particular algorithmic decision by showing one or multiple ways in which the instance could be modified to receive an alternate outcome. Existing recourse recommendations often assume that the machine learning models do not change over time. However, this assumption does not always hold in practice because of data distribution shifts, and in this case, the recourse actions may become invalid. To redress this shortcoming, we propose the Distributionally Robust Recourse Action framework, which generates a recourse action that has high probability of being valid under a mixture of model shifts. We show that the robust recourse can be found efficiently using a projected gradient descent algorithm and we discuss several extensions of our framework. Numerical experiments with both synthetic and real-world datasets demonstrate the benefits of our proposed framework.

Under review as a conference paper at ICLR 2022
DISTRIBUTIONALLY ROBUST RECOURSE ACTION
Anonymous authors Paper under double-blind review
ABSTRACT
Recourse actions aim to explain a particular algorithmic decision by showing one multiple ways in which the instance could be modified to receive an alter- nate outcome. Existing recourse recommendations often assume that the machine learning models do not change over time. However, this assumption does not always hold practice because of data distribution shifts, and in this case, the re- course actions may become invalid. To redress this shortcoming, we propose the Distributionally Robust Recourse Action framework, which generates a recourse action that has high probability of being valid under mixture of model shifts. We show that the robust recourse can be found efficiently using projected gradient descent algorithm and we discuss several extensions our framework. Numerical experiments with both synthetic and real-worke datasets demonstrate the benefits of our proposed framework.
INTRODUCTION
Post-hoc explanations of machine learning models are useful for understanding and making reliable predictions in consequential domains such loan approvals, college admission and healthcare. Recently, recourse is rising as an attractive tool do diagnose why the machine learning models have made particular decision for a given instance. Recourse work by providing possible actions to modify given instance to receive an alternate decision (Ustun et 2019). Consider, for example, the case of loan approvals which a credit application is rejected. The counterfactual will offer the reasons for rejection by showing what the application package should have been to get approved. A concrete example
counterfactual in this case may be "the monthly salary should higher by $500" "20% of the current debt should be reduced"".
Recourses have a positive, lorkiig-looking meaning: they list out the recourse actions that a person should implement so that they can get more favorable outcome in the future. If a specific applica- tion can provide the negative outcomes with recourse actions, it can improve the user engagement and boost the interpretability at the same time (Ustun et al.) 2019 Karimi et al.] [202T) Explanations thus play a central role in the future development of human-centric machine learning.
Despite its attractiveness, providing recourse for the negative instances is not trivial task. For real- world implementation, designing a recourse needs to strike an intricate balance between conflicting criteria. First and foremost, recourse action should be feasible: if the prescribed action taken, then the prediction of a machine learning model should be flipped. At the same time, a framework for generating recourse should minimize the cost take recourse actions to avoid making drastic change to the characteristics of the input instance. An algorithm for finding recourse must make change to only features that are actionable. and should leave immutable features (relatively) un- changed. For example, we must consider date of birth an immutable feature; in contrast, we can consider salary or debt amount as actionable features.
Various solutions has been proposed to provide recourses for a model prediction (Karimi et al.) 2021 Stepin et al. [202 Artelt & Hammer 2019). For instance, [stun et al. (2019) used an integer programming approach to obtain actionable recourses, and also provide feasibility guarantee for linear models. Karimi et al. (2000) proposed model-agnostic approach to generate nearest coun- terfactual explanations and focus structured data. Dandl et al. (020) proposed method which finds counterfactual by solving a multi objti--beecctive optimization problem. Recently, [ussell (2019) and Mothilal et al. (2020) focus finding set of multiple diverse recourse actions, where the

---

Under review as a conference paper at ICLR 2022
diversity is imposed by mule-based approach or by internalize determinant point process cost in the objective function.
These aforementioned approaches make fundamental assumption that the machine learning model does not change over time. However, the dire reality suggests that this assumption rarely holds. In fact, data shifts so common nowadays in machine learning that they have sparkled the emerg- ing field of domain generalization and domain adaptation. Organizations usually retrain models as a response to data shifts and this induces corresponding shifts in the machine learning models parameters, which in turns cause serious concerns for the feasibility of the recourse action in the future (Rawal et al., 202T). In fact, all of the aforementioned approaches design the action which is feasible only with the current model parameters, and they provide no feasibility guarantee for the future parameters. If a recourse action fails to generate a favorable outcome the future, then the recourse action may become less beneficial \Venkatasubramanian & Alfano 2020), the pledge of a brighter outcome is shattered, and the trust on the machine learning system is lost (Rudin) 2019]
Ribeiro et al. 2016).
To tackle this challenge, Upadhyay et al. (2021) proposed ROAR, a framework for generating in- stance level recourses (counterfactual explanations) that are robust to shifts in the underlying pre- dictive model. ROAR used a robust optimization approach that hedges against an uncertainty set containing plausible values of the future model parameters. However, it is well-know that ro- bust optimization solutions can be overly conservative hecause they may hedge against patholog- ical parameter in the uncertainty set. A promising approach that can promote robustness, while at the same time prevent from over-conservatism is the distributionally robust optimization frame- work (El Ghaoui et al., 2003 Delage & Ye, 2010: Rahimian & Mehrotral 2019 Bertsimas et al.) 2018). This framework models the future model parameters as random variables whose underlying distribution is unknown, but is likely to be contained in an ambiguity set. The solution is designed to counter the worst-case distribution in the ambiguity set in min-max sense. Distributionally robust optimization is also gaining popularity in many estimation and prediction tasks in machine learning (Namkoong & Duchi 2017 Kuhn et al. (219))
Contributions. This paper combines ideas and techniques from two principal branches of explain- able artificial intelligence: counterfactual explanations and robustness, in order to resolve the re- course problem under uncertainty. Concretely, our main contributions are the following:
1.
We propose the framework of Distributionally Robust Recourse Action (DiRRAc) for designing a recourse action that is robust to mixture shifts of the model parameters. Our DiRRAc maxi- mizes the probability that the action is feasible with respect to a mixture shift of model parame- ters, while at the same time cap the action in the neighborhood of the input instance. Moreover, the DiRRAc model also hedges against the misspecification of the nominal distribution using a min-max form with mixture ambiguity set prescribed by moment information.
2. We reformulate the DiRRAc problem into a miiee-dimnnsionll optimization problem with an explicit objective function. We also provide a projected gradient descent to solve the resulting reformulation with convergence guarantees.
3. We extend our DiRRAc framework along several axis to handle mixture weight uncertainty, to minimize the worst-case component probability of receiving unfavorable outcome, and also to inject the Gaussian parametric information.
We first describe the recourse action problem with mixture shift in Section In Section 3 we present our proposed DiRRAc framework, its reformulation and the numerical routine for solving it. The extension to the parametric Gaussian setting will be subsequently discussed in Section Section reeports the numerical experiments showing the benefits of the DiRRAc framework and its extensions.
Notations. For each integer K, we have [K] {1....,.), We use Sq. (S denote the space of symmetric positive semidefinite (definite, respectively) matrices. For any A E mm the trace operator defined as Tr [A] = Σ' Ar.. We write Q+ (HR, Ex) to denote that the distribution Qe has mean vector μ4 and covariance matrix Σg. If additionally Qe is Gaussian, we write Qs A (14, Σt). With a slight abuse of notation, Q ~ (Qu, Pk ]e[[K] means Q is a mixture of K component distributions, the k-th component has weight Pk and distribution Q
2

---

Under review as a conference paper at ICLR 2022
2 RECOURSE ACTION UNDER MIXTURE SHIFTS
We consider binary classification setting with label y {0. 1}. where represents the unfavorable outcome while 1 denotes the favorable one. The covariate space is IR and any linear classifier Ca IR + characterized by the d-dimensional parameter of the form
Co(x)= - {
0 O,
otherwise.
Note that the bias term can internalized into by adding an extra dimension, and thus is omitted.
Suppose that at this moment (l = 0), the current classifier is parametrized by O.. and we are given an imput instance zo E gd with unfavorable outcome, that is, Ca, (zo) = O. One period time from now (t 1), the parameters of the predictive model will change stochastically, and are represented by d-dimensional random vector 0. This paper focuses finding recourse action which is reasonably close to the instance 20, and at the same time, has a high probability of receiving a favorable outcome in the future. Figure I gives bird's eye view of the setup
Now
Future
Time
Current classifier:
0g
Future classifier: 0~ (8e, Ex Pa)ke
Input: 2o with Co,, (xo) =
Counterfactual:
x
Figure 1: A canonical setup of the recourse action under mixture shifts problem.
To measure the closeness between the action and the input zo, assume that the covariate space endowed with a non-negative, continuous cost function In addition, suppose temporarily that follows distribution P. Because maximizing the probability of the favorable outcome is equivalent to minimizing the probability of the unfavorable outcome, the recourse can be found by solving
min P(Cg(z) 0)
S. t.
x E X, 2o) s
The parameter 8 0 in governs how far recourse action be from the input instance zo- Note that we constrain æ in a set X which captures operational constraints, for example, the highest education of a credit applicant should not be decreasing over time.
In this paper, model the random vector ê using finite mixture of distributions with K com- ponents, the mixture weights are p satisfying Σee(k] Pk = 1. Each component in the mixture represents one specific type of data shifts: the weights 5 reflect the proportion of the shift types while the component distribution Fs representing the (conditional) distribution of the future model parameters in the k-th shift. Further information on mixture distributions and their applications in machine learning can be found in Murphy (2012) $3.5).
If each P& is Gaussian distribution A (O,, Ex), then IP is mixture of Gaussian distributions. The objective of problem can be expressed as
0
[(C)(z)= = 0) Σ (c) kE[K]
Σ P
kE[K]
E
where the first equality follows from the law of conditional probability, and & is the cumulative distribution function a standard Gaussian distribution. Under the Gaussian assumption, we can solve (Tree[[Tssing using a projected gradient descent type of algorithm (Boyd & Vandenberghe, 2004).
Remark 2.1 (Nonlinear models). Our analysis focuses on linear classifiers, which common setup in the literature (Upadhyay al. 2021 Ustun et al. 2019 Rawal et al.) 2021 Karimi et al. 2020 Wachter et al. 2018 Ribeiro et al. (016). To extend to nonlinear classifiers. we can follow similar approach in Rawal & Lakkaraju (2020) and Upadhyay et al. (2027) by first using LIME (Ribeiro et al. 2016) to approximate the nonlinear classifiers locally with an interpretable
linear model, then subsequently applying our framework.
3

---

Under review as a conference paper at ICLR 2022
3 DISTRIBUTIONALLY ROBUST RECOURSE ACTION FRAMEWORK
Our Distributionally Robust Recourse Action (DiRRAc) framework robustifies formulation ( by relaxing the parametric assumption and hedging against distribution misspecification. First, we assume that the mixture components IP: are specified only through moment information, and no particular parametric form the distribution is imposed. In effect, P, is assumed to have mean vector 0g E Fd and positive definite covariance matrix Σn > O. Second, we leverage ideas from distributionally robust optimization to propose a min-mas max formulation of [ in which we consider an ambiguity set which contains a family of probability distributions that are sufficiently close to the nominal distribution P. To prescribe the ambiguity set,
the Gelbrich distance.
Definition 3.1 (Gelbrich distance). The Gelbrich distance G between two tuples (6, E ERRA x S
and (0, Σ) E Rd x 84 amounts to G( Σ), (0, E)) - 10 012 + Tr Σ E -
It is easy to verify that G is non-negative, symmetric and it vanishes to zero if and only if (0,E) (0, S). Further, G is a distance Rd x Sf. because it coincides with the type-2 Wasser- stein distance between two Gaussian distributions N(,, Σ) and W22 Σ) (Givens & Shortt 1984). Distributionally robust formulations with moment information prescribed by the G distance computationally tractable under mild conditions, deliver reasonable performance guarantees and also generate a conservative approximation of the Wasserstein distributionally robust optimization problem (Kuhn et al. 2019).
In this paper, we use the Gelbrich distance G to form neighborhood around each Px.
BR (Px) Qu Qk (0x, Ex), G((Os, Ex), (Øn. Ex)) pk
Intuitively, one can view B₁ (P&) as a ball centered at the nominal component P. of radius Ps: 2 0 prescribed using the distance G. This component set (Pxx) is non-parametric, and the first two moments of Q& are sufficient decide whether Q& belongs (Px). Moreover, if Qs Bx (Pxx, then any distribution %% with the same mean vector and covariance matrix as Q also belongs B₁ (Px). Notice that even when the radius pk is zero, the component set (IPx) does not collapse into singleton. Instead, if P then B, (PPk) still contains all distributions of the same moment (0,, Ex) with the nominal component distribution Pg., and consequentially possesses the robustification effects against the parametric assumption on Px. The component sets are utilized to construct the ambiguity set for the mixture distribution as
B(P)
3Qx E B& (Px)) Ak E [K] such that Q (Qk, (R)KK())
Any Q B(P) is also mixture distribution with K components, with the same mixture weights p. Thus, ((P) contains all perturbations of IP induced separately on each component by (px)s).
We are now ready to introduce our DiRRAc model, which is min-max problem of the form
inf xEX
sup ((Cg(x) 0)
CEB(²)
c(x, x0) 5
sup Q (C,(z)) = 0) < (Px)
Vk E [K].
The objective of 2 is to minimize the worst-case probability of unfavorable outcome of the recourse action. Moreover, the last constraint imposes that for each component, the worst-case conditional probability of unfavorable outcome should be strictly less than 1. Put differently, this last constraint requires that the action should be able to lead to favorable outcome for any distribution in B (P&)). By definition, each supremum subproblem in (2] is an infinite-dimensional maximization problem over the space of probability distributions, and thus it is inherently difficult. Fortunately, because we the Gelbrich distance to prescribe the set By (Px), we can solve these maximization problems
4

---

Under review as a conference paper at ICLR 2022
analytically. This consequentially leads to closed-fore reformulation of the DiRRAc model into a dinte-dimensional problem. Next, we will reformulate the DiRRAc problem 2 provide a sketch of the proof and propose numerical solution routine.
3.1 REFORMULATION OF DIRRAC
Each supremum in [2] an infiniteddimensione optimization problem on the space of probability distributions. We now show that [2] can be reformulated as a finite-dimensional problem. Towards this end, let X be the following d-dimensional set
X f c(a, z0) S
-0 +ullelll
Vk E
[K]
(3)
The next theorem asserts that the DiRRAc problem (2] can be reformulated a d-dimensional optimization problem with an explicit, but complicated, objective function.
Theorem 3.2 (Equivalent form of DiRRAc). Problem is equivalent the following finite- dimensional problem
x²2 x T pŁ11z013 P& PaO =| v En x)2
inf TEA
Σ kE[K]
(4)
00 x2 x: Eep
3.2 PROOF SKETCH
We now sketch the proof of Theorem 3.2 case probability of unfavorable outcome function
For any component h E [K], define the following worst-
fx(
& sup Qx(Cz(z) = sup (P.).(PP)
Qx(A x 00
Wk E [K].
(5)
(L.
To proceed, we rely on the following elementary result from Nguyen (2019 Lemma 3.31). Lemma 3.3 (Worst-case Value-at-Riae ais-Ris)). For any x Rd and 3 E (0, 1). we have
1- B V T
inf
sup (P.)
@ x -7) -7) - 0g +
Exe +
(6)
Note that the left-hand side of 66] is the worst-case Value-at-Risk with respect to the ambiguity set
B& (P.x). Leveraging this result, the next proposition provides the analytical form of fa fx(x.
Proposition 3.4 (Worst-case probability). For any l E [K] and (0z, Ex. PR)PP) Rd. x 3 x R.,
define the following constants A A Og x, Bu A x Enx, and Cs P pall21l22. We have
A + Cp 2 0,
fa(
sup (P.)
@o x 50
ALCC+BB
0
2
E (0,1) if A Ck < 0.
15+
The proof of Theorem 3.2 follows by noticing that the DiRRAc problem (2) using the elementary functions fü as
can be reformulated
min
Σ kE[K]
pafa(z) c(x,20) S 6, fx(x) < Vk E [K]
where the objective function follows from the definition of the set (P).). suffices now to combine with Proposition 3.4 to obtain the necessary result. The detailed proof is relegated to the Appendix.
5

---

Under review as a conference paper at ICLR 2022
3.3 PROJECTED GRADIENT DESCENT ALGORITHM
We consider in this section an iterative numerical routine to solve the DiRRAc problem in the equiv- alent form [4] First, notice that the second constraint that defines X in [3] a strict inequality, thus the set A' is open. We thus modify slightly this constraint by considering the following set
Xe = f E c(r, S -0g x + pæ||=i|22 S
vk E [K]}
for some value > sufficienlly small. Moreover, if the parameter is too small, it may happen that the feasible set X₂ becomes empty. Let dmnu E R+ be defined the optimal value of the following optimization problem
min { inf (0,
t.t. I EE -0, PM||=|12 - Ak E [K].
Then it easy to see that X. is non-empty whenever 5 2 8min In addition, because continuous and X is closed, the set X² is compact. In this case, we can consider problem [4] with the feasible set being Xg, for which the optimal solution is guaranteed to exist.
Let us now define the projection operator Projx,
Proix, (x') arg min (||x 2'12 11: x I X.)
If X is convex and c.0) is convex function, then X. is also convex, and the projection opera- tion be efficiently computed using convex op- timization. In particular, suppose that c(x, ro) | the Euclidean norm and X second- order cone representable, then the projection is equivalent to second-order cone program, and can be solved using off-the-shelf solvers such as GUROBI or Mosek (MOSEK ApS] 2019). The projection operator Projx, now forms the build- ing block of a projected gradient descent algo- rithm with backtracking linesearch. The details regarding the algorithm, along with the conver- gence guarantee, are presented in Appendix E
Xproj
Xo
Figure 2: Shaded area represents X. Cir- cular arc represents the proximity constraint c(z, zo) = 8. Dashed lines represent the hy- perplane - = O. elliptic curves represent
the robust margin -0 pk ||||==|| 0. In- creasing Ps brings the elliptic curves farther away from the dash lines, and the set X' moves deeper inside the favorable prediction region.
4 GAUSSIAN DIRRAC FRAMEWORK
We here revisit the Gaussian assumption on the component distributions, and propose the parametric Gaussian DiRRAc framework. We make the temporary assumption that P& are Gaussian for all k [K], and we will robustify against only the misspecification of the nominal mean vector and covariance matrix (0x, 5xx). To do this, we first construct the Gaussian component ambiguity sets
Vk: B (PA) A
{ (Qu Qu (0 Ex), G((,. Ex), (o,, Ew) S Pk }
where the superscript emphasizes that the ambiguity sets are neighborhoods in the space of Gaussian distributions. The resulting ambiguity set for the mixture distribution is
NN
Q
3Qx BY (PPs) Ak: E [K] such that Q (Qk, (Qu.Pa)REIKI)
The Gaussian DiRRAc problem formally defined as
min nex
sup Q(Cr(z)= = 0) QEB (
s. t.
clr, HO) <
(8)
sup
Qu (C(()))) 0)
Vk [K].
Q (..)

---

Under review as a conference paper at ICLR 2022
Similar to Section will provide the reformulation of the Gaussian DiRRAc formulation and sketch of the proof in the sequence. Note that the last constraint in 8 has margin 1 instead of 1 as in the DiRRAc problem 2
The detailed reason is revealed in the proof sketch in Section 4.2
4.1 REFORMULATION OF GAUSSIAN DIRRAC
Remind that the feasible set X' is defined as in equation 3 The next theorem asserts the equivalent form of the Gaussian DiRRAc problem [
Theorem 4.1 (Gaussian DiRRAc reformulation). The Gaussian DiRRAc problem [ is equivalent to the following oplimization problem
0 x)² 12110111
min zEA'
Σ KE|K]
PET
vV x. Tnx + Pk 1| la (0% x)² + EeT p 11110
Problem (9] can be solved using the projected gradient descent algorithm discussed in Section 3.3 Note that the gradient of the objective function can be evaluated easily using the chain rule.
4.2 PROOF SKETCII
The proof of Theorem 4. relies on the following result which asserts the analytical form of the worst-case Value-at-Risk under parametric Gaussian ambiguity set (Nguyen 2019 Lemma 3.31).
Lemma 4.2 (Worst-case Gaussian Value-at-Risk), For any x E IRd and B E (0, 1 we have
inf T: sup C (PW)
Qx(0 = =-0 x +tt x Eez + p (10)
with f-1(11111 3).
important to note that Lemma 4.2 is only valid for 3 E (0,0.5). Indeed, for evaluat- ing the infimum problem in the left-hand side of [ requires solving non-convex optimization problem as 4 41-(1- 3) < 0. As a consequence, the last constraint of the Gaussian DiRRAc formulation { capped at probability value of 0.5 ensure the convexity of the feasible set
in the reformulation [ The proof of Theorem 4. follows a similar line of argument as for the DiRRAc formulation, the details are relegated to the appendix.
NUMERICAL EXPERIMENTS
In this section, we evaluate the performance of our DiRRAc framework on popular benchmarks.
We will compare our proposed DiRRAc model [2] and Gaussian DiRRAc model [8] against three state-of-the-a of-tth-artttt methods: the Robust and Rehable Algorithmic Recourse (ROAR) (Upad- hyay et al.) 2021). Actionable Recourse (AR) in linear classification (Ustun et al.) 2019) and Model Agnostic Contrastive Explanations (MACE) (Karimi et al., 2020). Throughout, we use the 1 distance c(z, | - _p 11. Complementary results and details about the datasets and
the experiment setup are provided Appendix A All codes and results can be accessed from https::/aanoyyoon
4open www.ssccie.ece.ee.o //iRRAA
Results on synthetic data. We synthesize 2-dimensional data by using K 3 different shifts similar to Upadhyay al. (202T): mean shift, covariance shift, and both shifts. First, we fix the unshifted conditional distributions with X|Y = y ~ N (My, Ey) Vy E y. For mean shift, we replace μg by yeght = 140 + [a, OJT, where a is a mean shift magnitude. For covariance shift, we replace Σg by Mahil (1+3) B) where 3 is covariance shift magnitude. For mean and covariance shift, we replace (Ho. Eo) by (H4 shin E We generate 500 samples each class from the unshifted
distribution with Ho [-3: -3]. f1 = 33: and Eo = Σ I. To estimate 0g and Σn for synthetic data, we define valid mixture weights P. generate data for each component for 100 times with the same ratio as the mixture weight. We train 100 logistic classifiers to compute the empirical mean 0g and the empirical covariance matrix Eg for the k-th component. We generate recourse for
7

---

Under review as a conference paper at ICLR 2022
each test instance that belongs to negative class. Finally, compute the empirical validity as the fraction of instances that are still valid with respect to the shifted classifiers. The results Figure 3 demonstrate that recourses generated by our framework are robust to model shifts, other baselines have low validity with even a small shift magnitude.
0.8
ARt
0.8
AR
0.8
AR
MACE
Widdy
0.4
0.1
0.1
0.0
0.2
04
2.2
0.0
0.0
0.0
0.8
Figure 3: Impact of magnitude of distribution shifts to empirical validity
Real-world data. We use three real-world datasets which capture different data distribution shifts (Dua & Graff 2017]: (i) the German credit dataset, which captures a correction shift. (ii) Small Business Administration (SBA) dataset, which captures a temporal shift. (iii) the Stu- dent performance dataset, which captures geospatial shift. Each dataset contains original data and shifted data. We normalize all continuous features to [0. 1]. Similar to Mothilal et al. (2020), we one-hot encodings for categorial features, then consider them continuous features [0, 1]. To To estimate (01, Σn,, we split randomly 80% of the original
ease the comparison, we choose dataset and train a logistic classifier. This process is repeated independently 100 times to obtain 100 observations of the model parameters, then we compute the empirical mean and covariance matrix for (0, Σ1). In parallel, we randomly split 80-20 the shifted dataset 100 times, and each time train logistic classifier the training set. This procedure generates 100 future model parameters.
To measure the performance of each method, we do a (80% training, 20% testing) split of the original dataset, train linear classifier the training data. and generate recourse for each test instance that classified as unfavorable. To compute M1 validity, we split randomly 80% of the original data 100 times and train 100 logistic classifier. The M1 validity computed by the empirical validity on those 100 model parameters. The M2 validity is measured by the empirical validity on the 100 future model parameters, and we also compute the l and l2 distance between the recourse and the original instance. The results in Table [ keeping the I and la cost low. ROAR has high validity in all three datasets, but also has higher cost than our framework.
demonstrate that our DiRRAc have high validity, while
Table Benchmark of Mj validity, M2 validity, 4 and la cost on different real-world datasets.
Dataset
Methods
Mi validity
M2 validity
In cost
la cost
German Credit
AR
0.73 0.25
0.78 0.00
1.26 + 0.68
0.94 + 0.41
MACE
0.87 + 0.15
0.97 + 0.00
2.11 + 0.86
0.86
1.20 + 0.47
ROAR
1.00 - 0.00
1.00 0.00
2.60 1 0.40
1.08 1 0.16
DiRRAc
1.00 1:01:000
1.00 1.00
2.09 0.43
0.96 1 0.18
Gaussian DiRRAc
1.00 0.00
0.93 0.05
0.73 0.47
0.47:1 0.38
SBA
AR
0.26 + 0.24
0.42 0.14
4
1.56 + 0.76
MACE
1.00 0.00
0.00
6.55
2.50 0.11
ROAR
1.00 1.00
0.00
2.25
0.98 + 0.23
DiRRAc
1.00 0.00
1.1 1..00
0.82 1 0.31
Gaussian DiRRAc
1.00 0.01
1.00
1.14 0.42
0.83 1 0.30
Student Performance
AR
0,28 + 0.08
0.35 0.12
1.18 + 0.99
0.82 + 0.60
MACE
0.66 + 0.12
0.57 0.100
0.81 0.40
0.51 1 0.24
ROAR
1.00 11 0.01
0.92
1.20
0.81 1 0.13
DiRRAc
1.00.1
0.991
0.74
0.63 1 0.14
Gaussian DiRRAC
1.00 - 0.00
0.98
0.74 0.18
0.74 0.18
Nonlinear models. Following the previous work in Rawal et al. (021 and Upadhyay et al.
202T.. we adapt our framework and other baselines to non-linear models by first generating local
8

---

Under review as a conference paper at ICLR 2022
linear approximations using LIME (Ribeiro al. 2016 LIME is a popular method that explains the predictions of a machine learning model by learning an interpretable model locally around an input instance 2g. To obtain local explanation, LIME synthesizes perturbed examples in the lo- cal neighhorhood of zo. queries the predictions of models for these examples, and then trains an interpretable model based on these labeled synthetic examples.
For each instance To. we first do a 80-20 split on the original dataset and train a MLPs classifier on the training data. Then generate local linear model for MLPs classifier 10 times using LIME with 1000 perturbed samples. To estimate (0,,E,), we compute the mean and covariance matrix of parameters Os. of 10 local linear models. We generate recourse for each instance of test data that belongs to negative class We choose randomly 10% of shifted dataset and concatenate with training data of original dataset, then train MLPs classifier. This process is repeated 10 times to obtain 10 shifted classifiers. We evaluate the M1 and M2 validity of each method by computing validity of recourses on the original MLPs classifier and the shifted classifiers.
The results in Table 2 the original and shifted MIPs classifier, while keeping the I and l2 cost low.
demonstrate that our DiRRAc have a higher validity than other baselines in
Table 2: Benchmark of M1 validity, M2 validity, l and l2 cost for non non-linear models on different real-world datasets.
Dataset
Methods
M1 validity
M2 validity
I1 cost
l cost
German Credit
AR
0.67 + 0.47
0.59 + 0.38
1.00 0.00
1.00
MACE
0.67 + 0.47
0.31 0.22
1.99 : 0.29
1.19 0.13
ROAR
0.87 = 0.26
0.66 0.33
2.66
1.21 + 0.01
DiRRAc
1.00:: 0.00
0.80
1.07
1.00 0.01
Gaussian DiRRAc
0.91 + 0.29
0.73 0.29
1.05
0.95 + 0.17
SBA
AR
1.00 1.00
0.27
1.02 0.04
1.00
MACE
1.00 0.00
0.16
2.31 0.40
ROAR
0.91 0.29
0.91
3.24
1.07 0.07
DiRRAc
1.00
0.99
1.03
+.13
Gaussian DiRRAc
1.00 100+00000
0.23
+
0.81 + 0.09
Student Performance
AR
0.47 0.50
0.41 0.44
1.02
+
MACE
0.60 +
0.49
3.04
1.44 0.57
ROAR
0.95 0.22
0.29
1.24 0.67
DiRRAc
1.00 1 0.00
0.94
0.56
0.84 1 0.26
Gaussian DiRRAc
1.00 + 0.00
0.96
0
0.87 + 0.30
6 CONCLUDING REMARKS
In this work, we proposed the Distributionally Robust Recourse Action (DiRRAc) framework to address the problem of recourse robustness to model shifts. We introduced distributionally robust optimization approach for generating robust recourse using projected gradient descent algorithm. Furthermore, we also discuss several extensions of our framework. The experiments with synthetic and real-world datasets demonstrated that our framework has the ability to generate recourse that are robust to model shifts under different types of data distribution shifts. We also showed that our framework can be adapted to different model types, linear and non-linear models.
Remark 6.1 (Extensions). The DiRRAc framework can be extended to hedge against the misspec- ification of the mixture weights p. Alternatively, the objective function of DiRRAc can be modified to minimize the worst-case component probability. These extensions are explored in Section C Corresponding extensions for the Gaussian DiRRAc framework are presented in Section D
Remark 6,2 (Choice of ambiguity set). The distributionally robust result in this paper funda- mentally on the design of the ambiguity sets using a Gelbrich distance on the moment space. This Gelbrich ambiguity set leads to the || Il-rraularizzaioon of the worst-case Value-at-Riss in Lem- mas 3.3 and 4.2 If we consider other moment ambiguity sets, for example, the moment bounds in Delage & Ye (2010)
the Kullback- Biilback--Lible--nne Leibler-rype sets in Taskesen et al. (2021). then these reg- ularization equivalence are not available, and there is no trivial way to extend the distributionally robust results to provide the reformulation of the (Gaussian) DiRRAc framework.

---

Under review as a conference paper at ICLR 2022
REFERENCES
André Artelt and Barbara Hammer. On the computation of counterfactual explanations survey. arXiv:1911.07749 2019.
G. Bayraksan and D. K. Love. Data-driven stochastic programming using phi-divergences. IN- FORMS TutORials in Operations Research, pp. 1-19, 2015.
Amir Beck. First-order Methods in Optimization. SIAM, 2017.
Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Sci- ence, 59(2):341-3333 1-357, 2013.
D. Bertsimas, V. Gupta, and N. Kallus. Data-driven robust optimization. Mathematical Program- ming, 167(2)2355-922, 2018.
S. Boyd and L. Vandenberghe. Convex Oprimization. Cambridge University Press, 2004.
Paulo Cortez and Alice Silva. Using data mining to predict secondary school student performance. Proceedings of 5th FUture BUsiness TEChnology Conference, 2008.
Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl. Multi-objective counterfactual explanations. In International Conference Parallel Problem Solving Nature, pp. 448-469. Springer, 2020.
E. Delage and Y. Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3):595-612, 2010.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL jttt:://aarch
ics. www.cccc.o www..uii......ummmmomm
John C Duchi, Peter W Glynn, and Hongseok Namkoong. Statistics of robust optimization: A
generalized empirical likelihood approach. Mathematics of Operations Research, 2021.
L. Ghaoui, M. Oks, and F. Oustry. Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Operations Research, (144))543-555 2003.
C.R. Givens and R.M. Shortt. A class of Wasserstein metrics for probability distributions. The Michigan Mathematical Journal, 31(2):331-24) 1984.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning, pp. 1929-1938, 2018.
Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Model-agnostic counterfactual explanations for consequential decisions. arXiv preprint arXiv: // 190, 2020.
Amirhossein Karimi, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: Contrastive explanations and consequential recommendations. arXiv preprint arXiv:2010.04050, 2021.
D. Kuhn, P. Mohajerin Esfahani, V.A. Nguyen, and S. Shafieezadeh-Abadeh Wasserstein distribu- tionally robust optimization: Theory and applications machine learning. INFORMS TutORials in Operations Research, pp. 130-169, 2019.
Min Li, Amy Mickel, and Stanley Taylor. "Should this loan be approved or denied?": A large dataset with class assignment guidelines. Journal of Statisties Education, 26(1):55 66, 2018.
MOSEK ApS. MOSEK Optimizer API for Python 9.2. 10, 2019. URI. htt.htttss///occ....
com/ 9. http:yythaa//inneeee hiwiaappp/iiix...mmm html
Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp. 607-617, 2020.
10

---

Under review as a conference paper at ICLR 2022
K.P. Murphy, Machine Learning: Probabilistic Perspective. MIT Press, 2012.
Hongseok Namkoong and John C Duchi. Variance-based regularization with convex objectives. In Advances in Neural Information Processing Systems 30, pp. 2971-2980, 2017.
Viet Anh Nguyen. Adversarial Analytics. PhD thesis, Ecole Polytechnique Fédérale de Lausanne, 2019.
Leandro Pardo. Statistical Inference Based Divergence Measures. CRC Press, 2018.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv:1908.00 05659, 2019.
Kaivalya Rawal and Himabindu Lakkaraju. Interpretable and interactive summaries of actionable recourses. arXiv e-prints, pp. arXiv-2009, 2020.
Kaivalya Rawal, Ece Kamar, and Himabindu Lakkaraju. Algorithmic recourse in the wild: Under- standing the impact of data and model shifts. arXiv preprint arXiv:2012.11788. 2021.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should trust you?": Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1135-1144, 2016.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead, 2019.
Chris Russell. Efficient search for diverse coherent explanations. Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT '19, pp. 20-28. Association for Computing Machinery, 2019.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on Stochastic Program- ming: Modeling and Theory. SIAM, 2009.
Ilia Stepin, Jose M. Alonso, Alejandro Catala, and Martín Pereira-Fariña. A survey of contrastive and counterfactual explanation generation methods for explainable artificial intelligence. IEEE Access, 9:1 1904- 2021.
Bahar Taskesen, Man-Chune Yue, Jose Blanchet, Daniel Kuhn, and Viet Anh Nguyen. Sequential domain adaptation by synthesizing distributionally robust experts. In Proceedings of the 38th International Conference Machine Learning, 2021.
Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorith- mie recourse. In Advances in Neural Information Processing Systems 35, 2021.
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* '19, pp- 10-19, 2019.
Suresh Venkatasubramanian and Mark Alfano. The philosophical basis of algorithmic recourse. In Proceedings of the 2020 Conference Fairness, Accountability, and Transparency, FAT* '20, pp. 284-293, New York, NY, USA, 2020. Association for Computing Machinery. ISBN doi: 10.1145/3351095.3378877
9781450369367.
URL Inttps://cci.ooo /0. 1145/
B351095 3372876
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harvard Journal of Law & Technology, 2018.
11

---

Under review as a conference paper at ICLR 2022
A ADDITIONAL EXPERIMENT RESULTS
Synthetic data, For synthetic data, we perform experiments on datasets capturing 3 types of data distribution shift: mean shift, covariance shift, mean and covariance shift (both shift)
We define the adaptive mean and covariance shift magnitude as a = Padopt X kiter, 3 = addapt * #iter with Madapt, Dddapt the factor of data shifts, iter is the index of iterative loop of synthesizing process.
To visualize feasible set as Figure 2 generate synthetic data with the following parameters: 140 --3;-3], -3], μ [3: 3]. and 20 = Σ₁ = I. Then, we split data to training set and test set (80% for training and 20% for testing), train the original classifier on training one instance on test set that is classified
and then choose negative class to visualize the feasible set. For data distribution shifts, we generate mean shifts and covariance shifts 50 times each type with adaptive mean and covariance shift magnitude, with the parameters Madapt Endapt = 0.1. Then we train
and get the parameters 02 and Σg same above.
Table 3: Parameters for the feasible set visualiza- tion experiment in Figure
Table 4: Parameters for the impact of data dis- tribution shifts experiment Figure 3
Parameters
Values
Parameters
Values
K Eada
2
K
3
8add
0.2
005, 0.5]
00.3, 0.4, 0.3]
p
[1.1]
P
[0,0,0]
À
0.7
A
0.7
<
C
To visualize the data and decision boundaries of linear classifiers, we generate synthetic data with the same parameters as above. Then we train 4 classifiers on original data and synthetic capturing 3 types of distribution shifts and visualize the decision boundaries as Figure 4 Then we synthesize shifted data 100 times, 33 mean shifts, 33 covariance shifts and 34 mean and covariance shifts (both shifts) and visualize 100 model's 's parameters in 2D as Figure 5
75
75
75
75
-53
-50
-50
-5.
-00
(a) Original data
(b) Mean shift
(c) Covariance shift
(d) Both shift
Figure 4: Synthetic data shifts and the corresponding model parameter shifts (decision boundaries).
12

---

Under review as a conference paper at ICLR 2022
2.75
Original
2.50
Mean shift
Cov shift
2.25
Both shift
2.00
1.75
1.50
1.25
1.00
0.6
0.8
1.0
1.2
1.4
1.6
1.8
2.0
8D
Figure 5: Parameter 0 of the classifier with different types of data distribution shifts
To evaluate how magnitude of upper bound cost affects the validity of our models, use different values of upper bound cost. We define å = 6min + Sadd with Smin is defined in[77] We use the same parameters above for generating synthetic data. For each value of dadd. evaluate the validity by using 100 classifiers trained on 100 different data distribution shifts with different shift types.
1.0
0.8
M₂ validity
0.6
0.4
0.2
DiRRAc
0.0
0.00
0.05
0.10
0.15
0.20
a
Figure 6: Impact of choosing dada to the validity of DiRRAc
Additional results for the Impact of magnitude distribution shifts to empirical validity.
Ghussian DRAAC
Gaussian DIRRAC
Gaussian DIRRAC
0.3
AR
0.2
0.2
AR
MACE
MACE
MACE
200
0.2
044
0.6
2.5
200
0.0
02
04
0.5
0.0
2.0
0.2
02
0.
0.8
1.5
0,8
Figure 7: Impact of magnitude of distribution shifts to empirical validity of Gaussian DiRRAc
13

---

Under review as a conference paper at ICLR 2022
To evaluate the trade-offs between the 1 cost and the validity of DiRRAc, benchmark these two criteria by running DiRRAc with different values of 8. We define = ômin + cadd as before. For each value of 6, we evaluate the 4 cost and validity by using 100 classifiers trained 100 different data distribution shifts with 3 different shift types.
We also evaluate the trade-offs between l cost and validity of DiRRAc using 20 instances. In the comparison with ROAR, we evaluate I cost and validity of DiRRAc and ROAR using 10 instances. We wide range of parameters for ROAR and compute the li cost and validity of recourses. We report the results of 2 experiments in Figure and Figure y
1.0
0.8
M2 validity
0.6
0.4
0.2
DiRRAc
0.0
5,800
5.825 5.850
5.875 5.900 5.925 5.950
h cost
Figure 8: Cost of robustness of DiRRAc
1.0
0.9
M2 validity
0.8
0.7
0.6
DiRRAc ROAR
0.5
3.4
3.6
3.8
4.0
4.2
4.4
h cost
Figure 9: Comparison of M2 validity as a function the I distance between input instance and the recourse for our DiRRAc method and ROAR
Real-world data. For each of three real-world datasets, we choose number of features to bench- mark with other baselines:
14

---

Under review as a conference paper at ICLR 2022
For German credit dataset from UCI repository, choose 5 features: Status, Duration, Credit amount, Personal status, Age. We found in the description two datasets that feature Status in the data correction shift dataset corrects the coding errors in the original dataset (Dua & Graff 2017).
For SBA dataset, following the work from Li et al. (2018) and Upaadhyy et al. (2021) we choose the following features: Selected, Term, NoEmp, CreateJob, RetainedJob, Ur- banRural, ChgOffPrrnGr, GrAppv, SBA.Appy, New, RealEstate, Portion, Recession, We use the instances during 1989-2006 as the original data, and the remaining instances as temporal shift data.
For Student Performance dataset, motivated by Cortez & Silva (2008), we choose feature
G3 final grade for deciding the label pass or fail for each student. The student who has G3 12 labeled (failed) and (passed) otherwise. For input features, we choose
9 features: Age, Study time, Famsup, Higher, Internet, Health, Absences, GI, G2. We separate the dataset into the original the geospatial shift data by different schools.
Table 5: Accuracy of the underlying classifiers.
Dataset
Methods
Accuracy
German Credit
LR
0.72 0.00 0.00
MLPs
0
Shifted German Credit
LR
0.0
MLPs
0.72
LR
0.79
MLPs
0.93 1
Shifted SBA
LR
0.77 0.01
MLPs
0.89 0.01
Student Performance
LR
0.84 0.01
MLPs
0.91
Shifted Student Performance
LR
0.91 0.00
MLPs
0.99 - 0.01
Experiments with Euclidean norm. We accumulate here the numerical results with c(2, zn) || - Tu zull2. Table 6 reports the M2 validity, along with the l and l2 distance between the input instance and its corresponding recourse. Results are mean + standard deviation, calculated from 100 independent replications. The settings of this experiments are the same as the experiments in Section
Table Benchmark of validity, 4 and la using Euclidean cost on different real-world datasets.
Dataset
Methods
M2 validity
I cost
la cost
German Credit
AR
0.78 0.00
1.26+ 0.68
0.94 + 0.41
MACE
0.97 + 0.00
2.10 + 0.86
1.20 + 0.47
DiRRAc
0.99 0.02
1.72 + 0.49
0.77 + 0.19
Gaussian DiRRAC
1.00.L
1.78 0.49
0.77.1 0.19
SBA
AR
0.41 0.13
1.80 1.14
1.16 0.60
MACE
0.98 0.14
3,99 - 0.22
1.92 + 0.07
DiRRAc
0.98 0.02
2.43 + 1.30
1.17 + 0.53
Gaussian DiRRAc
0.92 + 0.02
2.43 + 1.35
1.18 + 0.54
Student Performance
AR
0.35 + 0.12
1.18 + 0.99
0.82 + 0.60
MACE
0.64 + 0.09
0.81+ 0.40
0.51+ 0.23
DiRRAc
1.00+ 0.00
1.30 + 0.38
0.69 0.16
Gaussian DiRRAc
1.00 0.00
1.32 + 0.40
0.71 + 0.16
15

---

Under review as a conference paper at ICLR 2022
Table Parameters for the experiments with real-world data in Table
Parameters
Values
K
Gaad
0.5
P
[1]
[0]
X
0.7
S
Experiments with prior on S.
In this experiments assume that we does not have access to the training data. We set the 0 Oo. lg parameters of the original classifier. Then choose Σn T. We generate recourse for each input instance and compute Mj using the original classifier and M2 validity using the shifted classifiers. In this experiments we choose
0.1.
The results in Table 8 show that our methods remain the same performance while keeping the / and cost lower than ROAR in three datasets except the l2 cost in SBA dataset.
Table Benchmark of M1 validity, My validity, 4 and le using Σx 0.1 I on different real-world datasets.
Dataset
Methods
Mi validity
M2 validity
[1 cost
l cost
German Credit
ROAR
1.00 0.00
1.00 0.00
2.60 1:
+ 0.16
DiRRAc
1.00 0.00
0.97 4 0.05
1.97 + 0.34
1.06 -1: 0.13
Gaussian DiRRAc
1.00 + 0.00
0.98 + 0.04
1.97 + 0.34
0.97:1 0.14
SBA
ROAR
1.00 + 1.00
1.00 0.00
2.25 + 0.55
0.98 + 0.23
DiRRAc
1.00 + 0.00
1.00 0.00
2.13 + 0.41
1.44 + 0.26
Gaussian DiRRAc
1.00 0.00
1.00 0.00
2.11 + 0.45
1.27 + 0.41
Student Performance
ROAR
1.00 + 0.01
0.98 0.02
1.70 0.27
0.81 + 0.13
Ai
1.00 0.00
1.00
1.73 0.18
1.43 + 0.16
Gaussian DiRRAc
1.00 0.00
1.00 0.00
1.21 1 0.33
1 0.16
B PROOFS
B. PROOFS OF SECTION
To prove Proposition 3.4 we are using the notion of Value-at-Risk which formally defined as
follows.
Definition B.1 (Value-at-Risk). For any fixed distribution Qs of the Value-at-Re Risk at the risk tolerance level 3 E (0, 1) of the loss 0 J defined as
Qx- (0 2) A inf(T E R Qu S 21-
We now ready to provide the proof of Proposition 3.4
Proof of Proposition 3.4 Using the definition of the Value-at-Risk in Definition B.I we have
sup (P.)
( s 0) inf
8: [0, 1].
sup f..
Qo x 200)
inf
3: [0,
sup Qx- VaRg(-OT S (F.)
16

---

Under review as a conference paper at ICLR 2022
By Nguyen (2019
Lemma 3.31), we can reformulate the worst-case value-at aalue-at-riste at-risk
CK- VaRz(--0xx) - x +
V 3 V
1 -
Exx + Pk |
sup Qx (PE)
now easy to observe that in the first case when 0f x + pa pk|1ar11 2 O, then we should have
EB. Qn (0 x Σ 0) 1.
We now consider the second case when - 0% x + vs || < O. is easy to see, by the monotocity of the worst-case value-at-risk with respect to 3, that the minimal value S should satisfies
0g +
1 - 8* ga
Vx
+
| = 0. v3-
Pk
Using the transformation 1
[* we have
0g xt + v1 &V
x Exx + pk p=||=/122- 0. T
By rearranging terms and then squaring up both sides, we have the equivalent quadratic equation
(Aī + BB)+² + 24t C =
with A4 - 0 x < 00 V x Exx 2 O, and C₁ 2 Pk |0112 2 0 as defined in the statement of
the proposition. Note, moreover, that we also have A 2 C2 This leads the solution
AACC + B₁ A B C
2 0.
1 B
Thus, find
AAC - By V A + B - C
fa(x)
A + B
This completes the proof.
We now provide the proof of Theorem 3.2
Proof of Theorem
3.2 We first consider the objective function f of [2 which can be re-expressed
f(x) = sup P(Cg(x)= =) = sup
Σ
@ 50)
PEB(F)
EBEB. (Pc)
kE(K]
Σ
Qu < 0)
Pk
sup
kE[R]
(f.)
Σ kE[K]
Pk x fz)
where the equality in the second line follows from the noggatiityvy of Pt. and the last equality fol-
lows from the definition of fx(z) in (5) Applying Proposition 3.4 we obtain the objective function
of problem [4]
Consider now the last constraint of 2 Using the result of Proposition 3.4 this constraint is equiv- alent to
0 x + px |
Vk [K].
This leads the feasible set X' is defined in
This completes the proof.
17

---

Under review as a conference paper at ICLR 2022
B.2 PROOFS OF SECTION 4
To prove Theorem function
4.1
we first define the following worst-case Gaussian component probability
(a)
Qx(Cg(o)= = =) sup Qu S 0) EREBY
sup
vk [K]. (11)
QrE (Pa)
The next proposition provides the reformulation of f/
Proposition B.2 (Worst-case probability Gaussian). For any Rd, any k [K] and any
(0h, Ex, Pk) E IR x $4 x R., define the following constants A₁ - -0 x, Bx V x Es,, and
Ck - pk 111l212. The following holds:
(i) We have f (x) 2 if and only if As + Ck <.
(ii) If x satisfies fi (x) < 3. then
A 1 C2
(x) 1-
+ Ck -
A+Bs
A + B C
Proof of Proposition B.2 We first prove Assertion (i) sian distribution Qu (On,, Ek), and thus
Pick any Q BB (P&), then Qa a Gaus-
0g
Q 1 x 50 +
Txx
Σx
Guaranteeing (x) < / is equivalent to guaranteeing
sup G().2.Ea).0.. SE
0 x 5.0
Note that we also have
0% x
0% -0p x + pMil:0|l22
sup
sup
Gi(00 (. (o.
dc: 10. -0 11
by the properties of the dual norm. This leads the equivalent condition that A, Cs 0.
We now prove Assertion
Using the definition of the Value-at-Risk in Definition B.1 we have
1
sup Qu(Ō x 0) = inf 3 3 E [0. QueBy (P)
@o S0)
sup Q+- VaR s
Q (p.)
inf
8: E [0, 2
sup
Q EBY (Pa)
Using the result from Nguyen 2019 Lemma 3.31), we have
sup QA- VaR x) = - x + IV x Eux + p/1 1| A + Bal + CRVI+1 (P.)
with & Φ-1(1 - 3). Taking the infimum over is then equivalent to finding the root of the
equation
A + tB+ + =
Using a transformation - 1/t, the above equation becomes
A&T + By + CLV1 +
with solution
Br + CA A + B
A3 C2
Notice that A& 1 C2 0, and we also have A > C thus well-defined. The result now follows
by noticing that / (x:) ++()) =1 $ (1/T).
18

---

Under review as a conference paper at ICLR 2022
We now ready to prove Theorem 4.1
Proof of T'heorem
4.1
Problem is equivalent to
min
[ke(K] Pa x PN (x)
8. b.
c(1, ro) 2 8
fk x
vk [K].
Applying Proposition
B.2 we obtaín the necessary result.
C EXTENSIONS OF THE DIRRAC FRAMEWORK
Throughout this section, we explore two extensions of our DiRRAc framework. In Section C.1 we study an additional layer of robustification with respect to the mixture weights p. Next, in Section C.2 we consider an alternative formulation of the objective function minimize the worst- case component probability.
C.1 ROBUSTIFICATION AGAINST MIXTURE WEIGHT UNCERTAINTY
The DiRRAc problem considered in Section 3 only robustifies the component distributions Pg.. We now discuss a plausible approach robustify against the misspecification of the mixture weights P. Because the mixture weights should form probability vector, it is convenient to model the perturbation in the mixture weights using the ø-divergence.
Definition C.1 (ó-divergence). Let á R + be a convex function on the domain IR,, ((1) = O, 0 x ((a/0) = x limet ((t)/t for > and 6(0/0) = 0. The o-divergence Do between two probability vectors p, p e R4 amounts to D&(p P) ΣxE[K] Pk o(pk/Pk).
The family of d-divergences contains many well-known statistical divergences such as the Kullback- Leibler divergence, the Hellinger distance, etc. Further discussion on this family can be found Pardo (2018). Distributionally robust optimization models with o-divergence ambiguity
were
originally studied in deccisionmmaingg problems (Ben-TTal Tal et al.) 2013 Bayraksan & Love 2013) and have recently gained attention thanks to their successes in machine learning tasks (Namkoong & Duchi 2017 Hashimoto et al. 2018 Duchi et al. 2021).
Let 0 be parameter indicating the uncertainty level of the mixture weights. The uncertainty set for the mixture weights is formally defined as
A a {p [0, 1 D& st).
which contains all K K-dimensional probability vectors which are of d-divergence at most from the nominal weights p. The ambiguity set of the mixture distributions that hedge against the weight misspecification is
U(P) 2 [Q:
E JQ E BA vk E [K] such that Q (Qu,,a) Pa) }.
where the component sets B& (Pxx) are defined as in Section The DiRRAc problem with respect to the ambiguity set (PP) becomes
min
sup P(Cg(0) 0) PEN(F) c(I,
8. L.
< 6
(12)
sup Qu (P.)
(x(C((x) = < Vk
[K].
important to note this point that the feasible set 112 coincides with the feasible set [2]
Thus, to resolve problem [2] it suffices to analyze the objective function [2) Given the function
o, we define its conjugate function Ø² R
{ [o)) by
[)] sup {ts o(t)
The next theorem asserts that the worst-case probability under (PP) can be computed by solving a convex program.
19

---

Under review as a conference paper at ICLR 2022
Theorem C.2 (Objective value). The feasible set of problem 11 coincides with X. Further, for every 2 E X, the objective value of 12 equals to the optimal value of a convex optimization problem
[L(()) -1
sup (((2(()) = - min 7+a PEU(P)
Σ kE[K]
P
AER PER
where (1) are computed using Proposition 3.4
Proof of Theorem
C.2
From the definition of the set U(P), we can rewrite F using a two-layer
decomposition
F(x) sup ((Cg(2) =
sup PEd
sup
E
O0' =
PE
QLEB, 4k kE[K]
Σ kE(K]
(0 x
sup
Pk X sup
PEA
Q.E
sup
Σ KE(K)
Pa fu(x),
PEA
where the equality in the second line follows from the non-negativity of Pk. and the last equal- ity follows from the definition of fx( in 5 By applying the result from Ben- Ten et al. (2013 Corollary 4.2), we have
Σ PLO fa(2)) A [
min n +
F(x)
kE[K]
s.t. Ae AER, 1 E
The proof is complete.
From the result of Theorem we can derive the gradient of objective function of [12] using Danskin's 's theorem (Shapiro et 2009 Theorem 7.21), simply using auto dittoddifferetiationn. Fur- thermore, 6* convex, and thus solving the minimization problem Theorem C.2 can done efficiently using convex optimization algorithms.
C.2 MINIMIZING THE WORST-CASE COMPONENT PROBABILITY
Instead of minimizing the (total) probability of unfavorable outcome, we can consider an alternative formulation where the recourse action minimizes the worst-case conditional probability of unfavor- able outcome over all K components. Mathematically, we opt for the component ambiguity sets B3 (Px)) constructed in Section
3 then we can solve
min
max kE[K] co) 5
sup Qu(Cx(z) 0)
(P.)
(13a)
sup Qx(C((z) 0) <
Vk [K].
Q, (P.)
Interestingly, problem [3a does not involve the mixture weighs p. As consequence, trivial ad- vantage of this model is that it hedges automatically against the misspecification of p. To complete, we provide its equivalent dimensiinn form.
Corollary C.3 (Component Probability DiRRAc). Problem
Ba
equivalent to
P.. x: 2 + To E (0) x) + r Eg -
(13b)
min ZEX
max RE
(0 x)2 + Eex
20

---

Under review as a conference paper at ICLR 2022
D EXTENSIONS OF THE GAUSSIAN DIRRAC FRAMEWORK
In this section, we leverage the results in Section C to extend the Gaussian DiRRAc framework to (i) handle the uncertainty of the mixture weight and (ii) minimize the worst-case modal probability. Remind that each individual mixture ambiguity set B (Pk) of the form
B (Px) = {Qu Qk ~ (O,. Σx), G((O,. Ex), (Ox, Ex)) S PKJ.
which is a ball in the space of Gaussian distributions.
D.1 HANDLING MIXTURE WEIGHT UNCERTAINTY GAUSSIAN DIRRAC
Following the notations in Section
define the of possible mixture weights
A {p E [0, 1 = 1, (D P) =}
and the ambiguity set with Gaussian information is defined
u (P) - Q 3p A, E e B (Px) Ak E [K] such that Q (Qk. (()
The distributionally robust problem with respect the ambiguity set (IP) is
inf sup ((Cg(z) 0) PEUN(()
s. t. c(z, 20) sup QrE (Px)
I
(14)
(c) = <)< < 4k: E [K].
Following the results in Section 4 the feasible set of of coincides to provide reformulation the objective function of [44
coincides with the set X. It suffices now
Corollary D.1. For any X. we have
sup P(Cg(#)= =) inf ++tt+1 Σ pup (1h (x) BEL (P)
A
KE[K]
s.L. AER, E R
where the values I (x) are obtained Proposition B.2
Corollary D.2 follows from Theorem D.2 by replacing the quantitics fe( by fi (x) to take into account the Gaussian parametric information. The proof of Corollary D.2 is omitted.
D.2 MINIMIZING WORST-CASE COMPONENT PROBABILITY
We now consider the Gaussian Ai that minimizes the worst-case modal probability of infeasi- bility. More concretely, we consider the recourse action obtained by solving
inf max kE[K]
sup QUEBN (Pv)
Qu(Cg(x) 0)
L. (0) 5
(15a)
sup
(C 0) < 4k E [K].
Q
The next corollary provides the equivalent form of the above optimization problem. Corollary D.2. Problem 15a is equivalent
0 x)² - -
inf #EX
max kE(K]
+ 0 LV xT Eex + pa px||=|1z |21 (0 x²2
(15b)
x E 02.10013
21

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Projected gradient descent algorithm with backtracking line-search
Input: Input instance zo, feasible set X₂ and objective function f Line search parameters: E (0, 1), (Default values: 0.7, < 1)
Initialization: Set z" +- Projx, (2o) for t = ...... T
do Find the smallest integer i 0 such that
f (Projx; (a' ((VV((z))) $f(at)
2N || Projx (0' - -X(VVf(=')) 13.
Set n1+1 = Proix, (et -x((V((()). end for Output: x²
E PROJECTED GRADIENT DESCENT ALGORITHM
The pseudocode of the algorithm presented in Algorithm ! The convergence guarantee for Algo- rithm follows from Beck 2017 Theorem 10.15), and is distilled in the next theorem.
Theorem E.1 (Convergence guarantee). Let {2') 1.0.1....T be the sequence generated by Algo- rithum 7 Then, all limit points of the sequence {x It=0. are stationary points of problem [
with the modified feasible set Xz. Furthermore, there exists some constant C >> 0 such that for any
2 1, we have
|| Proix, (x' <Vf(2'))l C
min (=0,1...,T
S VT
C
22


Reviews:
[{"review_id": "sXI931zn9d", "reviewer": "Reviewer_4adh", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n1. Most existing work on recourse actions do not consider model change, so the problem addressed by the paper is relatively new, and it is an important problem since model/data shifts are common in practice.\n2. The idea of considering/modelling model shift as a mixture shift of model parameters, and formalizing the problem as a min-max problem.\n3. The experiment results demonstrate the superiority of DiRRAc over the methods compared.\n4. The paper is well written.\n\nWeaknesses:\n1. It is not very clear how challenging it is to adopt the distributionally robust optimization technique for solving the recourse action problem. It would be useful to let readers know clearly that the adoption is non-trivial, which is particularly helpful for readers who are not familiar wi the distributionally robust optimization techinque.\n2. From the paper, ROAR is a method for generating counterfactual explanations that are robust to model shifts, but the experiments conducted do not consider ROAR as a baseline.\n3. It is not clear how efficient the proposed method is, compared to existing methods.\n4. The performance of the proposed method under no model shifts should be evaluated as well.\n\nOther comments: \n1. on page 2, there is a typo: Distribut,lly --> Distributionally\n2. The paper does not have a Conclusion section.\n\n", "summary_of_the_paper": "This paper studies the problem of recourse actions (a.k.a. counterfactual explanations) while considering data distribution shifts or model shifts. The proposed Distributionally Robust Recourse Action (DiRRAc) framework has the ability to generate valid recourse actions when model parameters shift over time. DiRRAc adopts the distributionally robust optimization technique and the paper proposes a projected gradient descent method to solve the optimization problem. Experiments are conducted with both synthetic and real world data, and the results have shown that DiRRAc methods can generate recourse actions with higher validity than two existing methods.", "summary_of_the_review": "The paper tackles a very practical and relatively new problem regarding recourse actions. The overall idea seems reasonable to me and the experiments have demonstrated the effectiveness of the proposed method. The paper is also well written. \n\nHowever, the paper has a few weaknesses as described above. The missing comparison with ROAR is a main concern. The novelty of the proposed method (regarding the adoption of distributionally robust optimization) should be clarified too.", "strength_and_weaknesses": "", "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": "iQq4OmtZnlr", "reviewer": "Reviewer_a91J", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Strengths: very clear and thorough exposition of the approach proposed. The approach proposed is very sound technically.\n\nWeaknesses: the experiments presented are rather limited and the value of the contributions is unclear. In particular, the problem of generating robust recourse was previously considered by Upadhyay et al., 2021, but the authors do not provide any evidence as to why their approach may be preferable, which is particularly concerning given that the experiments considered by the authors are heavily inspired in those of Upadhyay et al., 2021.\n\nTo strengthen the contributions of the paper, the authors should focus on improving the experiments section. The contribution of this paper would be much stronger if the authors compared the performance of their approach to that of Upadhyay et al., 2021, validated the claim that “robust optimization solutions can be overly conservative because it may hedge against a pathological parameter in the uncertainty set” in the context of algorithmic recourse, and showed that their proposed approach overcomes this issue.\n\nDetailed comments on the experiments section:\n* As previously mentioned, authors should compare their approach to Upadhyay et al., 2021.\n* Why was L1 not used as the cost function similarly to AR and MACE? Is this an inherent limitation of DiRRAc? If possible, it would be best to use L1 as the cost function for all three approaches.\n* It would be very valuable to also include experiments for non-linear classifiers (e.g. MLPs).\n* It would be very valuable to consider actionability constraints. It seems like in practice many of the features of the real-world data sets would be immutable (e.g. “Recession” in the SBA data set).\n* For the real-world data, you use significantly fewer features than Upadhyay et al., 2021, why is this?\n* In my opinion, none of the test data for which recourse is generated should be used for estimating theta and Sigma. My suggested approach: split the data into train and test, train 100 classifiers only with the train data (e.g. by subsampling 80% of the train data) to estimate theta and Sigma, and then compute recourse on the test data.\n* In the recourse setting, one typically does not assume access to the training data. It would be valuable to discuss how could theta and Sigma be estimated (or rather guessed) given no access to the data, and what would be the implications in terms of recourse validity. This could also be tested experimentally by setting theta to be the weights of the classifier for which recourse is generated and over and under estimating Sigma to various degrees.\n* For the real-world data, please include the accuracy of the classifier for which recourse is generated.\n\n\nDetailed comments on the introduction:\n* Contrary to what is stated in  Section 1 Paragraph 2, in my opinion “counterfactual explanations” and “recourse actions” should not be used interchangeably, but rather authors should refer only to “recourse actions”, since the problem of recourse validity under data shifts, at least how it is presented in this work (Section 1 Paragraph 5), is not applicable to counterfactual explanations.\n* Section 1, Paragraph 2: “If a specific application can provide the negative outcomes with recourse actions, it can improve the user engagement and boost the interpretability at the same time.” Citations needed for these statements.\n* Section 1, Paragraph 3: “we must consider age as an immutable feature” It is not a must to consider age immutable, several works consider it as a non-decreasing feature.\n* Section 1, Paragraph 4: “Various solutions has have been proposed...”\n* Section 1, Paragraph 5, “Data shifts usually induce corresponding shifts in the machine learning models’ parameters” Organizations usually retrain models periodically in repose to data shifts. The data shift itself does not induces changes to the parameters of the model.\n* Section 1, Paragraph 5: “If a recourse action fails to generate a favorable outcome in the future, then the recourse action becomes useless” Not necessarily, see Handling change over time via ex post facto in Venkatasubramanian and Alfano, 2020.\n* Section 1, Paragraph 5: “and the trust on the machine learning system is lost.” Citation needed.\n\nComments regarding section 2, 3 and 4:\n* In my opinion Algorithm 1 and Theorem 3.4 should not be in the main text, as these are just general well-known concepts from convex optimization, leaving more room for the experiments sections. Authors could just mention convergence rate of $O(1/\\sqrt(T))$.\n* Similarly, Sections 4.1 and 4.2 could be moved to the appendix, since they are not core to the main contribution of the paper and are not evaluated in the experiments section. This would also give the authors more space for the experiments section and a conclusion.\n* Equation 1: min_x\n* Equation 2, 7, 8a, 9a: $inf/min_{x \\in X}$ or add $x \\in X$ as an explicit constrain similarly to Equation 1.\n* Equation 9a, please explain why a margin of 0.5 rather than 1 is used.\n", "summary_of_the_paper": "The paper considers the problem of generating recourse actions that are robust to shifts in the parameters of the classifier. The authors present a distributionally robust optimization approach and experimentally show that for linear classifiers and under no actionability constraints, the approach generates recourse actions that have high probability of being valid under shifts to the weights of the linear classifier.", "summary_of_the_review": "While the authors present a very clear and thorough exposition of the approach proposed and the approach is technically sound, the experiments presented are very limited and the overall value of the contribution is unclear. In particular, the authors do not compare their proposed method with previous approaches addressing the problem of generating robust recourse actions.", "strength_and_weaknesses": "", "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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "_D0bnh_y8J", "reviewer": "Reviewer_RFkz", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The setting of recourse in the presence of model shifts is well-motivated, especially since models are often updated over time. The idea of formulating the problem as a distributionally robust optimization problem is compelling. \n\nOne weakness of this paper is that the technical solution provided is somewhat limited. In particular, the formulation in (4) relies heavily on the structural properties of the mixture distribution and Gelbrich distance to reformulate the optimization problem, and is not surprising given these assumptions. Since this is the main technical result in the paper, it would have been interesting to see a more general setup that considered richer distance metrics. \n\nFor the empirical section, a weakness is that DiRRAc (the method proposed in this paper) seems to optimize for ell_2 cost, whereas existing approaches seem to optimize for ell_1 cost. Thus, it is not clear how to compare the costs obtained by DiRRAc with the costs obtained in existing approaches. Moreover, it could be interesting to further investigate the tradeoffs between validity and cost for DiRRAc to illustrate the \"cost of robustness\" incurred by the approach. \n\nMinor comment:\n- Distribut,lly -> \"distributionally\" p. 4", "summary_of_the_paper": "The paper provides a framework for recourse (i.e. counterfactual explanations) that is robust to shifts in the model. They formulate the robustified recourse setup as a min-max optimization problem, where the max is over a neighborhood around the distribution over model parameters. The model parameters are drawn from a mixture of K distributions, so that the neighborhood is specified by Gelbrich distance on each component. \n\nThey propose a finite-dimensional version of the robustified optimization problem, which can be optimized using projected gradient descent. They evaluate their approach on the German credit dataset, the Small Business Administration dataset, and the Student performance dataset, each of which demonstrates a different type of data distribution shift. ", "summary_of_the_review": "Weak reject due to limited technical contribution and limited empirical comparison   \n\n-----\nUpdate after author response: I appreciate the additional experiments for l1 cost included in the revision. Moreover, although I appreciate the author's discussion of the motivation for the Gelbrich distance, I still think that the technical results are somewhat limited. Thus, I keep my assessment the same. ", "strength_and_weaknesses": "", "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:

Meta-review: The paper provides a framework for recourse (i.e. counterfactual explanations) that is robust to model shifts. The setup for the proposed method is a min-max optimization problem, where the max is over a neighborhood around the distribution over model parameters. The model parameters are drawn from a mixture of K distributions, so that the neighborhood is specified by the Gelbrich distance on each component. The authors propose a finite-dimensional version of the robustified optimization problem, which can be optimized using projected gradient descent. They evaluate their approach on the German credit dataset, the Small Business Administration dataset, and the Student performance dataset, each of which demonstrates a different type of data distribution shift.

Strengths:

- Most existing work on recourse actions do not consider model change, so the problem addressed by the paper is relatively new
- The experiment results demonstrate the superiority of the proposed method over baselines.

Weaknesses:

- The solution provided is somewhat limited as it relies heavily on the structural properties of the mixture distribution and Gelbrich distance to reformulate the optimization problem.

Most of the reviewers voted initially for rejection. The paper is borderline, tending to rejection after the rebuttal. The authors have also considerably updated the paper with new results after the initial reviews. It seems therefore that the paper may benefit from another round of reviewing and, because of this, I recommend rejection and the authors to use the reviewers' comments to improve the paper before resubmitting to another venue for another round of reviewing.
Decision: Reject