Distributionally Robust Recourse Action
Authors: Duy Nguyen
Ngoc Bui
Viet Anh Nguyen
Venue: ICLR 2023 poster (2023)
Keywords: Robust Optimization
Explainable AI
Algorithmic Recourse

Abstract: A recourse action aims to explain a particular algorithmic decision by showing one specific way in which the instance could be modified to receive an alternate outcome. Existing recourse generation methods often assume that the machine learning model does not change over time. However, this assumption does not always hold in practice because of data distribution shifts, and in this case, the recourse action may become invalid. To redress this shortcoming, we propose the Distributionally Robust Recourse Action (DiRRAc) framework, which generates a recourse action that has high probability of being valid under a mixture of model shifts. We first formulate the robustified recourse setup as a min-max optimization problem, where the max problem is specified by Gelbrich distance over an ambiguity set around the distribution of model parameters. Then we suggest a projected gradient descent algorithm to find a robust recourse according to the min-max objective. We also show that our DiRRAc framework can be extended to hedge against the misspecification of the mixture weights. Numerical experiments with both synthetic and three real-world datasets demonstrate the benefits of our proposed framework over the state-of-the-art recourse methods, which generate robust recourses.


Published as a conference paper at ICLR 2023
DISTRIBUTIONALLY ROBUST RECOURSE ACTION
Duy Nguyen', Ngoc Bui', Viet Anh Nguyen?
VinAl Research, Vietnam
The Chinese University of Hong Kong
ABSTRACT
A recourse action aims to explain particular algorithmic decision by showing one specific way in which the instance could be modified to receive an alternate outcome. Existing recourse generation methods often assume that the machine learning model does not change over time. However, this assumption does not always hold in practice because of data distribution shifts, and in this case, the recourse action may become invalid. To redress this shortcoming, the Distributionally Robust Recourse Action (DiRRAc) framework, which gener- a recourse action that has a high probability of being valid under a mixture of model shifts. We formulate the robustified recourse setup as min-max opti- mization problem, where the max problem is specified by Gelbrich distance over ambiguity set around the distribution of model parameters. Then we suggest a projected gradient descent algorithm to find a robust recourse according to the min-max objective. We show that our DiRRAc framework can be extended hedge against the misspecification of the mixture weights. Numerical experiments with both synthetic and three real-worts datasets demonstrate the benefits of our proposed framework over state-of-the-ar recourse methods.
propose
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. Re- cently, recourse has been rising as attractive tool to diagnose why machine learning models have made a particular decision for given instance. A recourse action provides a possible modification of the given instance to receive alternate decision (Ustun al., (219).. Consider, for example, the case of loan approvals in which a credit application is rejected. Recourse will offer the reasons for rejection by showing what the application package should have been to get approved. A concrete example a recourse in this case may be "the monthly salary should be higher by S500" or "20% of the current debt should be reduced"".
recourse action has a positive, forward-looking meaning: they list out a directive modification that person should implement that they can get favorable outcome in the future. If a machine learning system can provide the negative outcomes with the corresponding recourse action, it can improve user engagement and boost the interpretability at the same time (Ustun al. 2019 Karimi et al. 20215). Explanations thus play a central role in the future development of human-computer interaction as well as 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 strike an intricate balance between conflicting criteria. First and foremost, recourse action should be feasible: if the prescribed action is taken, then the prediction of machine learning model should be flipped. Further, to avoid making dras- tic change to the characteristics of the input instance, framework for generating recourse should minimize the cost implementing the recourse action. An algorithm for finding recourse must make changes to only features that actionable and should leave immutable features (relatively) unchanged. For example, we must consider the date of birth as an immutable feature; in contrast, consider salary or debt amount as actionable features.
Various solutions have been proposed to provide recourses for model prediction Karimi et al.
202 Stepin et al. 2021 Artelt & Hammer 2019 Pawelczyk et al. 2021 2020 Verma et al.

---

Published as a conference paper at ICLR 2023
2020). For instance, [Ustun et al. (2019) used an integer programming approach to obtain actionable recourses and also provide a feasibility guarantee for linear models. Karimi et al. (2020) proposed a model-agnostic approach to generate the nearest counterfactual explanations and focus on structured data. Dandi et al. (020)) proposed a method that finds the counterfactual by solving a multi-objective optimization problem. Recently, [Russel] (2019) and Mothilal et al. (2020) focus finding set of multiple diverse recourse actions, where the diversity is imposed by a rule-based approach or by internalizing a 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 are 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 turn cause serious concerns for the feasibility of the recourse action in the future (Rawal et al. 2021b. 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 favorable outcome in the future, then the recourse action may become less beneficial /Venaatasubramanian & Alfano 2020). the pledge of a brighter outcome is shattered, and the trust in the machine learning system is lost (Rudin) 2019).
To tackle this challenge, Upadhyay et al. (202)) proposed ROAR, a framework for generating instance-level recourses that robust to shifts in the underlying predictive model. ROAR used a robust optimization approach that hedges against an uncertainty set containing plausible values of the future model parameters. However, it well-known that robust optimization solutions can be overly conservative because they may hedge against a pathological parameter in the uncertainty set (Ben-Tal Tal et al.) 2017 Roos & den Hertog 2020 A promising approach that can promote robustness while at the same time prevent from conservtsev is the distributionally robust op- timization framework (El Ghaoui al. 2003 Delage & Ye, 2010; Rahimian & Mehrotra 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. 2019)
Contributions. This paper combines ideas and techniques from two principal branches of explain- able artificial intelligence: counterfactual explanations and robustness to resolve the recourse prob- lem under uncertainty. Concretely, our main contributions are the following:
1. We propose the framework of Distributionally Robust Recourse Action (DiRRAc) for design- ing a recourse action that is robust to mixture shifts of the model parameters. Our DiRRAc maximizes the probability that the action is feasible with respect to a mixture shift of model parameters while at the same time confines the action in the neighborhood of the input instance. Moreover, the DiRRAc model also hedges against the misspecificatioo of the nominal distribu- tion using min-max form with mixture ambiguity set prescribed by moment information.
2. We reformulate the DiRRAc problem into diite-dimeeiional optimization problem with an explicit objective function. We also provide a projected gradient descent to solve the problem.
3. We extend our DiRRAc framework along several axis to handle mixture weight uncertainty, to minimize the worst-case component probability of receiving the unfavorable outcome, and also to incorporate the Gaussian parametric information.
We first describe the recourse action problem with mixture shifts in Section 2 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 discussed in Section 4 Section 5 reports the numerical experiments showing the benefits of the DiRRAc framework and its extensions.
Notations. For each integer K, we have [K] = {1...., .....,,K K}. We use S (S$ to denote the space of symmetric positive semidefinite (definite) matrices. For any A E Rm the trace operator is Tr A = Di= Ai If a distribution Qu has mean μı and covariance matrix Σx. we write Q ~ (14, mx). ) If additionally Qe is Gaussian, we write Q ~ [(4 Σx). Writing Q ~ (Qu.Pe) pe)ke[K] means Q is mixture of K components, the k-th component has weight pa and distribution Qc.
2

---

Published as a conference paper at ICLR 2023
2 RECOURSE ACTION UNDER MIXTURE SHIFTS
We consider a 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 : I2 + characterized by the d-dimensional parameter 0 is of the form
Co(a) = {
if x 0.
otherwise.
Note that the bias term can be internalized into 9 by adding an extra dimension, and thus it omitted.
Suppose that at this moment (t 0), the current classifier is parametrized by O. and we given an input instance To E gd with unfavorable outcome, that is, Co, (zn) = O. One period time from now (t 1), the parameters of the predictive model will change stochastically and represented by d-dimensional random vector 0. This paper focuses finding recourse action which is reasonably close to the instance zp, and at the same time, has a high probability of receiving a favorable outcome in the future. Figure gives bird's eye view of the setup.
Now
Future
0
t=
Time
Current classifier:
Oo
Future classifier: ~ (fe, Ex, Pu)se[]
Input: za with Co, (xa)
Counterfactual:
Figure I: A canonical setup of the recourse action under mixture shifts problem.
To measure the closeness between the action æ and the input zo. we assume that the covariate space endowed with a non-negative, continuous cost function c. In addition, suppose temporarily that follows distribution P.. Because maximizing the probability of the favorable outcome is equivalent minimizing the probability of the unfavorable outcome, the recourse can be found by solving
min (P(c(()) 0) E X, a(x, <
(1)
The parameter 8 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 (T) governs how far a recourse action can be from the input instance Tp-
In this paper, we model the random vector 0 using finite mixture of distributions with K com- ponents, the mixture weights are p satisfying Σve[K] Pr = 1. Each component in the mixture represents specific type of model shifts: the weights p reflect the proportion of the shift types while the component distribution PA represents the (conditional) distribution of the future model parameters in the k-th shift. Further information machine learning can be found in (Murphy 2012, $3.5). Note that the mixture model is not strong assumption. It is well-known that the Gaussian mixture model is universal approximator of densities, the sense that any smooth density can be approximated with any specific nonzero amount of error by a Gaussian mixture model with enough components (Goodfellow et al. 2016 McLachlan & Peel 2000). Thus, our mixture models are flexible enough to hedge against distribu- tional perturbations of the parameters under large values of K. The design of the ambiguity set to handle ambiguous mixture weights and under the Gaussian assumption is extensively studied in the literature distributionally robust optimization (Hanasusanto al. 2015 Chen & Xie 2021).
mixture distributions and their applications
If each fy Gaussian distribution ((,,, Σx), then IP is a mixture of Gaussian distributions. The objective of problem can be expressed as
0g
P(C,(x) 0) 0)= Σ P=)
Σ P
kE[K]
RE(K]
Ex
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 (T) using a projected gradient descent type of algorithm (Boyd & Vandenberghe, 2004).
3

---

Published as a conference paper at ICLR 2023
Remark 2.1 (Nonlinear models). Our analysis focuses linear classifiers. which is common setup in the literature (Upadhyay et al. 2021 Ustun et al. 2019 Rawal et al. [021 Karimi et al. 2020 Wachter al. 2018 Ribeino et al. 2016). To extend to nonlinear classifters. we can follow a similar approach as in Rawal & Lakkarajuu (020b) and Upadhyay et al. (2027) by first using LIME Ribeiro et al.) (2016) approximate the nonlinear classifiers locally with an interpretable linear model, then subsequently applying our framework.
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 iPx are specified only through moment information, and no particular parametric form of the distribution is imposed. In effect, P& assumed to have mean vector 0g E Ed and positive definite covariance matrix Σx > O. Second, we leverage ideas from distributionally robust optimization to propose a min-max formulation of []. in which consider an ambiguity set which contains a family of probability distributions that are sufficiently close to the nominal distribution P. We prescribe the ambiguity set using Gelbrich distance (Gelbrich 1990).
Definition 3.1 (Gelbrich distance). The Gelbrich distance between two tuples (6, E) E Rd S
and (Ø, Σ) E Rd x 84 amounts to G((0, E), (0, En V110 012 + Tr Σ + E 2 2 )
It is easy verify that G is non-negative, symmetric and it vanishes zero if and only if (0, - (0 E). Further, G a distance on Rd x s because it coincides with the type-2 Wasser- stein distance between two Gaussian distributions ((u, Σ) and (i, Σ) (Givens & Shortt 1984). Distributionally robust formulations with moment information prescribed by the G distance are 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 Nguyen et al.) 2021).
In this paper, we use the Gelbrich distance G form a neighborhood around each Ps
B& (PA) & Q : Qu ~ (0,, Ex), G((0s. Ex), (0.. Ex)) S Pt)
Intuitively, one can view BR (PA) as a ball centered at the nominal component P& of radius Pk: 2 0 prescribed using the distance G. This component set (Pxx) is non-parametric, and the first two moments of Q2 are sufficient decide whether Qx belongs (Px). Moreover, if Qs Bx (Pxx), then any distribution Q% 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 (PPx) does not collapse into singleton. Instead, if P = then (Pxs) still contains all distributions of the same moment (0,, Ex)) with the nominal component distribution Prx, 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) {Q: 3Qu E B& (Px) Vk E [K] such that Q (Qk, kEjK }
Any Q E B(P) is also mixture distribution with K components, with the same mixture weights p. Thus, B(P) contains all perturbations of IP induced separately on each component by (Px))
We are now ready to introduce our DiRRAc model, which is a min-max problem of the form
inf ZEX
sup Q(Cp(x) 0) QEB(F)
8. L.
c(x,
< 5
(2)
sup Qu (Cg(x) 0) <1 (fx)
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
4

---

Published as a conference paper at ICLR 2023
probability of unfavorable outcome should be strictly less than Put differently, this last straint requires that the action should be able to lead to favorable outcome for any distribution in
By (Px). By definition, each supremum subproblem in (2) is an crinite-dimensione. maximization problem over the space of probability distributions, and thus is inherently difficult. Fortunately, because we use the Gelbrich distance to prescribe the set By ), we can solve these maximization problems analytically. This consequentially leads to closed-form reformulation of the DiRRAc model into a dimeessaieiii problem. Next, we will reformulate the DiRRAc problem 2 pro- vide sketch of the proof and propose numerical solution routine.
3.1 REFORMULATION OF DIRRAC
Each supremum in (2) is an infinitedimmnsiinnal optimization problem on the space of probability distributions. We now show that (2) can be reformulated as fnite-dimensional problem. Towards this end, let X' be the following d-dimensional set.
X f X:: c(2, z0) 8, -0 +
Ak E
[K] }-
The next theorem asserts that the DiRRAc problem (2) can be reformulated as a d-dimensional optimization problem with an explicit, but complicated, objective function.
Theorem 3.2 (Equivalent form of DiRRAc). Problem 2 equivalent to the finite-dimensional optimization problem
inf ZEX
Σ pxfu(z)? kE[K]
where the function fur admits the closed-form expression
fx(z) pr0 a.1f + V EaaV 10 (0]a)²
xT F.gg
p 1=111
x) + x T Σtx
Next, we sketch proof of Theorem 3.2 and solution procedure to solve problem
3.2 PROOF SKETCH
For any component & E [K], define the following worst-case probability of unfavorable outcome
fa( sup (C((((x) 0) sup Q (P..
@o x S 0) vk E [K].
(5)
(P.).
To proceed, we rely the following elementary result from Nguyen 2019 Lemma 3.31).
Lemma 3.3 (Worst-case aalue-at-Risk) For any x E Rd and 3 E (0, 1). we have
-T) -1) ] = 0 + / - /1 V V
inf
sup (P.)
Qu(OT -
vB
Pk
|2l122
(6)
Note that the left-hand side of (6 is the worst-case Value-at-Risk with respect to the ambiguity set
B& (Pxx). Leveraging this result, next proposition provides the analytical form of fa (x). Proposition 3.4 (Worst-case probability). For any h E [K] and (0x, Ex,, Pk) E Rd x s x R4,
define the following constants A A 0% Bx A / x Esz, and Cs & pxl1=|12. We have
if + 2 0, E (0,1) A + C 0.
fe(x)
sup (P.)
@A 5 0)
AcCo+ A
B
C2
2
A
The proof of Theorem 3.2 follows by noticing that the DiRRAc problem ( can be reformulated using the elementary functions fs as
min
Pafa(z) : c(x, 56, fa(x) <1 4k [K]
ZEX
KE[K]
5

---

Published as a conference paper at ICLR 2023
where the objective function follows from the definition of the set ((P). It suffices to combine with Proposition 3.4 to obtain the necessary result. The detailed proof is relegated to the Appendix. Next propose projected gradient descent algorithm to solve the problem
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 First, notice that the second constraint that defines in (3) a strict inequality, thus the set X' is open. We thus modify slightly this constraint by considering the following set
X = x x xo) S 6, 0g x + pæ||=|12 S - Vk E [K]}
for some value > O sufficiently small. Moreover, if the parameter 8 is too small, it may happen that the set X₂ becomes empty. Define δmin E 1R, as the optimal value of the following problem
inf (((2,0)) E - -0 + pull=l12 S - Ak [K]].
Then it easy to see that X. is non-empty whenever ò 2 6min In addition, because c is continuous and X is closed, the set X is compact. In this case, we can consider problem (4) with the feasible set being Xe, for which the optimal solution is guaranteed to exist. Let us now define the projection operator Projx, as Projx, (a') & min { [||z x'13 z E X²). If X is convex and z0) is a convex function, then X is also convex, and the projection operation can be efficiently computed using convex optimization.
In particular, suppose that c(2,, 20) 20lla representable, then the projection is equivalent to a second- order cone program, and can be solved Mosek (MOSEK
zolla is the Euclidean norm and X is second-order cone
using off-the-shelf solvers such as GUROBI Gurobi Optimization, LLC (2021) ApS 2019). The projection operator Projx, now forms the building block of a projected gradient descent algorithm with a backtracking linesearch. The details regarding the algorithm, along with the convergence guarantee, are presented in Appendix B
To conclude this section, we visualize the geometrical intuition of our method in Figure 2
The feasible set X' in 3 is shaded in blue. The circular are represents the proximity boundary 2(2),00) 8 with being an Euclidean distance. Dashed lines represent the hyperplane -0 x = O for different k. while elliptic curves represent the robust margin - x + Pi ||=|||| 0 with matching color. In- creasing the ambiguity size as brings the elliptic curves towards the top-right corner and farther away from the dash lines. The set X' taken as the intersection of ellip- tical and promixity constraints will move deeper into the interior of the favorable prediction region, resulting in more robust recourses.
Figure 2:
Xpro
X
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 F& are Gaussian for all k [K]. and we will robustify against only the misspecification of the nominal mean vector and covariance matrix (0k, 5x). To do this, we first construct the Gaussian component ambiguity sets
Vk
(Px) A {Qu Qu ~ AoOO,, Ex), G((,,, Ex), (Øz, Ex)) S Pk: }.
where the superseript emphasizes that the ambiguity sets are neighborhoods in the space of Gaussian distributions. The resulting ambiguity set for the mixture distribution is
N QQ= JQu E B. (Pxx) Vk E [K] such that Q ~ (Qu, (Qt.PF)RE(K))

---

Published as a conference paper at ICLR 2023
The Gaussian DiRRAc problem is formally defined as
min T
sup QEBN c(z, ro) I
Q(Cg(z) 0)
S. t.
sup QuEBY (f.)
(C((((z) - 0) <
Vk E [K].
we 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 & instead of 1 as in the DiRRAc problem (2). The detailed reason will be revealed in the proof sketch in Section 4.2
Similar to Section 3
4.1 REFORMUL.ATOON OF GAUSSIAN DIRRAC
Remind that the feasible set X' is defined in (3. The next theorem asserts the equivalent form of the Gaussian DiRRAc problem (8.
Theorem 4.1 (Gaussian DiRRAc reformulation). The Gaussian DiRRAc problem ( is equivalent
the fiite-dimensionn optimization problem
min REX
(ox)))
KE[K]
where the function gb. admits the closed-form expression
(0 x)2 - -
9h (2)
0% TooV Enx + Pk pall=112 (0 x:2 + x T o 1=
Problem ( can solved using the projected gradient descent algorithm discussed in Section 3.3
4.2 PROOF SKETCH
The proof of Theorem relies the following analytical form of the worst-case Value-at-Ree Risk (VaR) under parametric Gaussian ambiguity set (Nguyen) 2019 Lemma 3.31).
Lemma 4.2 (Worst-case Gaussian VaR). For any E Rd and 3 (0, }.. lest = 2 2-1(1-11 101-3) 3). Then
{ { T: sup CLEBY
inf
Qu( S - 07 x + + xT
I Ee pVl++1 + 11 (10)
important to note that Lemma 4.2 is only valid for 3 E 00,..5). Indeed, for 1. evaluat- ing the infimum problem in the left-hand side of (10) requires solving non-convex optimization problem as = +- 4 3) < 0. As a consequence, the last constraint of the Gaussian DiRRAc formulation is capped at probability value of 0.5 to ensure the convexity of the feasible set the reformulation (9). The proof of Theorem follows a similar line of argument as for the DiRRAc formulation, with 9k being the worst-case Gaussian probability
gl. (x)
sup Q&EBY (Fx)
QA (C((x) = 0)=
sup QLEBY (Px)
@o x x50)
Wk: E [K].
To conclude this section, we provide a quick sanity check: by setting K = and P1 = 0. we have a special case in which 0 follows a Gaussian distribution ((,r,E,) Thus, 0 ~ _N[ x. Σ1x) and it easy to verify from the formula of Ø1 in the statement of Theorem 4.1 that 91 (x)
(ŌT <x)(x E1z),, which recovers the value of Pr(0") S 0) under the Gaussian distribution.
5 NUMERICAL EXPERIMENTS
We compare extensively the performance of our DiRRAc model 2 and Gaussian DiRRAc
model (8) against four strong baselines: ROAR (Upadhyay al. 2021) CEPM (Pawelczyk al.
7

---

Published as a conference paper at ICLR 2023
2020), AR (Ustun al. 2019) and Wachter (Wachter et al. 2018 We conduct the experiments on three real-world datasets (German, SBA, Student). Appendix
provides further comparisons with more baselines: Nguyen et al. (2022), KKrimi et al. a022aa and ensemble variants of ROAR, along with the sensitivity analysis of hyperparameters. Appendix also contains the details about the datasets and the experimental setup.
Metrics. For all experiments, we use the I distance c(z, Øn) = - as the cost function. Each dataset contains two of data (the present and shifted data). The present data is to train the current classifier for which recourses are generated while the remaining data is used to measure the validity of the generated recourses under model shifts. We choose 20% of the shifted data randomly 100 times and train 100 classifiers respectively. The validity of recourse is computed as the fraction of the classifiers for which the recourse valid. We then report the average of the validity of all generated recourses and refer this value as M2 validity. We also report Mi validity, which is the fraction of the instances for which the recourse is valid with respect the original classifier.
Results on real-world data. We use three real-world datasets which capture different data distri- bution shifts (Dua & Graff 2017): (i) the German credit dataset, which captures a correction shift. (ii) the Small Business Administration (SBA) dataset, which captures temporal shift. (iii) the Stu- dent performance dataset, which captures a geospatial shift. Each dataset contains original data and shifted data. We normalize all continuous features to [0, 1]. Similar to Mothilal et al. (2020). use one-hot encodings for categorial features, then consider them as continuous features in 0, To ease the comparison. we choose K 1. The choices of K are discussed further in Apnendix A Student
German
SBA
1.0
1.0
1.0
Ma validity
0.9
0.9
0.9
0.8
0.8
0.8
0.7
0.7
3
1.0
1.5
2.0
2.5
3.0
1.0
1.5
2.0
4 cost
1 cost
1 cost
DiRRAc
ROAR
Figure 3: Comparison of M2 validity as a function of the I distance between input instance and the recourse for our DiRRAc method and ROAR on real datasets.
Table 1: Benchmark of Mj and M2 validity, 1 and l2 cost for linear models on real datasets.
Dataset
Methods
Mi validity
M2 validity
cost
12
German
AR
1.00 + 0.00
0.76 + 0.26
0.61 + 0.40
0.43 + 0.25
Wachter
1.00 0.00
0.82 0.24
0.81 + 0.51
0.41 + 0.25
CEPM
1.00 0.00
0.83 0.38
1.30
1.02 + 0.04
ROAR
1.00 1 0.00
0.94 0.94
3.88 1 0.54
1.61 1 0.22
DiRRAc
1.00 1 0.00
0.99 0.06
1.62 0.30
1.25 1 0.21
Gaussian DiRRAc
1.00 = 0.00
0.99
1.62 0.30
1.05 = 0.23
SBA
AR
1.00 + 0.00
0.41 + 0.18
0.61 0.42
0.56 1 0.36
Wachter
1.00 1 0.00
0.55 0.22
2.30
0.77
CEPM
1.00 0.00
0.94
5.30
2.18 = 0.02 0.02
ROAR
1.00 = 0.00
0.00
3.70
1.35 + 0,30
DiRRAc
1.00 + 0.00
0.00
1.74
1.34 = 0,40
Gaussian DiRRAc
1.00 + 0.00
0.99 109+0000
1.60 0.62
0.98 + 0.42
Student
AR
1.00 + 0.00
0.29 0.21
0.26 - 0.18
Wachter
1.00 + 0.00
0.60
0.30 - 0.22
CEPM
1.00 + 0.00
0.15
4.02
2.03 + 0.01 0.01
ROAR
1.00 + 0.00
0.14
2.32
0.96 - 0.18
DiRRAc
1.00 + 0.00
0.95 0.09
1.55
+
1.07 + 0.23
Gaussian DiRRAc
1.00 1 0.00
0.74 0.18
0.78
1 0.30
0.54 T 0.21
We split 80% of the original dataset and train logistic classifier. This process is repeated 100 times independently to obtain 100 observations of the model parameters. Then we compute the empirical mean and covariance matrix for (0, Σn) ). To evaluate the trade-off between cost and M2 validity of DiRRAc and ROAR, compute / cost and the M2 validity by running Ai with varying
8

---

Published as a conference paper at ICLR 2023
values of dadd and ROAR with varying values of X. We define 8 = 6min + Sadd: Smin is specified in (7). Figure 3 shows that the frontiers of DiRRAc dominate the frontiers of ROAR. This indicates that DiRRAc achieves a far smaller / cost for the robust recourses than ROAR. Next, we evaluate the 1 and la cost, M, and M2 validity of DiRRAc, ROAR and other baselines. The results in Table demonstrate that DiRRAc Ac has high validity in all three datasets while preserving low costs (4 and l2 cost) in comparison to ROAR. Our DiRRAc framework consistently outperforms the AR, Wachter, and CEPM in terms of M2 validity.
Nonlinear models. Following the previous work as in Rawal et al. (2021) : Upadhyay et al. (2021) and Bui et al. (202)). we adapt our DiRRAc framework and other baselines (AR and ROAR) to non-linear models by first generating local linear approximations using LIME (Ribeiro et al. 2016). For each instance zo, we first generate local linear model for the MIPs classifier 10 times using
LIME, each time using 1000 perturbed samples. To estimate (01. Σn), we compute the mean and covariance matrix of parameters 8z, of 10 local linear models. We randomly choose 10% of the shifted dataset and concatenate with training data of the original dataset 10 times, then train a shifted MLPs classifier. According Table 2 On the German Credit and Student dataset, DiRRAc has higher M2 validity than other baselines, and a slightly lower M2 validity on the SBA dataset than ROAR, while maintaining low 1 cost relative ROAR and CEPM.
Table 2: Benchmark of M1 and M2 validity, 1 and l2 cost for non- non-linear models on real datasets.
Dataset
Methods
M1 validity
M2 validity
I cost
l cost
German
LIME-AR
0.72 + 0.45
0.71 + 0.27
1.05 0.20
1.00 0.03
Wachter
1.00 + 0.00
0.55 + 0.42
0.20 + 0.26
0.11 + 0.16
CEPM
1.00 = 0.00
0.74 0.40
1.30
1.02 : 0.00
LIME-ROAM
0.60 = 0.49
0.69
2.52
1,25 0.07
LIME-DiRRAo
0.78 188:044 0.42
1.02 1.24 0.27
LIMF-Gaussian DiRRAc
0.70 0.46
0.70
1.11
1.00
SBA
LIME-AR
0.65
0.60 0.49
0.23
0.233
Wachter
1.00
0.61
0.09
CEPM
1.00
0.40
0.01
1.42 +.00
AME-ROAR
0.97
0.97
0.36
0.93 0.26
0.93
1.10
1.07 0.05
LIME-Gaussinn DiRRAc
0.82 1 0.38
0.80 0.38
0.64 0.29
0.43 0.32
Student
LIME-AR
0.66 + 0.48
0.53 0.53 0.45
0.37 0.32
Wachter
1.00 0.00
0.43
0.20
0.20 0.14
CEPM
1.00 + 0.00
0.40
4.51
2.03 0.01
LIME-ROAR
0.97 + 0.18
+ 0
6.10
1.97 0.16
LIME-DiRRAc
0.97 + 0.18
0.97 1.12 0.18
1.12 +
LIME- -aaE-GGassiinn DIRRAC
0.69 1 0.46
0.59 0.46
0.58 0.54
0.50 1 0.51
Concluding Remarks. In this work, proposed the Distributionally Robust Recourse Action (DiRRAc) framework to address the problem of recourse robustness under shifts in the parame- ters of the classification model. We introduced distributionally robust optimization approach for generating a robust recourse action using a projected gradient descent algorithm. The experimental results demonstrated that our framework has the ability to generate the recourse action that has high probability of being valid under different types of data distribution shifts with a low cost. We also showed that our framework can be adapted different model types, linear and non-linear models, and allows for actionability constraints of the recourse action.
Remark 5.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
Remark 5.2 (Choice of ambiguity set). This paper's results rely fundamentally on the design of ambiguity sets using Gelbrich distance on the moment space. This Gelbrich ambiguity set leads to the I|- reguaaraaaaso of the worst-case Value-at- -is- in Lemmas 3.3 and 4.2 If consider other moment ambiguity sets, for example, the moment bounds in Delage & Ye (2010) the Kullback- Leibler-rype rype sets in Taskesen et al. (202T), then these regularization equivalence are not available, and there is no trivial way extend the results to reformulate the (Gaussian) DiRRAc framework.

---

Published as a conference paper at ICLR 2023
Acknowledgments. Viet Anh Nguyen acknowledges the generous support from the CUHK's Im- provement on Competitiveness in Hiring New Faculties Funding Scheme.
REFERENCES
André Artelt and Barbara Hammer. On the computation of counterfactual explanations A survey. arXiv preprint arviv: 1ee..19111.... 2019.
G. Bayraksan and D. K. Love. Data-driver 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 optimization problems affected by uncertain probabilities. Management Sci- ence, 59(2):31--377, 2013.
Aharon Ben-Tal, Tal, Ruud Brekelmans, Dick den Hertog, and Jean-Philippe Vial. Globalized robust optimization for nonlinear uncertain inequalities. INFORMS Journal on Computing, 29(2):350- 366, 2017.
D. Bertsimas, Gupta, and N. Kallus. Data-driven robust optimization. Mathematical Program- ming, 167(2):235-292, 2018.
Emily Black, Zifan Wang, and Matt Fredrikson. Consistent counterfactuals for deep models. In International Conference on Learning Representations, 2022. URL Bttphtsts///opeee/iiee
S. Boyd and Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Ngoc Bui, Duy Nguyen, and Viet Anh Nguyen. Counterfactual plans under distributional ambiguity. In International Conference on Learning Representations, 2022.
Zhi Chen and Weijun Xie. Sharing the value-at-risk under distributional ambiguity. Mathematical Finance, 31(55:331-559, 2021.
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 on 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 htttttttp///cchie
ics. uci. edu/ml
John C Duchi, Peter Glynn, and Hongseok Namkoong. Statistics of robust optimization: A generalized empirical likelihood approach. Mathematics of Operations Research, 2021.
L. El Ghaoui, M. Oks, and F. Oustry. Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Operations Research, 51(4):543-556 2003.
Stanislav Fort, Huiyi Hu, and Balaji Lakshminarayanan. Deep ensembles: A loss landscape per- spective. arXiv preprint arXiv:1912.0275: 2019.
M. Gelbrich. On formula for the L Wasserstein metric between measures on Euclidean and Hilbert spaces. Mathematische Nachrichten, 147(1):185-033 1990.
C.R. Givens and R.M. Shortt. A class Wasserstein metrics for probability distributions. The Michigan Mathematical Journal, 31(2):231-240, 1984.
10

---

Published as a conference paper at ICLR 2023
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. URL https://wwa/ gurobi com
G.A. Hanasusanto, D. Kuhn, S. W. Wallace, and S. Zymler. Distributionally robust multi-item newsvendor problems with multimodal demand distributions. Mathematical Programming, 152 (1-2):1-32, 2015.
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:1905. 2020.
Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: From counter- factual explanations to interventions. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, FAccT '21, pp. 353-362, 2021a.
Amirhossein Karimi, Bernhard Schölkopf, and Isabel Valera. survey of algorithmic recourse: Contrastive explanations and consequential recommendations. arXiv preprint arXiv:2010.04050, 2021b.
David Ketchen and Christopher L Shook. The application of cluster analysis in strategic manage- ment research: an analysis and critique. Strategic Management Journal, 17(6):44 1-458, 1996.
D. Kuhn, P. Mohajerin Esfahani, V.A. Nguyen, and S. Shafiezzadeh-Abadeh. Wasserstein distribu- tionally robust optimization: Theory and upplications in 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.
Geoffrey J. McLachlan and David Peel. Finite Mixture Models, volume 299 of Probability and Statistics Applied Probability and Statistics Section. Wiley, New York, 2000.
MOSEK ApS. MOSEK Optimizer API for Python 9.2.10, 2019, URL https:://ddo
com/ 9. 2/ httpp/ttooaa//inneeeeeeeeeeeeeee inneexxppiiiixx...iim mtml
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.
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.
Tuan-Duy H Nguyen, Ngoc Bui, Duy Nguyen, Man-Chung Yue, and Viet Anh Nguyen. Robust Bayesian recourse. In Uncertainty in Artificial Intelligence, pp. 1498-1508. PMLR, 2022.
Viet Anh Nguyen. Adversarial Analytics. PhD thesis, Ecole Polytechnique Fédérale de Lausanne, 2019.
Viet Anh Nguyen, Soroosh Shafieezadeh Abadeh, Damir Filipovic, and Daniel Kuhn. Mean- covariance robust risk measurement. arXiv preprint arXiv:21 2021.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley. Sebastian Nowozin, Joshua Dillon, Balaji Lakshninarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. Advances in neural information processing systems, 32, 2019.
Leandro Pardo. Statistical Inference Based Divergence Measures. CRC Press, 2018
11

---

Published as a conference paper at ICLR 2023
Martin Pawelczyk. Klaus Broelemann, and Gjergji Kasneci. On counterfactual explanations under predictive multiplicity. In UAI, 2020.
Martin Pawelczyk, Sascha Bielawski, Johannes van den Heuvel, Tobias Richter, and Gjergji Kas- neci. CARLA: A Python library to benchmark algorithmic recourse and counterfactual explana- tion algorithms. arXiv preprint arXiv:2108.0078. 2021.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv:I908.08:
2019.
Kaivalya Rawal and Himabindu Lakkaraju. Beyond individualized recourse: Interpretable and inter- active summaries of actionable recourses. Advances in Neural Information Processing Systems, 33:12187-12198, 2020a.
Kaivalya Rawal and Himabindu Lakkaraju. Beyond individualized recourse: Interpretable and in- teractive summaries of actionable recourses. arXiv preprint arXiv:2009.07165. 2020b.
Kaivalya Rawal, Ece Kamar, and Himabindu Lakkaraju. Algorithmic recourse the wild: Under- standing the impact of data and model shifts. arXiv preprint arXiv:2012..1788, 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. pp. 1135- 1144, 2016.
Ernst Roos and Dick den Hertog. Reducing conservatism in robust optimization. INFORMS Journal Computing, 32(4): 109-1127, 2020.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-215, 2019.
Chris Russell. Efficient search for diverse coherent explanations. In 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 1974-12000,, 2021.
Bahar Taskesen, Man-Chung Yue, Jose Blanchet, Daniel Kuhn, and Viet Anh Nguyen. Sequential domain adaptation by synthesizing distributionally robust experts. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Robert L Thoondike Who belongs in the family. In Psychometrika. Citeseer, 1953.
Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorith- mie recourse. 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, Accountabllity 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 on Fairness, Accountability, and Transparency. FAT '20, pp. 284-293, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450369367.
doi: 10.1145/3350055.332228 9351095.337287
URL https:://ci.ors
1145/
Sahil Verma, Varich Boonsanong, Minh Hoang, Keegan E. Hines, John P. Dickerson, and Chirag Shah. Counterfactual explanations and algorithmic recourses for machine learning: A review, abs 10....10000
2020. BRLLittts:://axxtaa
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.
12

---

Published as a conference paper at ICLR 2023
A ADDITIONAL EXPERIMENT RESULTS
Here, we provide further details about the datasets, experimental settings, and additional results. Source code can be found
A.1 DATASETS
Real-world datasets. We use three real-world datasets which are popular in the settings of ro- bust algorithmic recourse: German credit (Dua & Graff 2017). SBA Li et al. (2018), and Student performance Cortez & Silva (008). We select a subset features from each dataset:
For the German credit dataset from the UCI repository, we choose five features: Status, Dura- tion, Credit amount, Personal Status, and Age. We found in the descriptions of two datasets that feature Status in the data correction shift dataset corrects the coding errors in the original dataset (Dua & Grafi 2017).
For the SBA dataset, we follow et al. 2018) and Upadhyay et al. (202T) and we choose 13 features: Selected, Term, NoEmp, CreateJob, RetainedJob, UrbanRural. ChgOtiPrinGr, GrAppv, SBP_Appv, New, RealEstate, Portion, Recession. We use the instances during 1989-2006 as original data and the remaining instances as shifted data.
For the Student Performance dataset, motivated by Cortez & Silva (2008), choose G3 final grade for deciding the label pass or fail for each student. The student who has G3 < 12 is labeled 0 (failed) and (passed) otherwise. For input features, choose 9 features: Age, Study time, Famsup, Higher, Internet, Health, Absences, GI, G2. We separate the dataset into the original and the geospatial shift data by different schools.
We report the accuracy of the current classifiers and shifted classifiers for two types of models: logistics classifiers (LR) and MLPs classifiers (MLPs) each dataset in Table 3
Table 3: Accuracy of the underlying classifiers.
Dataset
Methods
Accuracy
German
LR
0.72 + 0.00
MLPs
0.76 =
Shifted German
LR
0.7 0.00
MLPs
0.72
SBA
LR
0.09
MLPs
0.93
Shifted SBA
LR
0.77 + 0.01
MIPs
0.89 +
Student
LR
0.84 184+0001
MLPs
0.91 0.01
Shifted Student
LR
0.91 0.00
MLPs
0.99 0.01
Synthetic data. We synthesize two-dimensional data and simulate the shifted data by using K different shifts similar to Upadhhyy et al. (202T): : mean shift, covariance shift, mean and covariance shift. First, we fix the unshifted conditional distributions with X|Y y N (My, Eyy) Vy E V For mean shift, replace No by whiit 04 + [a, where is
shift magnitude. For covariance shift, we replace No by > = (1 (1--0) 3) where a covariance shift magnitude. For mean and covariance shift, replace (Jo, En) by (righnn Eghin) We generate 500 samples for each class from the unshifted distribution with foo = -: 3). #1 [3; 3], and Σn = Σn II
To visualize the decision boundaries of the linear classifiers for synthetic data, synthesize the shifted data in total 100 times including 33 mean shifts, 33 covariance shifts and 34 both shifts, then visualize the 100 model's 's parameters in tvo-dimensional space in Figure and Figure
13

---

Published as a conference paper at ICLR 2023
10
10
10
R
0
-5-
-10
-10
-10
10
10
-10
10
(a) Original data
(b) Mean shift
Covariance shift
(d) Both shift
Figure 4: Synthetic data shifts and the corresponding model parameter shifts (decision boundaries).
2.75
Original
2.50
Mean
Cov shift
2.25
Both shit
2.00
1.75
1.50
1.25
1.00
0.6
1.0
1.2
1.4
1.6
1.8
2.0
0g
Figure 5: Parameter of the classifier with different types of data distribution shifts.
A.2 EXPERIMENTAL SETTINGS
Implementation details. For all the baselines. we use the implementation CARLA (Pawelezyk et al. 202T). We use the hyperparameters of AR, Wachter and CEPM that are provided by CARLA. For ROAR, we use the same parameters as ROAR (Upadhyay et al., (02T).
Experimental settings. The experimental settings for the experiments in the main text are as fol- lows:
In Figure we fix P1 0.1 and vary 8add E [0, for DiRRAc. Then we fix 6max 0.1 and vary E 0.01, 0.2] for ROAR.
In Table and Table 2 we first initialize
0.1 and we choose the &ada that maximizes the M, validity. We follow the same procedure as the original paper for ROAR (Upadhyay al.,
2021): choose ômax = 0.1 and find the value of À that maximizes the Mj validity. The detailed settings are provided in Table
Table 4: Parameters for the experiments with real-world data in Table
Parameters
Values
K
1
8ada
1.0
P
[1]
[0.1]
0.7
C
1
14

---

Published as a conference paper at ICLR 2023
Choice of number of components K for real-world datasets. To choose K for real-world datasets, we use the same procedure in Section to obtain 100 observations the model parameters. Then determine the number of components K these observations using K-means clustering and Elbow method (T'horndike) [953] Ketchen & Shook) 1996). Then we train a Gaussian mixture model on these observations and obtain Pk. On. Eg for the optimal number of components K. The Elbow method visualization for each dataset is shown in Figure
German
SBA
Student
Desortion
17a
components
components
components
Figure 6: Elbow method for determining the optimal number of components for parameter shifts.
Dashed lines represent the optimal for three real-world datasets. German Credit: Elbow at K 5.
SBA: Elbow K 4. Student Performace: Elbow at K 6.
Table 5: Performance of DiRRAc and Gaussian DiRRAc with K components on three real-world datasets.
Dataset
Methods
Mi validity
M2 validity
4 cost
l2 cost
German
DiRRAc (K- 5)
1.00 + 0.00
0.99 + 0.07
1.73 + 0.31
1,40 + 0.20
Gaussian DiRRAc (K-
1.00 0.00
0.99 = 0.07
1.73 = 0.31
1.23 = 0.23
SBA
DiRRAc (K- 4)
1.00 + 0.00
1.00 + 0.00
1.83 = 0.49
1.48 + 0.29
Gaussian DiRRAc (K-
1.00 0.00
0.99 1 0.02
1.67 0.68
0.98 : 0.42
Student
DiRRAc (K- 6)
1.00 + 0.00
0.96 + 0.09
1.59 = 0.33
1.04 = 0.22
Gaussian DiRRAc (K
1.00 0.00
0.75 + 0.19
0.82 0.30
0.53 0.21
The results in Table indicate that as we deploy our framework with the optimal number com- ponents K, then DiRRAc delivers smaller cost in all three datasets. DiRRAc slightly increases in the Student Performance dataset.
The M2 validity of Gaussian
Sensitivity analysis of hy pyprraaraeetess dadd and Pk. Here analyze the sensitivity of the hyperparameters dadd and Pk to the I cost of recourses and M2 validity of DiRRAc.
From the results in Figure of the recourse increase.
observe that 5add increases, both the cost and the robustness
We study the sensitivity of hyperparameters Pk M2 validity by first fixing the Sadd 0.1 and vary Pk: E [0.0, 0.5). According to Figure 7 we can observe that as Ps increases, the cost of recourses rises well, yielding in more robust recourses.
15

---

Published as a conference paper at ICLR 2023
German
SBA
Student
1.1
0.6
11 cost
0.5
0.8
0.8
0.4
0.6
0.2
0.2
0.4
M2 validity
0.95
0.65
0.90
0.8
0.55
0.7
pk
Pk
Pk
Figure 7: Sensitivity analysis of hyperparameters Pk to l cost and M2 validity of DiRRAc.
A.3 RESULTS ON REAL-WORLD DATA
Experiments with prior on Σ. In some cases, we presume, we may not have access to the training data. We set 0 = Oo. where 0g is the parameters of the original classifier. Then we choose Σ; = r/ with r 0.1. We generate recourse for each input instance and compute the M1 validity using the original classifier and the M2 validity using the shifted classifiers. The results in T show that our methods produce the same performance while at the same time keeping I and l2 cost lower than ROAR in all three datasets.
Table Benchmark of Mj validity, M2 validity, l and l2 using 0, = 0o and Σx = 0.17 on different real-world datasets.
Datasct
Methods
Mi validity
M2 validity
1i cost
12 cost
German
ROAR
1.00 = 0.00
0.94 + 0.15
3.88 + 0.54
1.61 0.22
DiRRAc
1.00 = 0.00
0.96 + 0.07
1.48 + 0.39
1.34 + 0.41
Gaussian DiRRAc
1.00 + 0.00
0.99 + 0.06
1.58 + 0.29
1.35 + 0.24
SBA
ROAR
1.00 = 0.00
1.00 + 0.00
3.72
1.35 + 0.30
DiRRAc
1.00 = 0.00
1.00 0.00
0.37
1.27 : 0.30
Gaussian DiRRAc
1.00 + 0.00
1.00 + 0.00
1.64
1.25 0.26
Student
ROAR
1.00 + 0.00
0.94 0.10
2,02 0.38
0.96 1: 0.18
DiRRAc
0.06
1.19
1.47 0.13
Gaussian DiRRAc
1.00 = 0.00
0.88 + 0.14
1.18
0.26
0.82 - 0.18
Experiments with actionability constraints. Using two methods (DiRRAc and Gaussian DiRRAc) and the AR method (Ustun et al., 2019). we analyze how the actionability constraints affect the and validity of the recourse. We select subset of features from each dataset and define each feature as immutable or non-decreasing as follows:
In the German credit dataset, we select Personal status as an immutable attribute because it is challenging to impose changes in individual's status and sex. We view age as non-decreasing feature.
the SBA dataset, we select UrbanRural and Recession as two immutable attributes since will be difficult to change these features in the near future. RetainedJob is another feature that we view as non-decreasing.
In the Student Performance dataset, assume that student's Higher education would not change, and select higher education as an immutable feature. Age and Absences are considered non-decreasing.
16

---

Published as a conference paper at ICLR 2023
The above specifications are aligned with the existing numerical setup in algorithmic recourse Us tun et al., 2019; Rawal Lakkaraju 2020a).
For each dataset, run the process of generating the recourse action by adding constraints to the projected gradient descent algorithm. The experimental setup on three different real-world datasets the same as in Section
The results in Table 7 indicate that the My validity of our methods drops in the German Credit dataset. The validity in shifted data of AR also decreases in this dataset. In other datasets, the performance of our 2 methods remains the same. The I and l2 cost of DiRRAc slightly increase in the Student Performance dataset. Furthermore, there exists recourse for every input instance.
Table 7: Benchmark of M1 validity, M2 validity, 4 and using actionability constraints on different real-world datasets.
Dataset
Methods
Mi validity
M2 validity
cost
cost
German
AR
1.00 + 0.00
0.76 + 0.26
0.61 0.40
0.43 0.25
DiRRAc
1.00 1 0.00
0.99 1 0.06
1.62 0.30
1.27 0.20
Gaussian DiRRAc
1.00 + 0.00
0.99 1 0.06
1.62 + 0.30
1.09 + 0.24
SBA
AR
1.00 = 0.00
0.41 = 0.18
0.61 = 0.42
0.56 + 0,36
DiRRAc
1.00 - 0.00
1.00 + 0.00
1.74 + 0.44
1.34 + 0.40
Gaussian DiRRAc
1.00 + 0.00
0.99 + 0.02
1.60 + 0.62
0.98 + 0.42
Student
AR
1.00 + 0.00
0,48 + 0.19
0.29 + 0.21
0.26 + 0.18
DiRRAc
1.00 +: 0.00
0.95 + 0.09
1.61 + 0.31
1.08 + 0.24
Gaussian DiRRAc
1.00 + 0.00
0.74 + 0.18
0.81 0.27
0.55 + 0.21
Comparison with RBR. Here we compare our approach on the nonlinear model settings to a more recent approach robust recourse (Nguyen al. 2022).
Table 8: Comparison with RBR for non-linear models on real datasets.
Dataset
Methods
Mi validity
M2 validity
1 cost
12 cost
German
RBR
0.98 + 0.13
0.71 + 0.25
1.11 0.10
0.50 0.07
LIME-DiRRAc
0.78 1 0.42
0.75 1 0.27
1.14 0.27
1.02 1 0.05
LIME-Gaussian DiRRAc
0.70 1 0.46
0.70 + 0.31
1.11 +: 0.26
1.00 1 0.06
SBA
RBR
1.00 = 0.00
0.97 = 0.12
1,42 + 0.45
0.59 + 0.18
LIME-DiRRAc
0.93 + 0.26
0.93 + 0.26
1.10 0.11
1.07 + 0.05
IME-Gaussian DiRRAc
0.82 + 0.38
0.80 + 0.38
0.64 0.29
0.43 + 0.32
Student
RBR
1.00 = 0.00
0.90 = 0.23
1.02 0.53
0.42 + 0.20
LIME-DiRRAc
0.97 + 0.18
0.97 + 0.18
1.12 0.23
1.12 0.23
LIMF-GGussian DiRRAC
0.69 + 0.46
0.59 + 0.46
0.58 0.54
0.50 + 0.51
We provide the results in Table S we can observe that RBR has (nearly) perfect M1 validity. This result is natural because RBR is designed to handle the nonlinear predictive model directly. Our methods do not have the perfect M₁ validity because we use the LIME approximation. However, is important to note that in the problem of robust recourse facing future model shifts, we regard the M2 validity as the most crucial metric because it is the proportion of recourse instances that are valid with respect to the shifted (future) models.
In terms of 1 cost and M2 validity, the results demonstrate that our method has competitive perfor- mance compared to the existing state-of-the-arr methods. In partieular, LIME-DiRRAC outperforms RBR in terms of M2 validity for two datasets (German and Student). In the SBA dataset, ap- proach has lower M2 validity, but the cost of recourses generated by our method is also lower. This result is consistent with discussion about the I cost and M2 validity trade-off in the Appendix.
Comparison with MINT on German Credit datasets. We add more recent baseline MINT proposed by Karimi et al. (2021a) for comparison purpose. MINT requires causal graph; thus, restrict the experiment to the German Credit dataset (the specifications of the causal graphs are not available for SBA and Student Performance). We do not consider MACE as baseline for nonlinear
17

---

Published as a conference paper at ICLR 2023
model comparison because MACE is not applicable neural network target models due to its high computational cost. We use the same set of features as in the MINT and ROAR paper (Karimi et al. 2021a; Upadhyay et al. 202T with four features: Sex, Age, Credit Amount and Duration. The results in Table@@demonstrate that the recourse generated by our framework is more robust to model shifts, but it has higher I cost.
Table 9: Comparison with MINT on German Credit dataset.
Methods
M1 validity
M2 validity
11 cost
MINT
1.00 + 0.00
0.87 + 0.09
0.77 1 0.23
DiRRAc
1.00 + 0.00
0.99 + 0.06
1.62 + 0.30
Gaussian DiRRAc
1.00 0.00
0.99 + 0.06
1.62 + 0.30
Comparison with ensemble baselines. Prior work suggested that model ensembles can be effective for out-of-distribttion prediction (Ovadia et al., 2019 Fort et al.] 2019). Now explore model ensemble method to generate recourse based on ROAR as follows. First we follow the procedure in Section 5 to obtain 100 model parameters 0f with f 1003. Then find recourse by solving the Tollowing problem:
& (Coz (a").1) + Ac (xo,
x² = arg min max max E"EA BEA sE(1...,110)
where l the cross-entropy loss function.
Second, the same 100 models and generate recourse for each model independently. Then average the ROAR recourses across those 100 models as follows.
100
x"
arg min max e (Co; (d").1) + Ac (x0.
100
EEA BEA
Table 10: Benchmark of different variants of ROAR on three real-world datasets.
Dataset
Methods
Mi validity
M2 validity
cost
cost
German
ROAR
1.00 = 0.00
0.94 = 0.15
3,88 0.54
1.61 + 0.22
ROAR Anneemeee
1.00 =
0.95 + 0.15
5.11
2.12 0.24
ROAR-Avg
1.00 + 0.00
0.95 0.15
0.36
2.00 + 0.14
DiRRAc
1.00 + 0.00
0.99 + 0.06
1.25 + 0.21
Gaussian DiRRAc
1.00 + 0.00
0.99
0.30
+
SBA
ROAR
1.00 + 0.00
1.00 0.00
0.72
1.35 + 0.30
ReR--nsemble
1.00 = 0.00
+.00
0.95
1.91 + 0.38
ROAR-Avg
1.00 0.00
1.00 1.000
2.86
0.700
1.78 1 0.35
DiRRAc
1
1.74
1.34 0.40
Gaussian DiRRAc
1.00 + 0.00
0.99 1 0.02
1.60
0.62
0.98 1 0.42
Student
ROAR
1.00 + 0.00
0.94 + 0.10
2.02 0.38
0,96
ReAm-Ensemble
1.00 - 0.00
0.98 0.05
0.50
1.43 + 0.19
ROAR-Avg
1.00 - 0.00
0.97 0.10
0.38
1.31 + 0.17
DiRRAc
1.00 = 0.00
0.09
1.34
1.07 + 0.23
Gaussian DiRRAc
1.00 =
0.14
0.78 - 0.30
0.54 1 0.21
In Table we provide results for the ROAR ensemble method as ROAR-Ensemble and the average ROAR recourses ROAR-Avg. From this table, the M1 and M2 validity of ROAR-Ensemble and ROAR-Avg remain the same for all datasets. almost every benchmark, the recourses generated by those two approaches more costly than ROAR. In comparison with framework, DiRRAc and Gaussian DiRRAc methods demonstrate advantages in terms the cost of recourses.
More discussions about cost-validity trade-off. Previous work about robust recourses have sug-
gested that recourses are more robust with the expense of higher costs (Rawal et al. 2021: Upadhyay
al. 2021 Pawelezyk al. 2020) Black et al. 2022 Our results with DiRRAC Ac and Gaussian
18

---

Published as a conference paper at ICLR 2023
DiRRAc consistent with this suggestion. However, framework achieve robust and ac- tionable recourses with a far smaller cost than ROAR (Upadhyay et 2021) and CEPM (Pawelezyk et al. 2020).
Comparison of run time. Table reports the average run time: we observe that Wachter has the smallest run time, and our (Gaussian) DiRRAc has smaller run time than ROAR in all datasets.
Table 11: Average runtime (seconds).
Methods
German
SBA
Student
0.027
0.046
0.039
Wachter
0.006
0.011
0.006
ROAR
0.396
0.355
0,412
DiRRAc
0,208
0.363
0.244
Gaussian DiRRAc
0.091
0.117
0.124
A.4 RESULTS ON SYNTHETICC DATA
We define the adaptive mean and covariance shift magnitude as a = Padapt Xiter, 3 =Eddapt X iter with Padapt; Endapt are the factor of data shifts, iter is the index of iterative loop of synthesizing process.
0.7
DiRRAc
0.6
ROAR
0.5
6.0
6.6
6.
70
cost
Figure 8: Comparison of M2 validity as a function the I distance between input instance and the recourse for our DiRRAc method and ROAR on synthetic data.
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 Padapt Madapt 0.1. To estimate 0g and Et,, we define valid mixture weights π and generate data for each component for 100 times with the same ratio the mixture weight. We train 100 logistic classifiers compute the empirical mean 0g and the empirical covariance matrix Σg for the ke-th component. We generate recourse for each test instance that belongs to the negative class. In Figure 8 we present the results of the cost-robustness analysis of DiRRAc and ROAR on synthetic data.
2.9
M4 valiohty
0.8
0.
2.8
3.5
0.5
05
15
0.0
322
0.50
5.75
1.00
1.25
150
3.75
2.00
3.00
0.21 330 0.55 100
1.25
3.50
3
2.00
500
0.25
0.50
0.75
1.00
1.25
3.50
3.35 2.00
8
DIRRAC
- AR
Wachter
ROAR
Figure 9: Impact of distribution shifts to the empirical validity. Left: mean shifts parametrized by
a; Center: covariance shifts parametrized by 3; Right: Mean and covariance shifts with a = 3.
19

---

Published as a conference paper at ICLR 2023
B PROOFS
B.1 PROOFS OF SECTION
3
To prove Proposition 3.4 we are using the notion of Value-at-Risk which is defined as follows.
Definition B.1 (Value-at-Risk). For any fixed distribution Qs of O, the Value-at-Ree Risk at the risk tolerance level / E (0, 1) of the loss 0 x is defined as
Qk- VaR x) inf E Qa x T) 21 21 33.
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.1 we have
@O s inf B B [0,
Qx ~00~
sup (P.)
sup (P.
inf :: [0,
sup (..
Qx VaRa(-0'))
By Nguyen 2019
Lemma 3.31), we can reformulate the worst-case value-at-risk as
Qe- VaRRs--TTrr -0p x +
B
T.A +
Pk: v3 |
sup (P..
V 3
It is now easy to observe that in the first case when 0g + pxll=112 2 0, then we should have su, Qu (0 s 0) 1.
2 ||=|||2 0. It is easy to see, by the monotocity of the worst-case value-at-risk with respect to 3, that the minimal value 3 should satisfies
We consider the second case when - 0. x
0g
Br ga
Pk Vx
Exx
|2:112 0.
vB-
Using the transformation t 3 we have
0 æt + v1 82 T Exx + px||a112 = 0.
By rearranging terms and then squaring up both sides, we have the equivalent quadratic equation
(A + B 2AACHt Cf B
with A& a 0 x S 0, B₁ A V x Ser 2 0, and C A Pk |x||| 2 0 as defined in the statement of
the proposition. Note, moreover, that we also have A > C This leads to the solution
A + BB
A
B
C
2 0.
A
B
Thus, find
-AA + Bs A
+
C
fa(x) =
A
+ B
This completes the proof.
We now provide the proof of Theorem 3.2
20

---

Published as a conference paper at ICLR 2023
Proof of Theorem 3.2
We first consider the objective function f of (2), which can be re-expressed
as
f(x)
sup ((C 0) PEB(3)
Σ P x5
sup
(Pt) ve kE[K]
Σ kE[R]
PK sup
Qx x 0)
QuEBa(FA)
Σ kE[K]
P& x [x(2),
where the equality in the second line follows from the non- non- congetiatvytty of Pk. 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
Consider now the last constraint of Using the result of Proposition 3.4 alent
this constraint is equiv-
0 + pa ||
Wk
[K].
This leads to the feasible set X' is defined in
3 This completes the proof.
B.2 PROOFS OF SECTION 4
To prove Theorem function
we first define the following worst-case Gaussian component probability
sup (x(Cg(1)) 0) sup Q6 00 CxEBY (Px)
Wk E [K]. (11)
CLEB (Px)
The next proposition provides the reformulation of ft Proposition B.2 (Worst-case probability Gaussian). For any x Rd. any k [K] and any
(0,, Ex. PR) E I x s4 x R., define the following constants A & 0 x. B v Σy,, and
C pal1al12. The following holds:
(i) We have f2 (x:) if and only if As + Ck <.
(ii) Ifo satisfies f (x) then
- A&Br + CR A
( = 1-
B C
Proof of Proposition
B.2 We first prove Assertion i sian distribution Qu (O,,, )x), and thus
Pick any Qa B. (Pa), then Qu Gaus-
0
@ x 0)
V
Σx.
Guaranteeing S (x) equivalent to guaranteeing
0 x < 0.
sup ((., E S5)
Note that we also have
0 x
-0% + px|10112
sup
sup 8c: 10 - Spa
G(( ( &
by the properties of the dual norm. This leads the equivalent condition that A Cs 0.
21

---

Published as a conference paper at ICLR 2023
We now prove Assertion I
Using the definition of the Value-at- Risk in Definition B.1 we have
1 3 E [0. 2
Qu(0" r - 0) = inf
Q S 50) s
sup
QueRy (Px)
Q PB
inf
3: 3 E [0,
sup Q E (P.)
Qx- Da- $0
Using the result from Nguyen 2019 Lemma 3.31), have
Qx- VaR5(-0's 2) 0 x + tV Ex + pV1 11|1||2 As But CRVI+t,
sup E. (Pxx)
with & Φ-1(1 - 3). Taking the infimum over is then equivalent finding the root of the equation
A + tBg + Cv+++F= Using transformation 1/t, the above equation becomes
A + By + C& C
with solution
BB + CN A B
>0.
A C
Notice that A₁ + C2 0, and we also have A > 0%, thus well-defined. The result now follows
by noticing that fi (x) 1 *()) ((1/T).
We are now ready to prove Theorem 4.1
Proof of Theorem
4.1 Problem is equivalent to
min
ΣnE(K]
Pa f (x)
8. c(x, xo) 5 JK (1))
Wk [K].
Applying Proposition
B.2
we obtain 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 2 we consider alternative formulation of the objective function minimize the worst- case component probability.
C.I ROBUSTIFICATION AGAINST MIXTURE WEIGHT UNCERTAINTY
The DiRRAc problem considered in Section 3 only robustifies the component distributions Ps. We now discuss a plausible approach to robustify against the misspecification of the mixture weights Because the mixture weights should form probability vector, it is convenient model the perturbation in the mixture weights using the o-divergence.
Definition C.1 (d-divergence). Let ó R + be a convex function on the domain R4, 6(1) = O, 0 x s(a/0) a x limetoo o(t)/t for > O, and 0 6(0/0) = 0. The d-divergence D between two probability vectors p, RK amounts to D&(p p) ΣkE[K] Pk d(px/pz).
The family o-divergences contains many well-known statistical divergences such as the Kullback- Leibler divergence, the Hellinger distance, etc. Further discussion this family can be found in Pardo (2018). Distributionally robust optimization models with o-divergence ambiguity set were originally studied in decision-making problems (Ben-Tal et al. 2013 Bayraksan & Love 2015) and
22

---

Published as a conference paper at ICLR 2023
have recently gained attention thanks to their successes in machine learning tasks Namkoong & Duchi 2017: Hashimoto et al. 2018 Duchi et al. 2022).
Let 0 be parameter indicating the uncertainty level of the mixture weights. The uncertainty set for the mixture weights is formally defined as
a {p E [o, 1] =pp= 1, D& P) Sej.
which contains all K --dimensional probability vectors which are of ø-divergence at most e from the nominal weights p. The ambiguity set of the mixture distributions that hedge against the weight misspecification
U(P) - IQ: 3p E A, JQu E BA (Px) vk E [K] such that Q (Qk, }.
where the component sets B& (Pxx are defined as in Section The DiRRAc problem with respect to the ambiguity set (IP) becomes
min
sup P(CG(0) = 0) PEU()) c(x, ro) S sup (F.
s.
(12)
(x(C <
Vk [K].
It is important to note at this point that the feasible set of (2) coincides with the feasible set of 2
Thus, resolve problem (12), suffices analyze the objective function of (22). Given the function
6, we define its conjugate function o² R - IR U } by
(8) = sup {ts x(t)}
120
The next theorem asserts that the worst-case probability under ((P) can be computed by solving a convex program.
Theorem C.2 (Objective value). The feasible set of problem [2 coincides with X. Further, for every X, the objective value of (2) equals the optimal value of convex optimization problem
Σ PRO" fa(I)) fo(z)=")) kE(K]
sup (x()((x) 00 min xERt, DER
+
where fi(x)) are computed using Proposition 3.4
Proof of Theorem decomposition
From the definition of the set U(P), we can rewrite F using a two-layer
PEU(P) F(x) sup (((g(()) = 0) sup PEA
sup
Σ (0 S
(P.)
kE[K]
Σ Pa X sup
@n x 5)
sup PEA
kE(K
Σ pk x fa(a), RE(K]
sup PEA
where the equality in the second line follows from the non-negativity of Pę. and the last equal- ity follows from the definition of (x) in (5. By applying the result from -ee--Tal et al. (2013 Corollary 4.2), we have
min n + Σ P fa(() 7)
F(x)
A
kE[R]
t.t. MER, E IR.
The proof is complete.
From the result of Theorem C.2 we can derive the gradient of the objective function of 12 using Danskin's theorem Shapiro et (2009) Theorem 7.21), simply using auto-differentiation. Fur- thermore, 6* convex, and thus solving the minimization problem Theorem C.2 can done efficiently using convex optimization algorithms.
23

---

Published as a conference paper at ICLR 2023
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 By (Px) constructed in Section
3 then we can solve
min
max kE[R] (P.) S. t. co) 5 sup Qu(Cx(x) - 0) < Vk [K].
sup Qx(Cg(x) -0)
(13a)
(P.
Interestingly, problem 13ap does not involve the mixture weighs p. As consequence, trivial ad- vantage this model is that hedges automatically against the misspecification of p. To complete, provide its equivalent mnite-dimensional form.
Corollary C.3 (Component Probability DiRRAc). Problem 13a is equivalent to
P& 2| + x ST v (0 x2 + x S. 1
(13b)
min ZEA
max
KE[K]
(0% x)2 + x Σ5.
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) = {cu Q+ NO Ex), G((),, Ex). (O,, Ex)) pk]
which is a ball in the space of Gaussian distributions.
D.1 HANDLING MIXTURE WEIGHT UNCERTAINTY GAUSSIAN DIRRAC
Following the notations in Section C.1 we define the set of possible mixture weights as _ {p 1] 1 p = 1, (x |I D) $
and the ambiguity set with Gaussian information is defined as
u (P) - 3p A, EQu E B (Px) 4k E [K] such that Q (Qk, (E)KPE))E(K))
The distributionally robust problem with respect the ambiguity set (IP)
inf
sup PELN(()
P(C)(z) = 0)
S. t. c( vO) < sup CLEBY (f.)
(14)
(C((((z) 0) Vk E [K].
Following the results in Section 4] the feasible set of (14) coincides with the set X. suffices now provide the reformulation for the objective function of (14
Corollary D.1. For any E X, we have
(x(2)
inf 7 m+at+ A Σ PRO
sup P(Cg(x)=
A
KE[K]
PEUN (1)
s.t. X R., E R,
where the values H (x) are obtained in Proposition B.2
Corollary D.2 follows from Theorem D.2 by replacing the quantities f((x) by f((()) to take into
account the Gaussian parametric information. The proof of Corollary D.2 is omitted.
24

---

Published as a conference paper at ICLR 2023
D.2 MINIMIZING WORST-CASE COMPONENT PROBABILITY
We now consider the Gaussian DiRRAc that minimizes the worst-case modal probability of infeasi- bility. More concretely, consider the recourse action obtained by solving
inf
max kE[K] QUEB (Fa)
sup
Qx(C
=
S. t. Cx, FO) S sup QuE (Px)
(15a)
(x(C -
4k E [K].
The next corollary provides the equivalent form of the above optimization problem. Corollary D.2. Problem [5a is equivalent to
(0 xx) - p 1
inf TEX
max KE[K]
1
(15b)
22 x xi Eexo + ph 12 (0 xx)2 x T5 - 121100113
E PROJECTED GRADIENT DESCENT ALGORITHM
The pseudocode of the algorithm is presented in Algorithm The convergence guarantee for Algo- rithm follows from Beck 2017 Theorem 10.15), and distilled in the next theorem.
Algorithm 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 x0 +- Projx; (2ra
for 1 = .,..., T
do Find the smallest integer i such that
1
/ (Proix; (x' - XcVS(xx))) $J(()) 2x
1| - Projx, (x* -X(V)(>>))
Set x 141 Proix, (xt -
end for Output: T
Theorem E.1 (Convergence guarantee). Let {o² ]12,,..... be the sequence generated by Algo-
rithm 7 Then, all limit points of the sequence {x" It stationary points of problem 4 with the modified feasible set Xx. Furthermore, there exists some constant > O such that for any
T > 1, we have
1|00 Projx, (et - (Vf(x'))l C
min
< VT
C
25


Reviews:
[{"review_id": "ZUuYBrfxsf", "reviewer": "Reviewer_UpMU", "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": "This work formulates and targets the setting of distributional robust recourse action to deal with model perturbation and changes in recourse action problems. It proposes the formulation of distributional robust recourse action as a min-max problem with a Gelbrich distance as the distance metric of the uncertainty set. In addition, a corresponding projected gradient descent algorithm is proposed to solve it. Experiments have been conducted to compare with baselines using the metric cost and validity.", "summary_of_the_review": "In summary, this is a work targeting a new setting called distributional robust recourse action to deal with model perturbation and changes, inspired by a distributionally robust optimization framework. It not only provides the formulation of this new problem but also proposes new methods DiRRAc or Gaussian-DiRRAc for it. The only concern is that the experimental results does not show a large gap between the proposed method and other baselines. So I suggest a borderline acceptance.", "strength_and_weaknesses": "Strength:\n1. This work seems to be the first work that considers the setting of distributional robust recourse action to deal with model perturbation and changes when generating recourse actions.\n2. By formulating the problem using Gelbrich distance, it proposes the reformulation of this problem in general and Gaussian framework and also the corresponding algorithms.\n\nWeaknesses:\n1. If I didn't understand wrongly, the baseline AR and Wachter has better ( smaller ) $\\ell_1$ cost than the proposed DiRRAc or Gaussian DiRRAc? And for M1 validity and M2 validity, it works the same as ROAR or similar to other baselines? So the performance of the proposed methods doesn't show very convincing results with comparisons to baselines.\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": "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": "ZHmlRcXaHi", "reviewer": "Reviewer_7AqH", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The paper proposes the Distributionally Robust Recourse Action (DiRRAc) framework that generates an optimal recourse action, which under a mixture of model shifts, enjoys the highest probability of being valid. A projected gradient descent algorithm is designed to solve the model and find an optimal recourse action.", "summary_of_the_review": "I would recommend an acceptance of this paper: the framework is well-motivated and well-designed. The treatment is clear yet noval.", "strength_and_weaknesses": "Strength:\n1. The framework is well motivated and the distributionally robust optimization approach is a suitable tool to address the issues raised.\n2. The ambiguity set to capture model shifts is effective, leading the framework to a formulation that can be solved with the designed algorithm.\n3. The extension to hedge against the misspecification of the mixture weights also supports that the framework is well-designed.\n4. The numerical experiments are convincing.\n\nWeakness:\nMy only comment is that some existing works should be cited:\n1. \"Distributionally robust multi-item newsvendor problems with multimodal demand distributions\" addresses a similar issue of uncertain mixture weights.\n2. \"Sharing the value-at-risk under distributional ambiguity\" also values the probability under distributional ambiguity around a reference Gaussian distribution.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IjCJ9MrzMo", "reviewer": "Reviewer_LdkR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a method to generate post-hoc recourses which remain valid under model shift, called DiRRAc. The model parameters are considered as a random vector modeled according to a mixture distribution (whose parameters are fit by taking models trained on trainset samples). Future model shifts are modeled by considering all distributions close to the initial distribution, called the ambiguity set. The paper proposes a minimax problem where inner max is over the ambiguity set and min is over possible counterfactuals. By choosing Gelbrich distance, the optimization problem is shown to be solvable, and the paper proposes a Projected GD algorithm. Experiments are conducted on 3 real-world datasets, and they compare against 4 baselines. ", "summary_of_the_review": "The paper applies distributionally robust optimization techniques to generate robust recourses in a technically sound way. Their way of quantifying model uncertainty, by using ambiguity sets, gets rid of having to specify an explicit set of possible future model parameters as in ROAR. Experimental results are convincing for linear models. DiRRAc may see limited success for highly non-linear models which can change in complicated ways.", "strength_and_weaknesses": "+ The paper deals with a practical problem; generating robust recourses is necessary for models which are to be deployed in the real world\n+ Experimental results are encouraging, as DiRRAc achieves best post-shift validity for all datasets shown, and compares favorably against ROAR [1] in cost of recourses\n+ Unlike ROAR [1], DiRRAc doesn’t have to specify the set of possible model parameter perturbations (\\Delta), but it has its own parameters to tune/specify. I am not sure if ROAR could have achieved similar M2 validity results with different \\Delta, but figure 3 seems to show DiRRAc consistently achieves lower cost recourses\n\n\n- DiRRAc is not the best performing method (in M2 validity) for non linear models, which are usually the ones deployed, since it relies on the local linear approximation \n- How can the initial distribution parameters be computed for classifiers which already exist? \n- How is \\rho_k determined? Ideally, we want to have a larger ball if we expect the model to change significantly. Is there a guideline for this?\n- How costly is the projection step? A study of time taken to generate recourses vs ROAR is necessary to determine practicality\n\nOther points\n* cite the source for Definition 3.1\n* possible typo on page 5, last paragraph, should it be f_k(x) <1 instead of f_k(x)\\leq 0 in the reformulation?\n* Citations are missing for the 3 datasets used\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": "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": "AaUCtFrqYA3", "reviewer": "Reviewer_URnu", "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": "In this paper, the authors proposed the Distributionally Robust Recourse Action (DiRRAc) framework, which generates a recourse action that has a high probability of being valid under a mixture of model shifts. The authors formulated the robustified recourse setup as a min-max optimization problem, where the max problem is specified by Gelbrich distance over an ambiguity set around the distribution of model parameters.  Numerical experiments with both synthetic and three real-world datasets demonstrate the benefits of our proposed framework over state-of-the-art recourse methods.\n", "summary_of_the_review": "1 . The convergence result is just a direct application of existing result, which can hardly be counted as a contribution\n2 . The analysis is based on linear case which is not really practical, which for nonlinear classifiers, it requires to use LIME to approximate, which could lead to degraded performances. .\n3. The authors may want to comment on/compare with the following recent work:\nNguyen, Tuan-Duy H., et al. \"Robust Bayesian Recourse.\" Uncertainty in Artificial Intelligence. PMLR, 2022.\n\n", "strength_and_weaknesses": "Strength\n1.  proposed a framework of Distributionally Robust Recourse Action (DiRRAc) for designing a recourse action that is robust to mixture shifts of the model parameters\n2. Numerical experiments with both synthetic and three real-world datasets demonstrate the benefits \n\nWeakness\n1. it requires LIME for local approximation\n2. Lack of comparison with new baselines\n\n", "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": {}}]

Author rebuttal:

Decision: Accept: poster