DISTRIBUTIONALLY ROBUST RECOURSE ACTION
Year: 2021

Abstract:
Recourse actions 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.

text: Recourse actions 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.

heading: 1 INTRODUCTION
text: Post-hoc explanations of machine learning models are useful for understanding and making reliable predictions in consequential domains such as loan approvals, college admission and healthcare. Recently, recourse is rising as an attractive tool do diagnose why the machine learning models have made a particular decision for a given instance. Recourse work by providing possible actions to modify a given instance to receive an alternate decision (Ustun et al., 2019). Consider, for example, the case of loan approvals in 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 of a counterfactual in this case may be “the monthly salary should be higher by $500” or “20% of the current debt should be reduced”.
Recourses have a positive, forward-looking meaning: they list out the recourse actions that a person should implement so that they can get a more favorable outcome in the future. 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 (Ustun et al., 2019; Karimi et al., 2021). 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 a trivial task. For realworld implementation, designing a recourse needs to strike an intricate balance between conflicting criteria. First and foremost, a recourse action should be feasible: if the prescribed action is 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 to take recourse actions to avoid making a 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) unchanged. For example, we must consider date of birth as 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., 2021; Artelt & Hammer, 2019). 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 nearest counterfactual explanations and focus on structured data. Dandl et al. (2020) proposed a method which finds counterfactual by solving a multi-objective optimization problem. Recently, Russell (2019) and Mothilal et al. (2020) focus on finding a set of multiple diverse recourse actions, where the
diversity is imposed by a rule-based approach or by internalize a determinant point process cost in the objective function.
These aforementioned approaches make a 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 emerging 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., 2021). 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 in 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 instance level recourses (counterfactual explanations) that are 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 is well-known that robust optimization solutions can be overly conservative because they may hedge against a pathological 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 framework (El Ghaoui et 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 a 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 explainable artificial intelligence: counterfactual explanations and robustness, in order to resolve the recourse 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 maximizes the probability that the action is feasible with respect to a mixture shift of model parameters, 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 a mixture ambiguity set prescribed by moment information.
2. We reformulate the DiRRAc problem into a finite-dimensional 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 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 subsequently 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}. We use Sd+ (Sd++) to denote the space of symmetric positive semidefinite (definite, respectively) matrices. For any A ∈ Rm×m, the trace operator is defined as Tr [ A ] = ∑d i=1Aii. We write Qk ∼ (µk,Σk) to denote that the distribution Qk has mean vector µk and covariance matrix Σk. If additionally Qk is Gaussian, we write Qk ∼ N (µk,Σk). With a slight abuse of notation, Q ∼ (Qk, pk)k∈[K] means Q is a mixture of K component distributions, the k-th component has weight pk and distribution Qk.

heading: 2 RECOURSE ACTION UNDER MIXTURE SHIFTS
text: We consider a binary classification setting with label Y = {0, 1}, where 0 represents the unfavorable outcome while 1 denotes the favorable one. The covariate space is Rd, and any linear classifier Cθ : Rd → Y characterized by the d-dimensional parameter θ is of the form
Cθ(x) = {
1 if θ>x ≥ 0, 0 otherwise.
Note that the bias term can be internalized into θ by adding an extra dimension, and thus it is omitted.
Suppose that at this moment (t = 0), the current classifier is parametrized by θ0, and we are given an input instance x0 ∈ Rd with unfavorable outcome, that is, Cθ0(x0) = 0. One period of time from now (t = 1), the parameters of the predictive model will change stochastically, and are represented by a d-dimensional random vector θ̃. This paper focuses on finding a recourse action x which is reasonably close to the instance x0, and at the same time, has a high probability of receiving a favorable outcome in the future. Figure 1 gives a bird’s eye view of the setup
To measure the closeness between the action x and the input x0, we assume that the covariate space is endowed with a non-negative, continuous cost function c. In addition, suppose temporarily that θ̃ follows a 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 x P̂(Cθ̃(x) = 0) s. t. x ∈ X, c(x, x0) ≤ δ.
(1)
The parameter δ ≥ 0 in (1) governs how far a recourse action can be from the input instance x0. Note that we constrain x 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, we model the random vector θ̃ using a finite mixture of distributions with K components, the mixture weights are p̂ satisfying ∑ k∈[K] p̂k = 1. Each component in the mixture represents one specific type of data shifts: the weights p̂ reflect the proportion of the shift types while the component distribution P̂k 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̂k is a Gaussian distribution N (θ̂k, Σ̂k), then P̂ is a mixture of Gaussian distributions. The objective of problem (1) can be expressed as
P̂(Cθ̃(x) = 0) = ∑ k∈[K] p̂kP̂k(Cθ̃(x) = 0) = ∑ k∈[K] p̂kΦ ( −x>θ̂k√
x>Σ̂kx
) ,
where the first equality follows from the law of conditional probability, and Φ is the cumulative distribution function of a standard Gaussian distribution. Under the Gaussian assumption, we can solve (1) using a projected gradient descent type of algorithm (Boyd & Vandenberghe, 2004). Remark 2.1 (Nonlinear models). Our analysis focuses on linear classifiers, which is a common setup in the literature (Upadhyay et al., 2021; Ustun et al., 2019; Rawal et al., 2021; Karimi et al., 2020; Wachter et al., 2018; Ribeiro et al., 2016). To extend to nonlinear classifiers, we can follow a similar approach as in Rawal & Lakkaraju (2020) and Upadhyay et al. (2021) by first using LIME (Ribeiro et al., 2016) to approximate the nonlinear classifiers locally with an interpretable linear model, then subsequently applying our framework.

heading: 3 DISTRIBUTIONALLY ROBUST RECOURSE ACTION FRAMEWORK
text: Our Distributionally Robust Recourse Action (DiRRAc) framework robustifies formulation (1) by relaxing the parametric assumption and hedging against distribution misspecification. First, we assume that the mixture components P̂k are specified only through moment information, and no particular parametric form of the distribution is imposed. In effect, P̂k is assumed to have mean vector θ̂k ∈ Rd and positive definite covariance matrix Σ̂k 0. Second, we leverage ideas from distributionally robust optimization to propose a min-max formulation of (1), 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, we use the Gelbrich distance. Definition 3.1 (Gelbrich distance). The Gelbrich distance G between two tuples (θ,Σ) ∈ Rd × Sd+ and (θ̂, Σ̂) ∈ Rd × Sd+ amounts to G((θ,Σ), (θ̂, Σ̂)) , √ ‖θ − θ̂‖22 + Tr [ Σ + Σ̂− 2(Σ̂ 12 ΣΣ̂ 12 ) 12 ] .
It is easy to verify that G is non-negative, symmetric and it vanishes to zero if and only if (θ,Σ) = (θ̂, Σ̂). Further, G is a distance on Rd × Sd+ because it coincides with the type-2 Wasserstein distance between two Gaussian distributions N (µ,Σ) and N (µ̂, Σ̂) (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).
In this paper, we use the Gelbrich distance G to form a neighborhood around each P̂k as Bk(P̂k) , { Qk : Qk ∼ (θk,Σk), G((θk,Σk), (θ̂k, Σ̂k)) ≤ ρk } .
Intuitively, one can view Bk(P̂k) as a ball centered at the nominal component P̂k of radius ρk ≥ 0 prescribed using the distance G. This component set Bk(P̂k) is non-parametric, and the first two moments of Qk are sufficient to decide whether Qk belongs to Bk(P̂k). Moreover, if Qk ∈ Bk(P̂k), then any distribution Q′k with the same mean vector and covariance matrix as Qk also belongs to Bk(P̂k). Notice that even when the radius ρk is zero, the component set Bk(P̂k) does not collapse into a singleton. Instead, if ρk = 0 then Bk(P̂k) still contains all distributions of the same moment (θ̂k, Σ̂k) with the nominal component distribution P̂k, and consequentially it possesses the robustification effects against the parametric assumption on P̂k. The component sets are utilized to construct the ambiguity set for the mixture distribution as
B(P̂) , { Q : ∃Qk ∈ Bk(P̂k) ∀k ∈ [K] such that Q ∼ (Qk, p̂k)k∈[K] } .
Any Q ∈ B(P̂) is also a mixture distribution with K components, with the same mixture weights p̂. Thus, B(P̂) contains all perturbations of P̂ induced separately on each component by Bk(P̂k). We are now ready to introduce our DiRRAc model, which is a min-max problem of the form
inf x∈X sup Q∈B(P̂) Q(Cθ̃(x) = 0) s. t. c(x, x0) ≤ δ sup
Qk∈Bk(P̂k) Qk(Cθ̃(x) = 0) < 1 ∀k ∈ [K].
(2)
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 Bk(P̂k). 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 use the Gelbrich distance to prescribe the set Bk(P̂k), we can solve these maximization problems
analytically. This consequentially leads to a closed-form reformulation of the DiRRAc model into a finite-dimensional problem. Next, we will reformulate the DiRRAc problem (2), provide a sketch of the proof and propose a numerical solution routine.

heading: 3.1 REFORMULATION OF DIRRAC
text: Each supremum in (2) is an infinite-dimensional 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 , { x ∈ X : c(x, x0) ≤ δ, −θ̂>k x+ ρk‖x‖2 < 0 ∀k ∈ [K] } . (3)
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) is equivalent to the following finitedimensional problem
inf x∈X ∑ k∈[K] p̂k
( ρkθ̂ > k x‖x‖2 + √ x>Σ̂kx √ (θ̂>k x)
2 + x>Σ̂kx− ρ2k‖x‖22 (θ̂>k x) 2 + x>Σ̂kx
)2 . (4)

heading: 3.2 PROOF SKETCH
text: We now sketch the proof of Theorem 3.2. For any component k ∈ [K], define the following worstcase probability of unfavorable outcome function
fk(x) , sup Qk∈Bk(P̂k) Qk(Cθ̃(x) = 0) = sup Qk∈Bk(P̂k) Qk(θ̃>x ≤ 0) ∀k ∈ [K]. (5)
To proceed, we rely on the following elementary result from Nguyen (2019, Lemma 3.31).
Lemma 3.3 (Worst-case Value-at-Risk). For any x ∈ Rd and β ∈ (0, 1), we have
inf { τ : sup
Qk∈Bk(P̂k) Qk(θ̃>x ≤ −τ) ≤ β
} = −θ̂>k x+ √ 1− β β √ x>Σ̂kx+ ρk√ β ‖x‖2. (6)
Note that the left-hand side of (6) is the worst-case Value-at-Risk with respect to the ambiguity set Bk(P̂k). Leveraging this result, the next proposition provides the analytical form of fk(x).
Proposition 3.4 (Worst-case probability). For any k ∈ [K] and (θ̂k, Σ̂k, ρk) ∈ Rd × Sd+ × R+, define the following constants Ak , −θ̂>k x, Bk , √ x>Σ̂kx, and Ck , ρk‖x‖2. We have
fk(x) , sup Qk∈Bk(P̂k)
Qk(θ̃>x ≤ 0) = { 1 if Ak + Ck ≥ 0,( −AkCk+Bk √ A2k+B 2 k−C 2 k
A2k+B 2 k
)2 ∈ (0, 1) if Ak + Ck < 0.
The proof of Theorem 3.2 follows by noticing that the DiRRAc problem (2) can be reformulated using the elementary functions fk as
min x∈X  ∑ k∈[K] p̂kfk(x) : c(x, x0) ≤ δ, fk(x) ≤ 0 ∀k ∈ [K]  , where the objective function follows from the definition of the set B(P̂). It suffices now to combine with Proposition 3.4 to obtain the necessary result. The detailed proof is relegated to the Appendix.

heading: 3.3 PROJECTED GRADIENT DESCENT ALGORITHM
text: We consider in this section an iterative numerical routine to solve the DiRRAc problem in the equivalent form (4). First, notice that the second constraint that defines X in (3) is a strict inequality, thus the set X is open. We thus modify slightly this constraint by considering the following set
Xε = { x ∈ X : c(x, x0) ≤ δ, −θ̂>k x+ ρk‖x‖2 ≤ −ε ∀k ∈ [K] } for some value ε > 0 sufficiently small. Moreover, if the parameter δ is too small, it may happen that the feasible set Xε becomes empty. Let δmin ∈ R+ be defined as the optimal value of the following optimization problem
δmin ,
{ inf c(x, x0)
s. t. x ∈ X, − θ̂>k x+ ρk‖x‖2 ≤ −ε ∀k ∈ [K]. (7)
Then it is easy to see that Xε is non-empty whenever δ ≥ δmin. 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 Xε, for which the optimal solution is guaranteed to exist.
Let us now define the projection operator ProjXε as
ProjXε(x ′) = arg min { ‖x− x′‖22 : x ∈ Xε } .
If X is convex and c( · , x0) 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(x, x0) = ‖x−x0‖2 is the Euclidean norm and X is secondorder cone representable, then the projection is equivalent to a 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 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 E.

heading: 4 GAUSSIAN DIRRAC FRAMEWORK
text: We here revisit the Gaussian assumption on the component distributions, and propose the parametric Gaussian DiRRAc framework. We make the temporary assumption that P̂k are Gaussian for all k ∈ [K], and we will robustify against only the misspecification of the nominal mean vector and covariance matrix (θ̂k, Σ̂k). To do this, we first construct the Gaussian component ambiguity sets
∀k : BNk (P̂k) , { Qk : Qk ∼ N (θk,Σk), G((θk,Σk), (θ̂k, Σ̂k)) ≤ ρk } ,
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
BN (P̂) = { Q : ∃Qk ∈ BNk (P̂k) ∀k ∈ [K] such that Q ∼ (Qk, p̂k)k∈[K] } .
The Gaussian DiRRAc problem is formally defined as
min x∈X sup Q∈BN (P̂) Q(Cθ̃(x) = 0)
s. t. c(x, x0) ≤ δ sup
Qk∈BNk (P̂k) Qk(Cθ̃(x) = 0) < 1 2 ∀k ∈ [K].
(8)
Similar to Section 3, we will provide the reformulation of the Gaussian DiRRAc formulation and a sketch of the proof in the sequence. Note that the last constraint in (8) has margin 12 instead of 1 as in the DiRRAc problem (2). The detailed reason is revealed in the proof sketch in Section 4.2.

heading: 4.1 REFORMULATION OF GAUSSIAN DIRRAC
text: Remind that the feasible set X is defined as in equation 3. The next theorem asserts the equivalent form of the Gaussian DiRRAc problem (8). Theorem 4.1 (Gaussian DiRRAc reformulation). The Gaussian DiRRAc problem (8) is equivalent to the following optimization problem
min x∈X 1− ∑ k∈[K] p̂kΦ
( (θ̂>k x) 2 − ρ2k‖x‖22
θ̂>k x √ x>Σ̂kx+ ρk‖x‖2 √ (θ̂>k x) 2 + x>Σ̂kx− ρ2k‖x‖22
) . (9)
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.

heading: 4.2 PROOF SKETCH
text: The proof of Theorem 4.1 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 ∈ Rd and β ∈ (0, 12 ], we have
inf { τ : sup
Qk∈BNk (P̂k) Qk(θ̃>x ≤ −τ) ≤ β
} = −θ̂>k x+ t √ x>Σ̂kx+ ρ √ 1 + t2‖x‖2 (10)
with t = Φ−1(1− β).
It is important to note that Lemma 4.2 is only valid for β ∈ (0, 0.5]. Indeed, for β > 12 , evaluating the infimum problem in the left-hand side of (10) requires solving a non-convex optimization problem as t = Φ−1(1 − β) < 0. As a consequence, the last constraint of the Gaussian DiRRAc formulation (8) is capped at a probability value of 0.5 to ensure the convexity of the feasible set in the reformulation (9). The proof of Theorem 4.1 follows a similar line of argument as for the DiRRAc formulation, the details are relegated to the appendix.

heading: 5 NUMERICAL EXPERIMENTS
text: 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-art methods: the Robust and Reliable Algorithmic Recourse (ROAR) (Upadhyay 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 l1 distance c(x, x0) = ‖x − x0‖1. Complementary results and details about the datasets and the experiment setup are provided in Appendix A. All codes and results can be accessed from https://anonymous.4open.science/r/DiRRAc.
Results on synthetic data. We synthesize 2-dimensional data by using K = 3 different shifts similar to Upadhyay et al. (2021): mean shift, covariance shift, and both shifts. First, we fix the unshifted conditional distributions with X|Y = y ∼ N (µy,Σy) ∀y ∈ Y . For mean shift, we replace µ0 by µshift0 = µ0 + [α, 0]
>, where α is a mean shift magnitude. For covariance shift, we replace Σ0 by Σshift0 = (1+β)Σ0, where β is a covariance shift magnitude. For mean and covariance shift, we replace (µ0,Σ0) by (µshift0 ,Σ shift 0 ). We generate 500 samples each class from the unshifted distribution with µ0 = [−3;−3], µ1 = [3; 3], and Σ0 = Σ1 = I . To estimate θ̂k and Σ̂k 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 θ̂k and the empirical covariance matrix Σ̂k for the k-th component. We generate recourse for
each test instance that belongs to negative class. Finally, we compute the empirical validity as the fraction of instances that are still valid with respect to the shifted classifiers. The results in 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.
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) the Small Business Administration (SBA) dataset, which captures a temporal shift. (iii) the Student 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), we use one-hot encodings for categorial features, then consider them as continuous features in [0, 1]. To ease the comparison, we chooseK = 1. To estimate (θ̂1, Σ̂1), we split randomly 80% of the original 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 (θ̂1, Σ̂1). In parallel, we randomly split 80-20 the shifted dataset 100 times, and each time train a logistic classifier on 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 a linear classifier on the training data. and generate recourse for each test instance that is 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 is 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 l1 and l2 distance between the recourse and the original instance. The results in Table 1 demonstrate that our DiRRAc have high validity, while keeping the l1 and l2 cost low. ROAR has high validity in all three datasets, but also has higher cost than our framework.
Nonlinear models. Following the previous work as in Rawal et al. (2021) and Upadhyay et al. (2021), we adapt our framework and other baselines to non-linear models by first generating local
linear approximations using LIME (Ribeiro et 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 x0. To obtain a local explanation, LIME synthesizes perturbed examples in the local neighborhood of x0, queries the predictions of models for these examples, and then trains an interpretable model based on these labeled synthetic examples.
For each instance x0, we first do a 80-20 split on the original dataset and train a MLPs classifier on the training data. Then generate a local linear model for MLPs classifier 10 times using LIME with 1000 perturbed samples. To estimate (θ̂1, Σ̂1), we compute the mean and covariance matrix of parameters θx0 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 a 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 demonstrate that our DiRRAc have a higher validity than other baselines in the original and shifted MLPs classifier, while keeping the l1 and l2 cost low.

heading: 6 CONCLUDING REMARKS
text: In this work, we proposed the Distributionally Robust Recourse Action (DiRRAc) framework to address the problem of recourse robustness to model shifts. We introduced a distributionally robust optimization approach for generating robust recourse using a 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 misspecification 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 relies fundamentally on the design of the ambiguity sets using a Gelbrich distance on the moment space. This Gelbrich ambiguity set leads to the ‖ · ‖2-regularizations of the worst-case Value-at-Risk in Lemmas 3.3 and 4.2. If we consider other moment ambiguity sets, for example, the moment bounds in Delage & Ye (2010) or the Kullback-Leibler-type sets in Taskesen et al. (2021), then these regularization 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.

heading: A ADDITIONAL EXPERIMENT RESULTS
text: 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 α = µadapt×iter, β = Σadapt ∗iter with µadapt ,Σadapt are the factor of data shifts, iter is the index of iterative loop of synthesizing process.
To visualize feasible set as Figure 2, we generate synthetic data with the following parameters: µ0 = [−3;−3], µ1 = [3; 3], and Σ0 = Σ1 = I . Then, we split data to training set and test set (80% for training and 20% for testing), train the original classifier on training set and then choose one instance on test set that is classified as 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 µadapt = Σadapt = 0.1. Then we train
and get the parameters θ̂k and ̂̂ Σk same as above.
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 parameters in 2D as Figure 5.
To evaluate how magnitude of upper bound cost affects the validity of our models, we use different values of upper bound cost. We define δ = δmin + δadd with δmin is defined in (7). We use the same parameters as above for generating synthetic data. For each value of δadd, we evaluate the validity by using 100 classifiers trained on 100 different data distribution shifts with 3 different shift types.
Additional results for the Impact of magnitude of distribution shifts to empirical validity.
To evaluate the trade-offs between the l1 cost and the validity of DiRRAc, we benchmark these two criteria by running DiRRAc with different values of δ. We define δ = δmin + δadd as before. For each value of δ, we evaluate the l1 cost and validity by using 100 classifiers trained on 100 different data distribution shifts with 3 different shift types.
We also evaluate the trade-offs between l1 cost and validity of DiRRAc using 20 instances. In the comparison with ROAR, we evaluate l1 cost and validity of DiRRAc and ROAR using 10 instances. We use a wide range of parameters for ROAR and compute the l1 cost and validity of recourses. We report the results of 2 experiments in Figure 8 and Figure 9.
Real-world data. For each of three real-world datasets, we choose a number of features to benchmark with other baselines:
Dataset Methods Accuracy
German Credit LR 0.72 ± 0.00 MLPs 0.76 ± 0.01 Shifted German Credit LR 0.7 ± 0.00 MLPs 0.72 ± 0.01
SBA LR 0.79 ± 0.01 MLPs 0.93 ± 0.02 Shifted SBA LR 0.77 ± 0.01 MLPs 0.89 ± 0.01
Student Performance LR 0.84 ± 0.01 MLPs 0.91 ± 0.01 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(x, x0) = ‖x − x0‖2. Table 6 reports the M2 validity, along with the l1 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 5
Experiments with prior on Σ̂.
In this experiments we assume that we does not have access to the training data. We set the θ̂1 = θ0, θ0 is parameters of the original classifier. Then we choose Σ̂1 = τ ∗ I . We generate recourse for each input instance and compute M1 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 l1 and l2 cost lower than ROAR in three datasets except the l2 cost in SBA dataset.

heading: B PROOFS
text: B.1 PROOFS OF SECTION 3
To prove Proposition 3.4, we are using the notion of Value-at-Risk which is formally defined as follows. Definition B.1 (Value-at-Risk). For any fixed distribution Qk of θ̃, the Value-at-Risk at the risk tolerance level β ∈ (0, 1) of the loss θ̃>x is defined as
Qk- VaRβ(θ̃>x) , inf{τ ∈ R : Qk(θ̃>x ≤ τ) ≥ 1− β}
We are 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
sup Qk∈Bk(P̂k)
Qk(θ̃>x ≤ 0) = inf { β : β ∈ [0, 1], sup
Qk∈Bk(P̂k) Qk(θ̃>x ≤ 0) ≤ β
}
= inf { β : β ∈ [0, 1], sup
Qk∈Bk(P̂k) Qk- VaRβ(−θ̃>x) ≤ 0
}
By Nguyen (2019, Lemma 3.31), we can reformulate the worst-case value-at-risk as
sup Qk∈Bk(P̂k)
Qk- VaRβ(−θ̃>x) = −θ̂>k x+ √ 1− β β √ x>Σ̂kx+ ρk√ β ‖x‖2.
It is now easy to observe that in the first case when −θ̂>k x + ρk‖x‖2 ≥ 0, then we should have supQk∈Bk(P̂k) Qk(θ̃ >x ≤ 0) = 1.
We now consider the second case when −θ̂>k x+ ρk√ β ‖x‖2 < 0. It is easy to see, by the monotocity of the worst-case value-at-risk with respect to β, that the minimal value β? should satisfies
−θ̂>k x+ √ 1− β? β? √ x>Σ̂kx+ ρk√ β? ‖x‖2 = 0.
Using the transformation t← √ β?, we have
−θ̂>k xt+ √ 1− t2 √ x>Σ̂kx+ ρk‖x‖2 = 0.
By rearranging terms and then squaring up both sides, we have the equivalent quadratic equation
(A2k +B 2 k)t 2 + 2AkCkt+ C 2 k −B2k = 0 with Ak , −θ̂>k x ≤ 0, Bk , √ x>Σ̂kx ≥ 0, and Ck , ρk‖x‖2 ≥ 0 as defined in the statement of the proposition. Note, moreover, that we also have A2k ≥ C2k . This leads to the solution
t = −AkCk +Bk
√ A2k +B 2 k − C2k
A2k +B 2 k
≥ 0.
Thus, we find
fk(x) = (−AkCk +Bk√A2k +B2k − C2k
A2k +B 2 k
)2 .
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 as
f(x) = sup P∈B(P̂) P(Cθ̃(x) = 0) = sup Qk∈Bk(P̂k) ∀k ∑ k∈[K] p̂kQk(θ̃>x ≤ 0)
= ∑ k∈[K] p̂k × sup Qk∈Bk(P̂k) Qk(θ̃>x ≤ 0)
= ∑ k∈[K] p̂k × fk(x),
where the equality in the second line follows from the non-negativity of p̂k, and the last equality follows from the definition of fk(x) 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 equivalent to
−θ̂>k x+ ρk‖x‖2 < 0 ∀k ∈ [K].
This leads to the feasible set X as is defined in (3). This completes the proof.
B.2 PROOFS OF SECTION 4
To prove Theorem 4.1, we first define the following worst-case Gaussian component probability function
fNk (x) , sup Qk∈BNk (P̂k) Qk(Cθ̃(x) = 0) = sup Qk∈BNk (P̂k) Qk(θ̃>x ≤ 0) ∀k ∈ [K]. (11)
The next proposition provides the reformulation of fNk . Proposition B.2 (Worst-case probability - Gaussian). For any x ∈ Rd, any k ∈ [K] and any
(θ̂k, Σ̂k, ρk) ∈ Rd × Sd+ × R+, define the following constants Ak , −θ̂>k x, Bk , √ x>Σ̂kx, and

heading: Ck , ρk‖x‖2. The following holds:
text: (i) We have fNk (x) < 1 2 if and only if Ak + Ck < 0.
(ii) If x satisfies fNk (x) < 1 2 , then
fNk (x) = 1− Φ ( A2k − C2k −AkBk + Ck √ A2k +B 2 k − C2k ) .
Proof of Proposition B.2. We first prove Assertion (i). Pick any Qk ∈ BNk (P̂k), then Qk is a Gaussian distribution Qk ∼ N (θk,Σk), and thus
Qk(θ̃>x ≤ 0) = Φ ( −θ>k x√
x>Σx
) .
Guaranteeing fNk (x) < 1 2 is equivalent to guaranteeing
sup G((θk,Σk),(θ̂k,Σ̂k))≤ρk
− θ>k x ≤ 0.
Note that we also have
sup G((θk,Σk),(θ̂k,Σ̂k))≤ρk − θ>k x = sup θk:‖θk−θ̂k‖2≤ρk − θ>k x = −θ̂>k x+ ρk‖x‖2
by the properties of the dual norm. This leads to the equivalent condition that Ak + Ck < 0.
We now prove Assertion (ii). Using the definition of the Value-at-Risk in Definition B.1, we have
sup Qk∈BNk (P̂k)
Qk(θ̃>x ≤ 0) = inf { β : β ∈ [0, 1
2 ), sup Qk∈BNk (P̂k) Qk(θ̃>x ≤ 0) ≤ β
}
= inf { β : β ∈ [0, 1
2 ), sup Qk∈BNk (P̂k) Qk- VaRβ(−θ̃>x) ≤ 0 } Using the result from Nguyen (2019, Lemma 3.31), we have
sup Qk∈Bk(P̂k)
Qk- VaRβ(−θ̃>x) = −θ̂>k x+ t √ x>Σ̂kx+ ρ √ 1 + t2‖x‖2 = Ak +Bkt+ Ck √ 1 + t,
with t = Φ−1(1 − β). Taking the infimum over β is then equivalent to finding the root of the equation
Ak + tBk + Ck √ 1 + t2 = 0.
Using a transformation τ = 1/t, the above equation becomes Akτ +Bk + Ck √ 1 + τ2 = 0
with solution
τ = −AkBk + Ck
√ A2k +B 2 k − C2k
A2k − C2k > 0.
Notice thatAk+Ck < 0, and we also haveA2k > C 2 k , thus τ is well-defined. The result now follows by noticing that fNk (x) = 1− Φ(t) = 1− Φ(1/τ).
We are now ready to prove Theorem 4.1.
Proof of Theorem 4.1. Problem (8) is equivalent to min ∑ k∈[K] p̂k × fNk (x)
s. t. c(x, x0) ≤ δ fNk (x) < 1 2 ∀k ∈ [K].
Applying Proposition B.2, we obtain the necessary result.

heading: C EXTENSIONS OF THE DIRRAC FRAMEWORK
text: 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 to minimize the worstcase component probability.
C.1 ROBUSTIFICATION AGAINST MIXTURE WEIGHT UNCERTAINTY
The DiRRAc problem considered in Section 3 only robustifies the component distributions P̂k. We now discuss a plausible approach to robustify against the misspecification of the mixture weights p̂. Because the mixture weights should form a probability vector, it is convenient to model the perturbation in the mixture weights using the φ-divergence. Definition C.1 (φ-divergence). Let φ : R → R be a convex function on the domain R+, φ(1) = 0, 0 × φ(a/0) = a × limt↑∞ φ(t)/t for a > 0, and 0 × φ(0/0) = 0. The φ-divergence Dφ between two probability vectors p, p̂ ∈ RK+ amounts to Dφ(p ‖ p̂) , ∑ k∈[K] p̂k × φ(pk/p̂k).
The family of φ-divergences contains many well-known statistical divergences such as the KullbackLeibler divergence, the Hellinger distance, etc. Further discussion on this family can be found in Pardo (2018). Distributionally robust optimization models with φ-divergence ambiguity set were originally studied in decision-making problems (Ben-Tal et al., 2013; Bayraksan & Love, 2015) 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 a parameter indicating the uncertainty level of the mixture weights. The uncertainty set for the mixture weights is formally defined as
∆ , { p ∈ [0, 1]K : 1>p = 1, Dφ(p ‖ p̂) ≤ ε } ,
which contains all K-dimensional probability vectors which are of φ-divergence at most ε from the nominal weights p̂. The ambiguity set of the mixture distributions that hedge against the weight misspecification is
U(P̂) , { Q : ∃p ∈ ∆, ∃Qk ∈ Bk(P̂k) ∀k ∈ [K] such that Q ∼ (Qk, pk) } ,
where the component sets Bk(P̂k) are defined as in Section 3. The DiRRAc problem with respect to the ambiguity set U(P̂) becomes
min sup P∈U(P̂) P(Cθ̃(x) = 0) s. t. c(x, x0) ≤ δ sup
Qk∈Bk(P̂k) Qk(Cθ̃(x) = 0) < 1 ∀k ∈ [K].
(12)
It is important to note at this point that the feasible set of (12) coincides with the feasible set of (2). Thus, to resolve problem (12), it suffices to analyze the objective function of (12). Given the function φ, we define its conjugate function φ∗ : R→ R ∪ {∞} by
φ∗(s) = sup t≥0 {ts− φ(t)} .
The next theorem asserts that the worst-case probability under U(P̂) can be computed by solving a convex program.
Theorem C.2 (Objective value). The feasible set of problem (12) coincides with X . Further, for every x ∈ X , the objective value of (12) equals to the optimal value of a convex optimization problem
sup P∈U(P̂) P(Cθ̃(x) = 0) = minλ∈R+, η∈R η + ελ+ λ ∑ k∈[K] p̂kφ ∗ (fk(x)− η λ ) ,
where fk(x) 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 P∈U(P̂) P(Cθ̃(x) = 0) = sup p∈∆ sup Qk∈Bk(P̂k) ∀k ∑ k∈[K] pkQk(θ̃>x ≤ 0)
= sup p∈∆ ∑ k∈[K] pk × sup Qk∈Bk(P̂k) Qk(θ̃>x ≤ 0)
= sup p∈∆ ∑ k∈[K] pk × fk(x),
where the equality in the second line follows from the non-negativity of pk, and the last equality follows from the definition of fk(x) in (5). By applying the result from Ben-Tal et al. (2013, Corollary 4.2), we have
F (x) =  min η + ελ+ λ ∑ k∈[K] p̂kφ ∗ (fk(x)− η λ ) s. t. λ ∈ R+, η ∈ R.
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 al., 2009, Theorem 7.21), or simply using auto-differentiation. Furthermore, φ∗ is convex, and thus solving the minimization problem in Theorem C.2 can be 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 unfavorable outcome over all K components. Mathematically, if we opt for the component ambiguity sets Bk(P̂k) constructed in Section 3, then we can solve
min max k∈[K] sup Qk∈Bk(P̂k) Qk(Cθ̃(x) = 0) s. t. c(x, x0) ≤ δ sup
Qk∈Bk(P̂k) Qk(Cθ̃(x) = 0) < 1 ∀k ∈ [K].
(13a)
Interestingly, problem (13a) does not involve the mixture weighs p̂. As a consequence, a trivial advantage of this model is that it hedges automatically against the misspecification of p̂. To complete, we provide its equivalent finite-dimensional form.
Corollary C.3 (Component Probability DiRRAc). Problem (13a) is equivalent to
min x∈X max k∈[K]
ρkθ̂ > k x‖x‖2 + √ x>Σ̂kx √ (θ̂>k x)
2 + x>Σ̂kx− ρ2k‖x‖22 (θ̂>k x) 2 + x>Σ̂kx . (13b)

heading: D EXTENSIONS OF THE GAUSSIAN DIRRAC FRAMEWORK
text: 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 BNk (P̂k) is of the form
BNk (P̂k) = { Qk : Qk ∼ N (θk,Σk), G((θk,Σk), (θ̂k, Σ̂k)) ≤ ρk } ,
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 ∈ [0, 1]K : 1>p = 1, Dφ(p ‖ p̂) ≤ ε } and the ambiguity set with Gaussian information is defined as
UN (P̂) = { Q : ∃p ∈ ∆, ∃Qk ∈ BNk (P̂k) ∀k ∈ [K] such that Q ∼ (Qk, pk)k∈[K] } .
The distributionally robust problem with respect to the ambiguity set U(P̂) is
inf sup P∈UN (P̂) P(Cθ̃(x) = 0) s. t. c(x, x0) ≤ δ sup
Qk∈BNk (P̂k) Qk(Cθ̃(x) = 0) < 1 2 ∀k ∈ [K].
(14)
Following the results in Section 4, the feasible set of (14) coincides with the set X . It suffices now to provide the reformulation for the objective function of (14). Corollary D.1. For any x ∈ X , we have
sup P∈UN (P̂) P(Cθ̃(x) = 0) =  inf η + ελ+ λ ∑ k∈[K] p̂kφ ∗ (fNk (x)− η λ ) s. t. λ ∈ R+, η ∈ R,
where the values fNk (x) are obtained in Proposition B.2.
Corollary D.2 follows from Theorem D.2 by replacing the quantities fk(x) by fNk (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 DiRRAc that minimizes the worst-case modal probability of infeasibility. More concretely, we consider the recourse action obtained by solving
inf max k∈[K] sup Qk∈BNk (P̂k) Qk(Cθ̃(x) = 0) s. t. c(x, x0) ≤ δ sup
Qk∈BNk (P̂k) Qk(Cθ̃(x) = 0) < 1 2 ∀k ∈ [K].
(15a)
The next corollary provides the equivalent form of the above optimization problem. Corollary D.2. Problem (15a) is equivalent to
inf x∈X max k∈[K] 1− Φ (
(θ̂>k x) 2 − ρ2k‖x‖22
θ̂>k x √ x>Σ̂kx+ ρk‖x‖2 √ (θ̂>k x) 2 + x>Σ̂kx− ρ2k‖x‖22 ) . (15b)
Algorithm 1 Projected gradient descent algorithm with backtracking line-search Input: Input instance x0, feasible set Xε and objective function f Line search parameters: λ ∈ (0, 1), ζ > 0 (Default values: λ = 0.7, ζ = 1) Initialization: Set x0 ← ProjXε(x0) for t = 0, . . . , T − 1 do
Find the smallest integer i ≥ 0 such that
f ( ProjXε(x t − λiζ∇f(xt)) ) ≤ f(xt)− 1
2λiζ ‖xt − ProjXε(x t − λiζ∇f(xt))‖22.
Set xt+1 = ProjXε(x t − λiζ∇f(xt)).
end for Output: xT

heading: E PROJECTED GRADIENT DESCENT ALGORITHM
text: The pseudocode of the algorithm is presented in Algorithm 1. The convergence guarantee for Algorithm 1 follows from Beck (2017, Theorem 10.15), and is distilled in the next theorem. Theorem E.1 (Convergence guarantee). Let {xt}t=0,1,...,T be the sequence generated by Algorithm 1. Then, all limit points of the sequence {xt}t=0,1,...,T are stationary points of problem (4) with the modified feasible set Xε. Furthermore, there exists some constant C > 0 such that for any T ≥ 1, we have
min t=0,1,...,T ∥∥xt − ProjXε (xt − ζ∇f(xt))∥∥2 ζ ≤ C√ T .

Review summaries:
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.   They 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. 

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.