Covariance-Robust Minimax Probability Machines for Algorithmic Recourse
Authors: Ngoc Bui
Duy Nguyen
Kim-Cuc Nguyen
Man-Chung Yue
Viet Anh Nguyen
Venue: Submitted to ICLR 2023 (2023)
Keywords: Optimization and Learning under Uncertainty
Algorithmic Recourse
Trustworthy ML and Statistics

Abstract: Algorithmic recourse is rising as a prominent technique to promote the explainability and transparency of the predictive model in ethical machine learning. Existing approaches to algorithmic recourse often assume an invariant predictive model; however, this model, in reality, is usually updated temporally upon the input of new data. Thus, a recourse that is valid respective to the present model may become invalid for the future model. To resolve this issue, we propose a pipeline to generate a model-agnostic recourse that is robust to model shifts. Our pipeline first estimates a linear surrogate of the nonlinear (black-box) model using covariance-robust minimax probability machines (MPM); then, the recourse is generated with respect to this robust linear surrogate. We show that the covariance-robust MPM recovers popular regularization schemes, including l_2-regularization and class-reweighting. We also show that our covariance-robust MPM pushes the decision boundary in an intuitive manner, which facilitates an interpretable generation of a robust recourse. The numerical results demonstrate the usefulness and robustness of our pipeline. 

Under review as a conference paper at ICLR 2023
COVARIANCE-ROBUST MINIMAX PROBABILITY MA- CHINES FOR ALGORITHMIC RECOURSE
Anonymous authors Paper under double-blind review
ABSTRACT
Algorithmic recourse is rising as a prominent technique to promote the explainabil- ity and transparency of the predictive model in ethical machine learning. Existing approaches to algorithmic recourse often assume an invariant predictive model; however, this model, in reality, usually updated temporally upon the input of new data. Thus, recourse that is valid respective to the present model may become invalid for the future model. To resolve this issue, we propose a pipeline to generate a model-agnostic recourse that is robust to model shifts. Our pipeline first estimates a linear surrogate of the nonlinear (black-box) model using covariance-robust mini- max probability machines (MPM); then, the recourse is generated with respect to this robust linear surrogate. We show that the covariance-robus MPM recovers popular regularization schemes, including fg-regularization and class-reweighting. We also show that our covariance-rov crrbuus MPM pushes the decision boundary in an intuitive manner, which facilitates interpretable generation of robust recourse. The numerical results demonstrate the usefulness and robustness of our pipeline.
INTRODUCTION
The recent prevalence of machine learning (ML) in supporting consequential decisions involving humans such as loan approval (Moscato et al. (021). ). job hiring (Cohen et al.) [201 Schumann et al. 2020), and criminal justice (Brayne & Christin (021]) urges the need of transparent ML systems with explanations and feedback to users (Doshi-Velez & Kim 2017 Miller 2019). One popular and emerging approach to providing feedback is the algorithmic recourse (Ustun et al. 2019). recourse suggests how the input instance should be modified to alter the outcome of a predictive model. Consider a specific scenario in which an individual is rejected from receiving a loan by a financial institution's 's ML model. Recently, it has become legal necessity to provide explanations and recommendations to the individual so that they can improve their situation and obtain a loan the future (GDPR, Voigt& & Von dem Bussche (2017). For example, an explanation can be "increase the income to $5000" or "reduce the debt/asset ratio to below 20%" Leveraging the recourses, financial institutions can assess the reliability of their MI predictive models and increase user engagement through actionable feedback and acceptance guarantee if they fulfill the requirements.
To construct plausible and meaningful recourses, one must assess and strike balance between conflicting criteria. They can be: (1) validity, a recourse should effectively reverse the unfavorable prediction of the model into favorable one, (2) proximity, recourse should be close the original input instance to alleviate the efforts required, and thus to encourage the adoption of the recourse, (3) actionability, preseribed modifications should follow causal laws of our society (Ustun al. 2019 Karimi et al.) 202T); for example, one can not modify their race or decrease their age.
Various techniques were proposed to devise algorithmic recourses for given predictive model, extensive surveys are provided in (Karimi et al. [2000a] [Stepin et al., 2021 Pawelczyk et al.] 2021 Verma et al. 2020). |aachter et al. (2017) introduced the definition of counterfactual explanations and proposed gradient-based approach to find the nearest instance that yields favorable outcome. Ustun et al. (009)) proposed mixed integer programming formulation (AR) that can find recourses for a linear classifier with flexible design of the actionability constraints. Alternatively, Karimi et al. [202T] 2020b) investigated the nearest recourse through the lens of minimal intervention to take causal relationships between features into account. Recent works including Russell (0019)

---

Under review as a conference paper at ICLR 2023
and Mothilal et al. (2020) also studied the problem of generating menu of diverse recourses to provide multiple possibilities that users might choose.
The aforementioned methods rely
assumption of invariant predictive model. Nevertheless, machine learning models are usually re- re-trained or re-calibrated as new data arrive. Thus, a valid recourse present may become invalid in the future, leading to exemplary case where rejected applicant may spend efforts to improve their income and reapply for a loan, but then is rejected (again) simply because the ML model has been updated. This leads potential inefficiency due to the waste of resources and loss of trust in the recommendation and in the ML system (Rudin) 2019).
Studying this phenomenon, Rawal et al. (020)) described several types of model shifts related to the correction, temporal, and geospatial shifts from data. They pointed out that the recourses, even constructed with state-of-the-an algorithms, are vulnerable to distributional shifts in the model's parameters. Pawelczyk et al. (2020) study counterfactual explanations under predictive multiplicity and its relation to the difference in the way two classifiers treat predicted individuals. |Black al.) (2021) then show that the constructed recourses might be invalid even for the model retrained with different initial conditions such as weight initialization and leave-one-out variations in data. Recently, Upadhyay et al. (202T) leveraged robust optimization to propose ROAR framework for generating recourses that are robust to shifts in the predictive model, which is assumed to be a linear classifier.
Despite the promising results, existing methods are often restricted to the linear classifiers setting to be able to introduce actionability or robustness (Ustun et al., 2019; Russell 2019 Upadhyay et al. 2021 Rawal et al. 2020). For non-linear classifiers, linear surrogate method such LIME (Ribeiro et al. 2016 is used to approximate the local decision boundary of the black- boo classifiers; the recourse is then generated respectively the (linear) surrogate model instead of the nonlinear model. LIME is well-known for explaining predictions of black-box ML models by fitting a reweighted linear regression model to the perturbed samples around an input instance. In the recourse literature, LIME is the most common linear surrogate for the local decision boundary of the black-box models (Ustun
al. 2019 Upadhyay al. 202I).
Unfortunately, the LIME surrogate has several limitations. Firstly, Laugel et al. (018) and White & Garcez (2019) showed that LIME may not be faithful to the underlying models because LIME might be influenced by input features at global scale rather than local scale. Secondly, explanations generated by perturbation- -ased methods are also well-known to be sensitive to the original input and
the synthesized perturbations (Alvarez-Melis & Jaakkola 2018 Ghorbani et al. 2019: Slack et al.
2020 2021 Agarwal et al. 2021 Laugel et al. (0188).
Several works have been proposed to overcome these issues. Laugel et al. 2018 and Vlassopoulos (ct al. (2020) proposed alternative sampling procedures that generate sample instances in the neigh- borhood of the closest counterfactual to fit a local surrogate. WWite & Garcez (2019) integrated counterfactual explanation to local surrogate models to introduce a novel fidelity measure of an ex- planation. Later, Garreau & von Luxburg (2020) and (Agarwal et al. (2021 analyzed theoretically the stability of LIME, especially in the low sampling size regime. Zhao et al. (021) leveraged Bayesian reasoning to improve the consistency in repeated explanations of single prediction. Nevertheless, the impact and effectiveness of these surrogates on the recourse generation are still unknown.
Contributions. We revisit the recourse generation scheme through surrogate models. We propose a novel model-agnostic pipeline that facilitates the generation of robust and actionable recourses. The core innovation in our pipeline is the use of the covariance-robuss minimax probability machines (MPM) as a linear surrogate of the nonlinear black-box ML model. Additionally, we contribute
to the field of MPM and robust classifier: We propose and analyze in detail the covariance-robut MPMs in which the set of possible perturbations of the covariance matrices are prescribed using distances on the space of positive semidefinite matrices. Motivated by the statistical distances between Gaussian distributions, show that the rovariance-robustness induces and connects to two prominent regularization schemes of the nominal MPM:
if the distance is motivated by the Bures distance, we recover the Eg-regularization, if the distance is motivated by the Fisher-Rao distance, we recover class reweighting schemes.
'Throughout, "robustness" is used in the algorithmic recourse setting with respect to the model shifts (Raaal al. 2020). "Robustness" is also used to indicate the sensitivity of L.ME. to the sampling distribution. To avoid confusion, what follows, we use "stability" to refer the aforementioned sensitivity of LIME.
2

---

Under review as a conference paper at ICLR 2023
black-bax clessrirr f
Estmato
(1-1; 1
d
dr
instance
Boundary Sampler
Covariance-robust MPM
Recourse Search
Figure 1: The sampler synthesizes new instances around Zo and queries the predicted labels from the classifier f- The moment information (Fy, E.yy) estimated from the synthetic psedo-labeled data (represented by triangles and ellipsoids) serves as inputs for the Covariance-robur, MPM. The MPM surrogate d (red hyperplane) the target classifier used generate recourses (red circle).
While prior works showed that distributionally robust optimization (DRO) with optimal transport distance recovers norm regularization (Shafiezadeh--bbadee et al. 2019b) and f-divergence DRO leads to reweighting (Duchi & Namkoong, 2019), this paper extends the connections to the MPMs.
to the field of robust algorithmic recourse: We propose an intuitive and interpretable approach generate robust recourse. We show that, by calibrating the radii of the ambiguity sets proper manner, the covariance-robuss MPM shifts the separation hyperplane towards the favorable class. As consequence, our recourse exhibits robustness to model shifts and is also lenient to incorporate mixed-intee constraints to promote actionability.
This paper unfolds as follows. Section 2 we delineate our explanation framework using MPM. Section 3 dives deeper into the MPM problem and its robustification. Section construct two types of covariance-robust MPM using the Bures and Fisher-Rao distance on the space of covariance matrices. Section G we demonstrate empirically that the covariance-robus: MPM provides competitive approximation of the local decision boundary, and improves the robustness of the recourse subject model shifts. All proofs are relegated the appendix.
RECOURSE GENERATION FRAMEWORK
Throughout this paper, we assume that the covariate space X' Rd and we have binary label space ) = (-,,--1 Without any loss of generality, we assume that label -1 encodes the unfavorable decision, while +1 encodes the favorable one, Given a specific classifier and an input 2o with an unfavorable predicted outcome, the goal of this paper is to find recourse recommendation for zo that has a high probability of being classified into favorable group, subject to possible shifts in the parameters underlying the classifier. Such recourse is termed a robust recourse. Our robust recourse generator consists of three components (see Figure for schematic view):
(i) local sampler: we use similar procedure as in Vlassopoulos (2018). Given an instance Ty. we choose k nearest counterfactuals T1, Ti,..., Ty from the training data that have the opposite label Zp. For each 2,, we perform line search to find point øb,; that is on the decision boundary and the line segment between Zo and x;, Among Tb,s, we choose the nearest point dı to To and sample uniformly in an fz-neighborhood with radius Tp around st. We then query the black-box classifier to obtain the predicted labels of the synthetic samples.
(2020) and Laugel al.
(ii) a linear surrogate using (covariance-robus)) MPM: We use the synthetic samples to estimate the moment information (Piy Σ,y)) of the covariate conditional on each predicted class y. We then train a covariance-robust MPM parametrized by (PP to approximate the local decision boundary of the ML model.
(iii) a recourse search: Basically, we can apply any existing recourse search for linear models on top of the linear surrogate 8 dictated by the covariance-robhe MPMs find robust recourse. In this paper, we use a simple projection onto the hyperplane prescribed by 8 for simplicity and AR (Ustun et al. 2019), which a MIP-based framework, to promote actionable recourses.
Center to the success of our pipeline is the possibility of shifting the MPM classification hyperplane toward the region of the favorable class, which induces robust recourse with respect to model shifts in geometrically-intutte manner (see Remark 4.6 for detailed discussion). It is imperative to

---

Under review as a conference paper at ICLR 2023
note clear distinction between pipeline and the existing method of ROAR (Upadhyay al. 2021): ROAR uses a non-robust surrogate in Step (ii) and then formulates a min-max optimization problem in Step (iii) for recourse search, whilst our pipeline uses robust surrogate in Step (ii) and then employs a simple recourse search in Step (iii). Note that mixed-integer formulations can be injected in Step (iii) generate more realistic robust recourses in our pipeline. On the contrary, mixed-integer constraints are not casy to be integrated into the min-max formulation of ROAR.
Subsequently, Sections describe in detail different methods build robust surrogates in Step (ii). The application of recourse research in Step (iii) is provided in the experiment section (Section 6.2
3 CCOVARIANCE-ROBUSS MPM
MPM is a binary classification framework pioneered by Lanckriet et al. (2001) and extended to Quadratic MPM in (Lanckriet et al., 2003). For each class y E V. MPM makes no assumption on the specific parametric form of the (conditional) distribution P of X|Y y. Instead, MPM assumes that we can
(6.s. 2.i]
Be Eic)
P-1
P-j - 0.p-a - 10
identify Fy only up to the first two moments, i.e., it assumes that I has mean vector Thy E Rd and co- variance matrix Σ, E $4. denoted Pp (Ty, Ey). These moments can be estimated from the samples synthesized from the boundary sampler. The goal of MPM is to find a (non-trivial) linear classifier that minimizes the maximum misclassification rate among classes. To this end, we consider the family of linear classifiers parametrized by (w, b) E gd+1
Figure 2: An intuitive explanation of the ro- bustification mechanism. From left to right: As the radius p-1 increases, the worst-case covariance matrix the class - inflated and shifts the MPM boundary towards the fa- vorable class. The projection of the input zo onto the hyperplane will have tendency to lie deeper into the favorable region and may become more robust to model shifts.
w * 0 with classification rule
(x(x) = sign(w) b), b).
where (w, b) is the slope and intercept. The MPM solves the min-max optimization problem
min max EE
max vEy
(x( #))
P. EPp
where we define the feasible set θ A 10 (w, gd+1, + 03. Notice that the constraints w f 0 eliminate trivial solutions to the classification problem.
To derive the MPM, we define the set of feasible slopes W w E Rd Evey you
which is hyperplane in Rdd The main instrument for solving T is the following result from Lanck
riet et al. 2001 $2) which provides the form of its optimal solution.
Lemma 3.1 (Optimal solution). Let w be an optimal solution to the second-order cone program
Σ V / Engm,
min WEW
then Ø (w, b) solves the MPM problem where = (Ever V and TTP+1
Ry T E41
In this paper, we refer to the second-order cone program as the nominal MPM problem, because the MPM fully determined by the solution to (2). We next discuss the covariance-robust MPM.
3.1 QUADRATIC MPM
In practical setting, it is likely that the covariance matrices En are misspecified, for example, due to low sample size, statistical estimation error, corrupted data. To hedge against these mismatches, Lanckriet et al. (2003) proposed to add another layer robustness by allowing the mean vectors and the covariance matrices of the conditional distributions to be chosen (adversarially) in preseribed set,
4

---

Under review as a conference paper at ICLR 2023
which we call the ambiguity set. They showed that perturbing the mean vectors does not change the optimal classifier. In this paper, we, therefore, perturb only the covariance matrices. More specifically, we allow the conditional distribution py to be in the ambiguity set
Uy(P,)) = (py: Py ~ (Fyy Ey), p 5 where is measure of dissimilarity between covariance matrices. The distributionally robust minimax probability machine formulated
min max O5
(y)Co(X) v).
yEy ()EU((F))
Previously, Lanckriet al. (2003) considered the robust MPM with moment uncertainty, in which
the covariance matrix is perturbed using the quadratic divergence.
Definition 3.2 (Quadratic divergence). Given two positive semidefinite matrices E, E s4. the
quadratic divergence between them is Q(E Σ) Tr [(E [E.].
The divergence Q is the squared Frobenius norm of Σ E3 thus Q is non-negative and vanishes to zero if and only if Σ Σ, so it is a divergence on s4. The Quadratic MPM has the below form (Lanckriet et al. 2003).
Theorem 3.3 (Quadratic MPM), Suppose that t = Q Let w be a solution to the problem
min Σ, wEW
yey V / (Sey + Vp
(4)
Then 0 ( (9) solves the distributionally robust MPM problem (3 with
n EnEy ((W (PxT)wa)= 8 (w F441 18 ( (É-1 vP4I/)w9.
The Quadratic MPM can be considered as a regularization of the nominal problem 2 each matrix En is added with diagonal matrix vpyl, making the matrix better conditioned. This is equivalently known as inverse regularization, which ensures invertibility when E. is low-rank and Py >
3.2 COVARIANCE-ROBUS ROBUST MPM
While Lanckriet et al. (2003) focused only the quadratic divergence, their results can be generalized
to the covariance-robust MPM with general divergence yp. For any y V, define Ty .Rdd - RR. as
(r))
max ( 1
w Eyw.
(5)
E. ES4
We are now ready give generalized reformulation of problem (3.
Proposition 3.4 (Covariance-robus MPM). Let w be the optimal solution to the problem
min WEW
Σ " (1:),
then 8P (wf, bP) solves the distributionally robust MPM problem where
k2 EE wEy Ty (W))))
and b = (wP) f+1 x2 PL (w
3.3 EQUIVALENCE UNDER GAUSSIAN ASSUMPTIONS
While the quadratic divergence Q in Definition 3.2 is attractive for its tractability, it not statistically meaningful. More specifically, it does not coincide with any distance between probability distributions with the corresponding covariance information. In this paper, we consider discrepancy measures that arise as statistical distance between Gaussian distributions. To this goal, we first need to show that the covariance-robust MPM is invariant with the Gaussian assumption. Define a parametric ambiguity set constructed on the space of Gaussian distribution of the form
U (1 {P,, E P(X): Py ~ (P,, Ey), (E, || ΣS < }3)
wherein any distribution Gaussian. Consider the Gaussian distributionally robust MPM problem (C)(C(( + v). P.EUY (B,)
min max yEY
max
(6)
5

---

Under review as a conference paper at ICLR 2023
Proposition 3.5 (Gaussian equivalence). The optimizer 8 = (w bb) in Proposition alao solves the Gaussian parametric covariance-robute MPM problem (6).
Proposition 3.5 justifies the use of divergences induced by distance between normal distributions.
We study several constructions of the covariance-robust MPM in the subsequent sections.
BURES MPM
We first explore the case where is the Bures divergence whose definition is follows.
Definition 4.1 (Bures divergence). Given two positive semi-definite matrices E, Σ 84, the Bures divergence between them is BB Σ) = Tr [ - )
It can be shown that B is symmetric and non-negative, and it vanishes to zero if and only if = Σ. As such, IB is divergence on the space of positive semidefinite matrices. Moreover, B also equals the squared type-2 Wasserstein distance between two Gaussian distributions with the same mean vector and covariance matrices E and Σ (Olkin & Pukelsheim 1990). Next, we assert the form of the Bures MPM.
1982. Givens & Shortt 1984 Gelbrich
Theorem 4.2 (Bures MPM). Suppose that up = B. Let w
be the solution of the following problem
EyeD E
V
+ Eyeype) 110112. 1ulll2
min NEW
Then @B (woB, BB) ) is the optimal solution of the distributionally robust MPM problem (3) where
r (Ewer ((wD)) EyuB + E yEy Py) Py)
and
B = (u4))
- 16 1B (V (oB))T+1uu + p+1 112)
Theorem 4.2 unveils fundamental connection between robustness and regularization: if we construct the ambiguity sets for the covariance matrices using the Bures divergence, the resulting optimization (2). This connection aligns with previous observations highlighting the equivalence between regularization schemes and optimal transport robustness (Shaticezadeh-Abllee Abbdeh et al. 2019a Blanchet et al. 2019).
problem (7) an Iz-regularization of the nominal problem
To prove Theorem 4.2
provide result that asserts the analytical form of T (ww).
Proposition 4.3 (Bures divergence). If B, then Ty (w) Pyl|w|la + v w Enw for all y E V.
The proof of Theorem 4.2 follows by combining Propositions 3.4 and 4.3
Next, we study the asymptotic form of the Bures MPM as the radii of the ambiguity sets grow. Note that problem ( depends only on the sum of the radii, but not on the individual values of each radius. Let p == Eyey Py be their sum, it suffices to study when p grows to infinity. To this end, denoted by w the optimal solution of problem ? parametrized by p. The next result provides the analysis of the asymptotic value of w as p + oo.
-0.
-1.3
Proposition 4.4 (Bures asymptotic hyperplane). Fix V, let -y be its opposite class and suppose that p-y remains constant. Let w be the optimal solution of (7) parametrized by Py. As Py + 0c,
Figure 3: A 2D example of the Bures MPM hyperplanes with fixed p+1 0 and p-
wB
+
B Woo
NEy w(a) / E wey yi
0.01 (red) and p-1 = 10 (green). The green line is pushed towards the favorable region (predicted as +1).
Notice that as Py + 00, BBB (w Thus, bE (w By for any V. The asymptotic hyperplane defined by w is thus characterized by the linear equation w w + 0, which identifies hyperplane passing through П- Evey you My asymptotic hyperplane does not depend the covariance matrices.
Moreover, we note that the

---

Under review as a conference paper at ICLR 2023
Remark 4.5 (Quadratic asymptotic hyperplane). It is provable that the solution of problem converges to wxx as p Ey py tends to infinity. Thus, Quadratic MPM and Bures MPM 7 asymptotically equivalent even though they induce different regularizations of the nominal MPM
are
Remark 4.6 (Geometric intuition for robust recourse). Figure 3 visualizes the Bures MPM hyper- planes by varying the radii. Notice that the hyperplane drifts toward the favorable (+1) class as the uncertainty of the unfavorable (-1) covariance matrix increases. Thus, the recourse generated w.r.t the green hyperplane more robust compared to that generated w.r. the red one. By calibrating the radii, we shift the hyperplane and obtain robust recourses at different robustness-cost trade-offs.
5 FISHER-RAO MPM
We now explore the case where yp is the Fisher-Rao distance which defined as follows.
Definition 5.1 (Fisher-Rao distance). Given two positive definite matrices Σ. E. $4 $44, the Fisher- Rao distance between them is F(E,
log(E - - 1)2,, where log( () is the matrix logarithm.
The Fisher-Rao distance enjoys many nice properties. In particular, it is invariant to inversion and congruence, i.e., for any Σ + and invertible A E Raddd F(E, Σ) FEE FEE-,,511)
F(AEAT, T) Such invariances are especially statistically meaningful as it implies that the results remain unchanged we reparametrize the problem with an inverse covariance matrix (instead of the covariance matrix) or apply a change of basis to the data space X. It is shown that F is the unique Riemannian distance (up to scaling) on the cone Sd with such invariances (Savage 1982 Next, we assert the form of the Fisher-Rao MPM.
Theorem 5.2 (Fisher-Rac Rao MPM). Suppose that y = F. Let wº be the solution of the problem
min WEW
Σ
yEy exp
(w) V V
8
Then OF (WF, (WFFbF) 6.²)) is the optimal solution of the distributionally robust MPM problem
3 where
F
cxp
(yy 2
/ (w=F) ( " and b = (w ) - R= exp (P+1) 2
cxp
( (WF)TS41u E
V
VEY
Theorem 5.2 divulges another foundational connection between robustness and regularization: if we construct the ambiguity sets for the covariance matrices using the Fisher-Rao distance, the resulting optimization problem (8) is a reweighted version of the nominal problem 2 Each term (w w) assigned weight exp(py/2), which is proportional to the radius Py- This connection aligns with previous observations highlighting the equivalence between reweighting schemes and distributional robustness (Ben-Tal al. 2013 Bayraksan & Love 2015 Namkoong & Duchi 2017 Hashimoto
et al. 2018 To prove Theorem 5.2 we derive an analytical expression of T (w()).
Proposition 5.3 (Fisher-Rao distance). I = F, then T (w) = exp (oz) (w Tu)) 2 for all y E V.
The proof of Theorem 5.2 follows by combining the results from Proposition 3.4 and Proposition 5.3 Next, we study the asymptotic form of the Fisher-Rao MPM.
Proposition 5.4 (Fisher-Ra) asymptotic hyperplane). Fix y E y, let -y y be its opposite class and suppose that p-y remains constant. Let w be the optimal solution of (8) parametrized by Py- Let
a A EyEy yr then as Py - oc, Wp - w 50.0
A (a ( 1) "
Contrary to the Bures MPM, the asymptotic hyperplane of Fisher-Rao MPM depends explicitly on the covariance matrix Ey,. The boundary prescribed by the Risher-Rao MPM can shifted through an appropriate calibration of the radii py. Thus, Fisher- Rao MPM can generate robust algorithmic recourse in a geometrically-ininee inttuiitvv manner.
NUMERICAL EXPERIMENTS
We conduct comprehensive experiments to highlight the performance of our models. We first compare the fidelity and stability of our surrogates with LIME, We then compare the quality of our recourses against two popular baselines: ROAR (Upadhyay et al. 2021) and AR (Ustun al. 2019
7

---

Under review as a conference paper at ICLR 2023
Classifier. We use three-layer MLP with 20, 50, 20 nodes and ReLU activation functions in each consecutive layer. We use a sigmoid function in the last layer to produce probabilities.
Dataset. We evaluate our framework using popular real-world datasets for algorithmic recourse: German Credit (Dua & Graff 2017; Groemping 2019), Small Bussiness Administration (SBA) (Li et al. 2018), and Student performance (Cortez & Silva 2008). Each dataset contains two sets of data (the present data- - Dj and the shifted data D2). The shifted dataset D2 could capture the correction shift (German credit), the temporal shift (SBA), or the geospatial shift (Student). For each dataset, we use 80% of the instances in the present data Dj to train an underlying predictive model and the remaining instances are used to generate and evaluate recourses. The shifted data D2 is used to train future classifiers in Section 6.2] The main text contains the results for the German and Student datasets. Further results, including the SBA and the synthetic data, are provided in Appendix A
6.1 FIDELITY AND STABILITY OF THE SURROGATE MODELS
We evaluate the performance of different surrogate models with respect to the current classifier. We compare our methods: QUAD-MPN, in (33).. the BW-MPM in (4.) and the FR-MPM in (.2)
against the popular linear surrogate LIME (Ribeiro et al. 2016) under the following metries:
Stability. We use the procedure in Agarwal et al. (202T) measure the stability of the surro- gate models with respect to small perturbations in the input instance. For a given instance x, we draw a set Uz of 10 neighbors of x from N(x, 0.001 7) independently. We use the above- mentioned methods to find the linear surrogate 0r (Wg'. bz.) for each x' E Ug. We report the maximum distance of the explanations of x' to that of x; precisely, the stability formula
German
Student
Fidiiiy
0.80
0.98
0.78
0.96
0.75
0.94
0.73
20a
Gemman
Student
0.40
0.30
Spaiii
0.20
Stability(ws) = max, EM, ||u, Wa 1|2-
0.10
Fidelity. We use the LocalFid criterion as in Laugel et al. (2018) to measure the fidelity of local surrogate model. For given instance x, we draw a set V2 of 1000 instances uniformly from an l2-ball of radius rnd centered æ. The local fidelity of the surrogate 0g is measured as:
10>
10
102
10
samples
QUAD-NPM
BW:MPM
FPMMPM
Figure 4: Benchmarks of fidelity and stability on the German and Student dataset. Higher local fi- delity and lower stability are better.
LocalFid(Oa)= Vi Exev, lIf(x') Co2 (x')1l2,
where f(-) is the original classifier and Co(.) ) is the linear surrogate classifier. Basically, LicalFid measures the fraction of instances where the output class of f and Co agree. Here, we set rad to 10% of the maximum distance between instances in the training data. Note that V. is for evaluation only and independent from the perturbation samples used to train the local surrogate.
To generate the MPM's surrogates, we choose 10 nearest counterfactuals of zg in training data find Tb. We set the perturbation radius Pp to 5% of the maximum distance between instances in the training data and set p+1 0, p-1 1.0. For LIME, we use the default parameters recommended in the LIME source code and return 0 = (w, b- 0.5) as the LIME's surrogate, similar to Laugel et al. (2018). We vary the number of perturbation samples in range of [500, 10000] to measure the fidelity and sensitivity of constructed surrogates under low sampling sizes. The results on German and Student datasets are shown in Figure [ The results show the superiority of MPM's surrogates compared to LIME in both local fidelity and stability metrics. Meanwhile, FR-MPM provides higher-fidelity surrogates compared to QUAD-MPM and BW-MPM.
6.2 ROBUSTNESS OF RECOURSES
We now study the robustness to model shifts of recourses and its trade-off against the recourse cost. Metrics. We use an & diddistance as the cost function. We define the current validity as the validity of the generated recourses with respect to the given classifier. To measure the validity of recourses under
8

---

Under review as a conference paper at ICLR 2023
the model shifts, we sample 80% instances of the shifted data D2 100 times train 100 'future' MLP classifiers. We then report the future validity of recourse as the fraction of the future classifiers with respect to which the recourse is valid.
The experiment in Section 6.1 suggests that the Fisher-Rao model can be used to represent the class of covariance- MPM as the linear surrogate OF = (w" bF) and a simple projection to generate recourse by finding Iy = arg min { | zoll1 x
Baselines.
Table I: Performance of competing algorithms on real datasets. For the current and future valid- ity, higher is better. For the cost, lower is better. Bold indicates the best performance.
MPM. We use FR-
T T==" + 6" 2 0}.
German credit
Methol
We compare the above method, namely FR- MPM-PROJ, against strong baselines, including Wachter (Wachter et al. (017) and ROAR (Upad- hyay et al., (021)) using LIME (Ribeiro et al., 2016), CLIME (Agarwal et al. (021), and LIMELS (Laugel et al., 2018 as surrogates. Comparisons with ROAR using the vanilla MPM and SVM surrogates are in Appendix/A.2
Vafidity
Valudity
Wachter
0,42 +: 0.02
1,00 = 0.00
0.52 0.03
LIME-PROI LIME-ROAR CLIME-ROAR
0.10
0.51
1.09 0.19
0.66 = 0.15
0.64 = 0.08
+.45
0.76 = 0.17
0.72
LIMELS ROAR
1.29:00.7
0.88 = 0.03
0.79 0.02
QUAD-MPM-PPR
0.90
0.89 = 0.05
0,76 0.03
RW-MPPMPROO
1.03+ 0.02
0.93
0.78
FR MRO.
1.01 0.02
0.94
0.03
0,78 D.01
German
Student
1.00
1:00
Cumont Valant
Cost-validity trade-off. We fix the number of perturbation samples to 1000 and vary the ambi-
0.80
0.60
0.60
guity size (p+1 0, p-1 E [0, 10) for FR-MPM-
0.40
PROJ and mma E [0, 0.2] for the uncertainty size of ROAR). We then plot the Pareto frontiers of the cost-validity trade-off in F Generally, increasing the ambiguity size will increase both the current and future validity of recourses, but induces sacrifice in the cost. This result consis-
0.20
0.25
1.00
1:25
Gorman
Student
Futre Valdday
0.80
0.70
0.60
0.60
tent with the analysis in Rawal et al. (2020). How- ever, the frontiers of FR-MPM-PROL. dominate the frontiers of LIME-ROAR, CLIME-ROAR, and LIMELS-ROAD Note that we use CARLA's im- plementation with default parameters for Wachter and its higher cost compared to the linear surro- gate's methods the Student dataset is consistent with results in Upadhyay et al. (021) and Pawelczyk et al. (202T). T shows the performance of FR-MPMMPROO
0.50
0.40
0.25
0.50
0,75 1.00
1:25
Cost
Cost
LIME ROAR CLIMERROAR
LIMELS-ROAR FR-MPA-PRO)
Wachtee
Pareto frontier of the cost-validity trade-off on the German and Student datasets.
Figure 5:
methods uncertainty size mmx = 0.2. Here, the FR-MPM-PPR has similar future validity compared to LIMELS-ROAR, but lower cost and higher current validity. Further results and discussion are in Appendix A.2
radii P+1 O. P-1 10 and of ROAR
Actionability. By introducing robustness into the linear surrogate model, our method can use AR (Ustun et al. 2019) as a recourse search mech- anism to promote flexible actionability constraints. In Table 2 we compare the AR performance us- ing different surrogate models (LIME, CLIME, LIMELS, SVM, MPMs). We consider the re- course under some actionability constraints such as immutable race, gender, non-decrease age (see Appendix A. for more details on the action- ability constraints). The result shows that AR using FR-MPM as the linear surrogate increases both the current and future validity substantially
Table 2: Performance of AR using different local surrogate models.
German credit
Method
Coxt
Cur Validity
Fut Validit
LIME-AR
0.44 0.08
0.15 - 0.05
0.40 = 0.07
CLIMF-AR
0.73 0.53
0.27 + 0.12
0.45 0.10
L-MELS-AR
0.24 0.36
0.44 =
SVM-AR MPM-AR
0.39
0.21 0.08
0.42 = 0.08
0.09
0.19
0.42 =
QUAD-MPM-AR
1.25 0.09
0.77
0.73 0.03
BW-MPM-AR
1.86
0.09
0.74
MPM-PR
1.92 0.10
0.80 0.05
0.74 0.03
compared to other surrogates. The results for other datasets are presented in Appendix A.2
2 LIMESS S uses the houndary sampling algorithm as the FR-MPM but trains ridge regression instead.
9

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
In order to foster reproducibility, we have released all source code and scripts used to replicate our experimental results at ht pett::pponymousss 4open scwence x mpm recourse The repository includes source code, datasets, configurations, and instructions; thus one could reproduce our results with several commands.
Ustun al., 2019). We use a well-known CARLA's implementation for Wachter (Wachter al., 2017). Since we cannot find the open-source code for CLIME (Agarwal et al. (02T), LIMELS (Laugel et al. 2018), and ROAR (Upadhyay et al., 2021), we implement according to their papers. CLIME and
We use the original authors' implementations of for LIME" (Ribeiro et al., 2016) and AR
LIMELS are adapted from LIME's s source code while ROAR is adapted from CARLA's source code for Wachter.
The hyperparameter configurations for our methods and other baseline are clearly stated in Section Appendix [ and Appendix AA.2 and also stored in the repository. The surrogates sharing the same local sampler will be ensured to have the same random seed, therefore, have the same synthesized samples. The hyperparameters that affect baselines' performance such as and the probabílistic threshold of Wachter and ROAR will also be studied in Appendix A.2
The remaining proofs and theoretical claims are provided in Appendix B
REFERENCES
Sushant Agarwal, Shahin Jabbari, Chirag Agarwal, Sohini Upadhyay, Steven Wu, and Himabindu Lakkaraju. Towards the unification and robustness of perturbation and gradient based explanations. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pp. 110-119. PMLR, 18 24 Jul 2021.
David Alvarez-Melis and Tommi S Jaakkola. On the robustness of interpretability methods. arXiv preprint ar arXi:: 000118000000000 2018
G. Bayraksan and D. K. Love. Data-driven stochastic programming using phi-divergences. INFORMS TutORials in Operations Research, pp. 1-19, 2015.
Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2):341-357, 2013.
C. Berge. Topological Spaces: Including Treatment of Multi- Valti-Valued Functions, Vector Spaces, and Convexity. Courier Corporation, 1963.
Dennis S. Bernstein. Matrix Mathematics: Theory, Facts, and Formulas. Princeton University Press, 2009.
Emily Black, Zifan Wang, Matt Fredrikson, and Anupam Datta. Consistent counterfactuals for deep models. arXiv preprint arXhv:2110.03100 2021.
Blanchet, Kang. and Murthy. Robust Wasserstein profile inference and applications to machine learning. Journal of Applied Probability, 56(3):830-885 857,0-557222 2019.
Sarah Brayne and Angèle Christin. Technologies of crime prediction: The reception of algorithms in policing and criminal courts. Social Problems, 68(3):608-624, 2021.
Lee Cohen, Zachary C Lipton, and Yishay Mansour. Efficient candidate screening under multiple tests and implications for fairness. arXiv preprint 1905v:1905. 1361, 2019.
Paulo Cortez and Alice Silva. Using data mining to predict secondary school student performance. Proceedings of 5th FUture BUsiness TEChnology Conference, 2008
hhtpss//githbbccommmaaooc///// "https///githubbc "hanp://gituub..o//uuuuuuutt http://hwwwcccuuuuuuuucaoooanttr http::/ggthha.cccommaaaaaccccccn
10

---

Under review as a conference paper at ICLR 2023
Finale Doshi- Velez and Been Kim. Towards rigorous science of interpretable machine learning. arXiv preprint 1XX::1700,.8808,, 2017.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archiv/
ics. uci. edu
John Duchi and Hongseok Namkoong. Variance-based regularization with convex objectives. Journal of Machine Learning Research, 20(68):1-55, 2019.
17-750. html
Damien Garreau and Ulrike von Luxburg. Looking deeper into tabular LIME. arXiv preprint arXiv:2008. / 1092, 2020.
M. Gelbrich. On a formula for the L Wasserstein metrie between measures on Euclidean and Hilbert spaces. Mathematische Nachrichten, (47(1):185-2))) 1990.
Amirata Ghorbani, Abubakar Abid, and James Zou. Interpretation of neural networks is fragile. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3681-3688, Jul. 2019. doi: 10. 1at.16099aaaii331/ w33.:a....1111111133303333333000 AAT AAT/article htte:icclllleee/eeee 44252
BtLttts::///jss... org/ index.ndixee/// php/A
C.R. Givens and R.M. Shortt. A class of Wasserstein metrics for probability distributions. The Michigan Mathematical Journal, 31(2):231-240, 1984.
Groemping. South German credit data: Correcting a widely used data set. Reports in Mathmatics, Physics and Chemistry, Depariment II, Beuth University of Applied Sciences Berlin, 2019.
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, Bernhard Schölkopf, and Isabel Valera. survey of algorithmic recourse: Definitions, formulations, solutions, and prospects. arXiv preprint arXiv:20100 200:::20000000500 0404050, 2020a.
Amir-Hossein Karimi, Julius Von Kügelgen, Bernhard Schölkopf, and Isabel Valera. Algorith- mic recourse under imperfect causal knowledge: A probabilistic approach. arXiv preprint arXivv2006.0683/ 2020b.
Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counter- factual explanations to interventions. Proceedings of the 2021 ACM Conference on Fairness, Accountability and Transparency, pp. 353-362, 2021.
Gert Lanckriet, Laurent E Ghaoui, Chiranjib Bhattacharyya, and Michael Jordan. Minimax probability machine. In Advances in Neural Information Processing Systems, pp. 801-807, 2001.
Gert Lanckriet, Laurent Ghaoui, and Michael and Jordan. Robust novelty detection with single- class MPM. In S. Becker, S. Thrun, and K. Obermayer (eds.), Advances in Neural Information Processing Systems, volume 15. MIT Press, 2003.
Thibault Laugel, Xavier Renard, Marie-Jeanne Lesot, Christophe Marsala, and Marcin Detyniecki. Defining locality for surrogates in post-hoc interpretablity. arXiv preprint arXiv: 100.:/0806.7488, 2018
Tam Le, Truyen Nguyen, Makoto Yamada, Jose Blanchet, and Viet Anh Nguyen. Adversarial regression with doubly non-negative weighting matrices. arXiv preprint 1rXiv:2109.1499 2021.
Min Li, Amy Mickel, and Stanley Taylor. "Should this loan be approved or denied?": A large dataset with class assignment guidelines. Journal of Statistics Education, 26(1):55-66, 2018.
Tim Miller. Explanation in artificial intelligence: Insights from the social sciences. Artificial
intelligence, 267:1-38, 2019.
Vincenzo Moscato, Antonio Picariello, and Giancarlo Sperlí. A benchmark of machine learning approaches for credit score prediction. Expert Systems with Applications, 165:1 13886, 2021.
11

---

Under review as a conference paper at ICLR 2023
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.
Hongseok Namkoong and John C Duchi. Variance-based regularization with convex objectives. In Advances in Neural Information Processing Systems 30, pp. 2971-2980, 2017.
Viet Anh Nguyen, Soroosh Shaficezadeh-Abadeh Man-Chung Yue, Daniel Kuhn, and Wolfram Wiesemann. Calculating optimistic likelihoods using (geodesically) convex optimization. In Advances in Neural Information Processing Systems 32, pp. 13942-13953, 2019.
Viet Anh Nguyen, D. Kuhn, and P. Mohajerin Esfahani. Distributionally robust inverse covariance estimation: The Wasserstein shrinkage estimator. Operations Research, 2021. Forthcoming.
I. Olkin and Pukelsheim. The distance between two random vectors with given dispersion matrices. Linear Algebra and its Applications, 48:257-263, 1982.
Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. On counterfactual explanations under predictive multiplicity. In UAI, 2020.
Martin Pawelezyk, Sascha Bielawski, Johannes van den Heuvel, Tobias Richter, and Gjergji Kasneci. CARLA: A Python library to benchmark algorithmic recourse and counterfactual explanation algorithms. arXiv preprint arXiv: 108.0000000000
arXiv:2108.00788: 00783, 2021.
Kaivalya Rawal, Ece Kamar, and Himabindu Lakkaraju. Can I still trust you?: Understanding the impact of distribution shifts on algorithmic recourses. arXiv preprint arXiv:2012.11788, 2020.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should trust you?" Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1135-1144, 2016.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-22) 215, 2019.
Chris Russell. Efficient search for diverse coherent explanations. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 20-28, 2019.
Richard P Savage. The space of positive definite matrices and Gromov's invariant. Transactions of the American Mathematical Sociery, 274(1):239-2)) 263, 1982.
Candice Schumann, Jeffrey Foster, Nicholas Mattei, and John Dickerson. We need fairness and explainability in algorithmic hiring. In International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2020.
S. Chafiezzadeh-Ahadeh P. Mohajerin Esfahani, and D. Kuhn. Regularization via mass transportation. Journal of Machine Learning Research, 20:1-68, 2019a.
Soroosh Shafierzadeh-Abaaeee Daniel Kuhn, and Peyman Mohajerin Esfahani. Regularization via mass transportation. Journal of Machine Learning Research, 20(103):1-68, 2019b.
Dylan Slack, Sophie Hilgard, Sameer Singh, and Himabindu Lakkaraju. How much should trust you? modeling uncertainty black box explanations. arXiv preprint orXiv:2008. 05030, 2020.
Dylan Slack, Anna Hilgard, Sameer Singh, and Himabindu Lakkaraju. Reliable post hoc explanations: Modeling uncertainty in explainability. Advances in Neural Information Processing Systems, 34, 2021.
Ilia Stepin, Jose M Alonso, Alejandro Catala, and Martin Pereira-Fariñh, A survey of contrastive and counterfactual explanation generation methods for explainable artificial intelligence. IEEE Access, 9:11974-12001, 2021.
Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorithmic recourse. In Advances in Neural Information Processing Systems, 2021.
12

---

Under review as a conference paper at ICLR 2023
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Faimess, Accountability, and Transparency, pp. 10-19, 2019.
Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning: A review. arXiv preprint arXiv:2010. 10596, 2020.
Georgios Vlassopoulos, Tim van Erven, Henry Brighton, and Vlado Menkovski. Explaining predic- tions by approximating the local decision boundary. arXiv preprint arXiv:2006.07983, 2020.
Paul Voigt and Axel Von dem Bussche. The EU general data protection regulation (GDPR). A
Practical Guide, 1st Ed., Cham: Springer International Publishing, 10:3152676, 2017.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harvard Journal of Law & Technology, 31: 841. 2017.
Adam White and Artur d' Avila Garcez. Measurable counterfactual local explanations for any classifier. arXiv preprint arXiv: 1908. 030020, 2019.
Xingyu Zhao, Wei Huang, Xiaowei Huang, Valentin Robu, and David Flynn. Baylime: Bayesian local interpretable model- explanations. In Uncertainty in Artificial Intelligence, pp. 887-896. PMLR, 2021.
13

---

Under review as a conference paper at ICLR 2023
A
EXPERIMENTS
A.1 EXPERIMENTAL DETAILS
Classifier. We a three-layer MLP with 20, 50, and 20 nodes and ReLU activation in each consecutive layer. We use the sigmoid function in the last layer to produce probabilities. To train this classifier, use the binary cross-entropy, solved using the Adam optimizer and 1000 epochs.
Datasets. We provide more details about synthetic and real-world datasets. For synthetic data, we generate 2-dimensional data by sampling instances uniformly rectangle (01, [-2, 4] x [-2, 7J. Each sample is labeled using the following function:
{
211++2 + 2n + x 21 +E
f(x)
otherwise,
where is random noise. We generate a present data D1 with and shifted data D2 with e ~ [0, 1). The decision boundary of the MI. classifier for current synthetic data is illustrated in Figure
-2
Figure 6: illustration of MLP's decision boundary for the synthetic data.
The detail of three real-world datasets are listed below:
i German Credit (Dua & Graff 2017). The dataset contains the information (c.g. age, gender, financial status....) of 1000 customers who took loan from a bank. The classification task is determine the risk (good or bad) of an individual. There is another version of this dataset regarding corrections of coding eтror (Groemping) 2019). We use the corrected version of this dataset as shifted data to capture the correction shift. The features we used in this dataset include 'duration', 'amount', peersonal_stauss.se (Section 6.2). we set personal as immutable and 'age' to be non-decrease.
and 'age". When considering actionability constraints
Small Bussiness Administration (SBA) (Li al. 2018). This data includes 2,102 observations with historical data of small business loan approvals from 1987 to 2014. We divide this dataset into datasets (one instances from 1989 2006 and one is instances from 2006 2014) to capture temporal shifts. We use the following features: selected, 'Term', 'NoEmp', 'Createlob', 'RetainedJob'. 'UrbanRural', 'ChgOftPrinGr', 'GrAppv', 'SBA_AppV', "New', 'RealEstate'. 'Portion', "Recession'. When considering actionability constraints, we set 'UrbanRural" as immutable.
ii Student performance (Cortez & Silva 2008). This data includes the performance records of 649 students two schools: Gabriel Pereira (GP) and Mousinho Silveira (MS). The classification task is to determine if their final score is above average or not. We split this dataset into two sets in two schools to capture geospatial shifts. The features we used are: 'age', 'Medu', 'Fedu', 'studytime', 'famsup', 'higher', 'internet', 'romantic', 'freetime', 'goout', 'health', 'absences', 'GI', 'G2'. When considering actionability constraints, we set 'romantic' as immutable and 'age' to be non-decreased.
14

---

Under review as a conference paper at ICLR 2023
For categorical features, use one-hot encoding convert them to binary features, similar to Mothilal et al. (2020). We also normalize continuous features to zero mean and unit variance before training the classifier. The performance of the classifier is reported in Table 3
Table 3: Accuracy and AUC results of the classifiers on the synthetic and three real-world datasets.
Present data D
Shift data D2
Classifier
Dataset
Accuracy
AUC
Accuracy
AUC
Synthetic data
0.99 + 0.00
1.00 0.00
0.94
0.01
0,99 0.01
German credit
0.67 + 0.02
0.60 + 0.03
0.66 0.23
0.60 0.04
MLP
SBA
0.96 + 0.00
0.99 + 0.00
0.98 + 0.01
0.96 +
Student
0.86 + 0.02
0.93 + 0.01
0.91 + 0.04
0.97
A.2 ADDITIONAL EXPERIMENTAL RESULTS
Local fidelity and stability experiments. Here, we provide benchmarks of local fidelity and stability (Section 6. on the synthetic and SBA datasets in Figure 7
We also run with a different setting for the stability and local fidelity metric assess if the results are sensitive to the parameter choices. Specifically, we sample 10 neighbors in the distribution (z, 0.00012) instead of (ax, 0.001I) to measure the stability. Mcanwhile, we fid to 20% and the radius rp to 10% of the maximum distance between instances in the training data. The result is shown in Figure
Synthetic data
SBA
Local Local Fidelity
0.91
0.96
0.92
0.94
0.88
10a
10*
10a
104
Synthetic data
SBA
0.20
0.60
Stablity
0.15
0.40
0.10
0.05
0.20
10a
10
10a
No. samples
No. samples
LIME
QUAD MPM
BW MPM
FR. MPM
Figure 7: Benchmarks of the local fidelity and stability on synthetic and SBA dataset.
Table 4: Performance of competing algorithms on synthetic, SBA, and Student datasets.
Method
Synthetic
performance
Cost
Cur Valldrr
Far Validit
Cast
Cur Volidity
Fut Validby
Cou
Cur Validity
Fut Vadisity
Wachter
1,01 1: 0.03
1,00 1: 0.00
0.63 2: 0.04
1.74 1: 0.26
0.98
1: 0.01
0.13 1 0.06
3.33 =
0.95 1. 0.03
0.29 1: 0.02
LIME- PROE
2,13 0.08
0.77
0.01
0.76 0.01
0.81 0.06
0.97
1 0.01
0.79 1 0.03
1.07 0.13
0.78 1. 0.04
0.37 1. 0.07
1.816:0.16
CLIME-ROR
1,80+
0.50
0.95
0.04
LIMELS R-RAR
1.30 0.00
1.00 0.00
0.98 0.01
1.63
0.23
1.00
0.00
0.88 + 0.05
2.47 147-0.29
0.95 + 0.08
0.75 + 0.09
QUAD PROT
1.09 0.02
0.99 à: 0.01
0.98 2: 000
L.7 0.11
1.00
0.00
0.85 + 0.05
1.46 0.13
0.95
4 0.03
0.54 4: 0.07
BW MPM-PP-PPP PROJ
1.19.1.
1,00
0.00
0.99 0.00
1.67
1 0.13
1.00
0.00
0.95 0.02
2.18
0.95
0.03
0.76 0.06
FR-MPM-PROY
The cost-validity trade-off. Here, we provide more detail about the settings of the baselines and the complementary results of the experiments in Section 6.2 in the main paper.
15

---

Under review as a conference paper at ICLR 2023
Synthetic data
German
SBA
Student
Local Local Foality
0.92
0.96
0.74
0.90
0.90
0.94
0.72
0.88
0.80
10
10
10a
10
10a
10
107
10
Synthetic data
German
SBA
Student
0.75
0.15
0.40
Sobliit
0.50
0.05
0.20
0.25
0.20
10a
10
10²
10*
10²
10
10a
10
No. samples
No. samples
No. samples
No. samples
LIME
QUAD MPM
BW-MPM
FR-PPM
Figure 8: Benchmarks of the local fidelity and stability.
Synthetic data
German
SBA
Student
1.00
1.00
1.00
1.00
Oureent Validity
0.00
0.80
0.80
0.80
0.60
0.60
0.40
0.40
0.40
0.20
1.0
1.
2.0
2.5
0.25
0.50
0.75
1.00 1.25
0.5
1.0
1.5
2.0
2
Synthetic data
German
SBA
Student
1.00
0.80
Future Valldity
0.70
0.80
0.60
0.60
0.60
0.60
0.50
0.40
0.40
1.0
1.5
2.0
2.5
0.25
0.50
0.75
1.00
1.25
0.5
1.0
1.5
2.0
2
Cost
Cost
Cost
Cost
Wachter
-
LIM-RDDK
CLIME-ROAR
+ LIMELS ROAR
- FR-MPM-PROO
Figure Pareto frontier of the cost-validity trade-off with the MLP classifier on the real-world datasets. For FR-MPM-PROJ, we vary the ambiguity size in range of p_ [0, 10). For the ROAR-related methods, we vary the uncertainty size in a range 8max E 0.2]. And for Wachter, we vary the hyperparameter À E [0.05, 0.4].
For Wachter's implementation, we use CARLA's source codo Pawelezyk et al. 2021 which employs an adaptive scheme to adjust the hyperparameter (A) if no valid recourse is found. We adopt this implementation for ROAR and set the initial À to 0.1 as suggested in (Upadhyay et al. 2021).
Regarding the surrogate models, we use the open-source code with the default settings for LIMH (Ribeiro et al. 2016). We adapt this source code accordingly for CLIME's implemen- tation (Agarwal et al. 2021). LIMELS, SVM, and MPM-related surrogates use the same boundary and
sampling procedure (with the same seed), which we set the number counterfactuals the number of perturbation samples is 1000.
Figure shows the Pareto frontiers of the cost-validity trade-off on the synthetic and three real-world datasets. Table 4 shows the performance of FR-MPM-PROJ at radii P+1 0. p-1 10 and of ROAR-related methods at uncertainty size 5max = 0.2 on synthetic, SBA, and Student datasets. The hyperparameter is set to 0.1 for both Wachter and ROAR-related methods.
In FR-MPM-PROJ and ROAR-related methods, the trade-off between cost and validity can be observed when increasing the ambiguity size (p_1 for FR-MPM and 5max for ROAR-related methods),
https://gthhb.co//caaarrccoosse https://ggthuh.co/mmarreee/////e
16

---

Under review as a conference paper at ICLR 2023
Synthetic data
German
SBA
Student
1:00
1:00
Curtent Valdity
0.80
0.80
0.00
0.60
0.40
0.40
0.40
0.20
1.0
1.5
2.0
2.5
0.25
0.50
0.75
1.00 1.25
0.5
1.0
1.5
2.0
2
Synthetic data
German
SBA
Student
1.00
1.00
Fature valdity
0.80
0.80
0.80
0.80
0.60
0.60
0.60
0.50
0.60
0.20
1.0
1.5
2.0
2.5
0.25
0.50
0.75
1:00
1.25
0.5
1.0
1.5
2.0
1
2
Cost
Wachter
LIME-ROAR
MPM-RDAR
SVM-ROAR
FR-MPM-PRO)
Figure 10: Pareto frontiers of our method compared with ROAR using vanilla MPM and SVM as the surrogate model. The recourses are generated with respect the MLP classifier synthetic and three real-world datasets.
Table 5: Performance of AR using different local surrogate models.
Method
Syntheric data
SRA
Student performance
Cost
Cur Validay
Fac Validity
Cost
Cur Validrry
Fur Validayy
Cost
Cur Validity
Volldiry
LIME-AR
2.06 1: 0.07
0.67
1: 0.02
0.67 +: 0.01
4,50 = 3.48
0.10 i: 0.07
0.04 2003
3.38
0.24
0.45 = 0.07
0.42 :: 0.06
CLIME-AR
1,31 1. 0.05
0.41
1 0.02
0.13 1: 0.01
4.10
3,80
0.07 0.07
0.01 0.001
1,24
0.63 0.28
0.50 1: 0.15
LIMELS-AR
0.03
SVM-AR
1,02 0.06
0.64
0.04
061 0
606
4.06
0.02
8:23
0.36 0.03
MPM-AR
1.08 +0004
0.68 + 0.04
0.62 0.03+003
5.6
3.33
0.39 + 0.18
008 0.05
3,02 + 0.19
0.40-0.15
0.36 0.00
QUAD MPM-AR
1,6 + 0.08
0.99
+ 0.01
0.98 0.01 0.0
7.40
1:00=..0 3.36
0.97 0.03
0.49 0.19
5.00
+
0.97 = 0.04
0.69 + 0.05
BW-MPM-AR
1,86
1,00
0.00
0.99 0.01
9.66
3.21
0.98
8.62
1.00
0.00
0.92 0.05
FR-MPM-R
2.03
similar to the analysis (Rawal et al. 2020) and the experimental results (Upadhyay et al. 2021 I
Black et al. (021). Generally, the Pareto frontiers of FR-MPM-PROI dominate the frontiers of ROAR-related methods on all evaluated datasets. other words, with the same cost (or validity), method will provide recourses with a higher validity (or lower cost) compared to ROAR. Table demonstrates that our method has similar validity but much smaller cost than ROAR on Synthetic and German datasets. Meanwhile, our method achieves higher validity with reasonable cost on SBA and Student datasets.
Comparing other baselines, LIMELS-ROAS performs slightly better compared LIME-ROAR and CLIME-ROAR, Wachter provides the recourses with high current validity but is vulnerable to model shifts, resulting in poor future validity. Wachter has the lowest datasets but higher cost for the SBA and Student datasets compared to the linear surrogate- based methods. This consistent with the results (Upadhyay et al.) 202T) since the objective function of Wachter might be non-convex when the classifier an MLP network.
for the synthetic and German
Comparison with ROAR using the vanilla MPM and SVM as the surrogate model. Here, we compare the FR-MPM-PPR Both vanilla MPM and SVM use the same boundary sample procedure (with the same seed number) as FR-MPM. The settings are similar to the experiment in Section 6.2 The result shown in Figure I0 demonstrates the merits of our method.
with ROAR using the vanilla MPM and SVM as the surrogate model.
Actionability. We provide the complementary result of the actionability experiment the synthetic, SBA, and Student datasets Table 5 Using AR with FR-MPM produces the recourses with higher value in both the current and future validity compared to AR using other surrogates.
Ablation study, We conduct an ablation study to understand the contribution of each stage in our method. Figure shows the comparison of our method with ROAR using vanilla MPM and SVM as the local surrogate. Figure ITo the Pareto frontiers of FR-MPM-PRO. compared to its ablations by alternating the FR-MPM with other surrogates (LIME, MPM) or alternating the projection with
17

---

Under review as a conference paper at ICLR 2023
Synthetic data
German
SBA
Student
1.00
1.00
Current Valrdiy
0.90
0.80
0.80
0.80
0.70
0.40
0.60
0.60
0.60
0.20
0.40
0.5
1.0
0.5
1.0
1.5
2.0
Synthetic
Student
1.00
0.80
Future Validity
0.70
0.80
0.80
0.60
0.60
0.70
0.50
0.60
0.40
0.5
0.5
1.0
2.0
Cost
Wachter
ROBUST-PROI
FRIMPMM-AACHTE
PRIMPM-PRC
Figure 11: Ablation study: Pareto frontiers of MR-MPM-PROJ compared its ablations by alternating the FR-MPM by common local surrogates. The recourses are generated with respect to the MLP classifier synthetic and three real-world datasets.
Synthetic data
German
SBA
Student
Current Vilddly
0.90
0.80
0.70
0.40
0.60
0.60
0.40
0.20
0.5
1.0
1.5
1.0
2.0
Synthetic data
German
SBA
Student
Future Valddty
0.90
0.80
0.80
0.80
0.70
0.70
0.40
0.50
1.0
1.5
1.0
1.5
Cost
WHLD
FR-MPM-PROO
Figure 12: Comparison with the probabilistic shiftings.
Wachter. Particularly, we compare our method with LIME-ROBUST-PROJ, which uses LIME as the surrogate model and then solves the robustified projection:
Fr arg min ( [| zolli x: w + 8max | 2 0),
where (w, b) is the weight and bias of LIME'S surrogate, 8max is similar to the uncertainty size of ROAR (Upadhyay et al. 2021). The recourses are generated with respect to the MLP classifier on synthetic and three real- weal-world datasets. This result demonstrates the usefulness the FR-MPM in promoting the generation of robust recourses. Note that, for p_ 0 and p+ 0, the hyperplane of the FR-MPM classifier recovers the vanilla MPM's hyperplane.
Comparison with the probabilistic shiftings. One might attempt to increase the probabilistic threshold (usually set 0.5) which sample is considered 'favorable" to generate robust recourses. In Figure I2 compare the proposed method with Wachter, LIME, and MPM with various probabilistic thresholds in the range [0.5, 0.9]. It can seen that FR-MPM-PROJ consistently achieves the best performance compared other baselines. Interestingly, Wachter improves its future validity significantly on the synthetic and German datasets as the threshold increases. However, our method still dominates Wachter in all datasets.
Robust recourses with MPM's variants. We compare FR-MPM-PROJ with QUAD-MPM and BW-MPM-PROJ, The settings similar in the cost-validity trade-off experiments in Section 6.2
18

---

Under review as a conference paper at ICLR 2023
Synthetic data
German
SBA
Student
1:00
1:00
Current Valldtty
0.90
0.80
0.80
0.80
0.60
0.60
0.70
0.40
0.40
1.0
1.5
2.0
2.5
0.25
0.50
0.75
1.00
1.25
0.5
1.0
1.5
Synthetic data
German
SBA
Student
1.00
0.80
1.00
Fature valdity
0.80
0.70
0.60
0.60
0.70
0.50
0.20
1.0
1.3
2.0
2.5
0.25
0.50
0.75
1.00
1.25
0.5
1.0
1.5
Wachter
LIME-ROR
QUAD-MPM-PRO)
BW (WV-MPH-PRO)
FR- MPM-PD))
Figure 13: The comparison among MPM-related methods with different distances.
The number of samples is 1000. The results are shown in Figure 13 Generally, all three MPM-related methods perform better than LIME-ROAK and Wachter. However, FR-MPM-PRON better than DUAD-MPM-PRO. and BW-MPM-PRON especially in synthetic and Student datasets.
68
5.0
UM
MPM
UPM
35
SPM
35
15
SPI
25
15
05
30
15
29
23
58
35
15
30
15
23
28
30
35 60 03
13
15
20
25
50
33
(a) p+1 = 0-1
(b) p+1 = 0,p-1=1
(c) p+1
0, p-1 10.
Figure 14: Visualization of MPM's hyperplanes with Quadratic, Bures, and Fisher-Rao distances.
When P+1 = p-1 = 0, all hyperplanes coincide and recover the vanilla MPM. All hyperplanes move towards the favorable class the radius for the unfavorable class p-1 increases. p-1 10 in Subfigure (c), the hyperplanes of Quadratic and Bures MPMs come close together which is distinct from the Fisher-Rao MPM's hyperplane. Notice that the Fisher-Rao MPM in Subfigure (c) tends to position in parallel to the major axis of the infavorable covariance matrix. which shows the dependence on Em1, Proposition 5,4 The Bures and Quad MPM hyperplanes in Subfigure (c) do not show any dependence on the covariance matrix, which aligns with the results in Proposition 4.4
A.3 COVARIANCE-ROBUS. MPMS WITH DIFFERENT DIVERGENCES
In this section, we discuss the variants of svariiance-rbuus MPMs with different distances and provide guidance for choosing the surrogate model in practice, especially at low sample size.
Proposition 4.4 and Remark 4.5 showed that Quadratic MPM and Bures MPM coincide when one of the radii Py grows to infinity and they independent of the covariance matrices Σ.y. Meanwhile, the asymptotic hyperplane of the Fisher-Rao MPM when Py >> oc aligns with axes of the covariance matrices Σ,, (see Proposition 5.4 and Figure 14p. It suggests that the Fisher-Rao MPM is not suitable surrogate at low sample sizes as it relies on the estimate the covariance matrices. On the other hand, when the number of samples is sufficient estimate the covariance matrices accurately, Fisher-Re Rash MPM would be better than Quadratic MPM and Bures MPM as it takes the geometry of the data into account when robustifying the surrogate.
We probe the performance MPMs with different distances at low sample sizes to demonstrate our claim above.
19

---

Under review as a conference paper at ICLR 2023
Synthetic data
German
SBA
Student
2.6 10"
Negative
10
Neçative
10
Negative dass
1014
Nigative
Condition number
3.5 10"
Positive class
10
Pestive cass
10
Posiive dass
2011
Positive dlass
3.4 10"
10²
10²
10P
10'
10
10P
10P
100
20a
10a
20
10a
107
10a
107
samples
samples
No. samples
samples
(a) The average condition number of the generated covariance matrices for positive and negative classes.
Synthetic data
German
SBA
Student
0.98
Local Local Fdelity
0.80
0.95
0.75
0.90
0.95
0.93
0.70
0.93
0.90
0.00
202
10
10'
10'
10'
10"
10'
10*
No. samples
No. samples
No. samples
No. samples
QUAD-MPM
BW-MPM
(b) Local fidelity of MPM variants at low sample sizes.
Figure 15: The comparison among MPM-related methods with different distances at low sample sizes.
Local fidelity. We probe the local fidelity at low sample sizes and plot the result in Figure 15 The experiment settings are similar to those in Section 6.1 The number of samples is set in the range of [50, 1000]. We also measure the average condition number of estimated covariance matrices for both positive and negative classes in Figure 15a It can be seen that the covariance matrices are ill-conditioned at 50 samples on SBA and Student datasets. The fidelity of FR-MPM just slightly better than QUAD-MPM and BW-MPM. When the number of samples increased, FR-MPM benefited the most, and the gap between FR-MPM and QUAD-MPM (or BW-MPM) became more significant. It supports our claim that FR-MPM would better approximate the decision boundary when the number of samples is sufficient for estimating the covariance matrices.
Synthetic
Synthetic data
1.00
1.50
Ciivere Walsty
Curore Vandtty
0.35
0.98
0.98
0.95
0.50
0.40
0.93
0.96
0.20
0.54
0.8
1.0
1.2
0.2
0.4
0.6
0.8
0.0
0.9
1.0
1.1
0.5
0.7
0.8
Synthetic data
SBA
Synthetic data
1.00
Future Weidlt
0.60
Fature Valieiy
0.90
0.60
0.80
0.50
0.70
0.20
0.80
0.8
1.0 Cost
1.2
0.2
0.4
0.5
0.5
0.81
1.0
1.0
1.5
Cook
Cost
Cos:
QUMD-MPM-PP0
FR-MPM-PRR
OUKG-MP1A-PRO
FR-NPM4-ROO
(a) 50 synthesized samples.
(b) 1000 synthesized samples.
Figure 16: The comparison of QUAD-MPM-PROI and FR-MPM-PROJ at low sample sizes.
Robust recourses. We revisit the recourse generation with covariance-robust MPMs using quadratic distance (QUAD-MPX) 110-MMMM-PR) and Fisher-Rao distance PRR-MPM-PROL) at which the surrogate is estimated with 50 and 1000 synthesized samples. We omit the comparison with Bures distance to ease the presentation as it behaves asymptotically like the MPM using the quadratic distance. The results shown in Figure 16 The results showed that QUAD-MPM-PROO, would be better low
20

---

Under review as a conference paper at ICLR 2023
sample size. When increasing the number of samples, the recourses constructed with Fisher-Rao MPM exhibit a better cost-validity trade-off. This result is consistent with our previous observation in the local fidelity experiment.
B PROOFS
B.1 PROOFS OF SECTION
3
Proof of Proposition 3.4
The covariance-robus. MPM problem
min lE0
max vEY
max
Py(Co(X) *
F, (Ug
is equivalent to
min 1 a s.t.
E R4, W RRR {0], bER
(9)
1- max max. HEY (F,
Pulu(wT X b) s 5),
where we used the classification rule that Cx(x) sign(w" x - 6) if and only if y( X - 6) 2 and that the feasible set takes the form Q & {0 (w, E Rd+1 w * 0}. We claim that is never optimal. To see this, take w = O. Then,
Py((ww X b) s 0) (yb 2) 0),
which is independent of the random variable X and is either 0 or 1 no matter what we choose. Therefore,
max max Po(u(WTx x - b) - 0) 11 NEY (F,
and hence a O, which is never optimal. So, the domain of w can be relaxed from Rd \ (0) to Rd. Problem ( can then be further re-written
max a
L. a E W E Rd bER
(10)
P 5) 1-a2 (,
Vy E V
Notice that here, equivalency means the optimal solution (w*, b*) of 10p will constitute the optimal solution 8* = (w",b") of the original min-max-max problem. Moreover, recall the definition of the ambiguity set
Uy (f,)) (Py P,~ (Ry. Ey), (LE, 1 py}.
where Py ~ (my. Eny) means that the the distribution Py has mean J, and covariance Ey. In other ) is determined by first choosing covariance matrix My satisfying the divergence constraint s0(i, || Σny S Py and then picking a distribution I,, having mean My and covariance Eyg Therefore, the worst-case probability admits two-layer decomposition
words, each element P., in the ambiguity Uy (1py)
max Py(w(") X b) S 0) (P
max E, Edd ( SS SSP
max (ay
Py(((W X b) s 0). (11)
F
Using Lanckriet et al. 2001 Equation (6)), the inner maximum value is given by
Polu(w X - 6) < <0
max E.)
R.
Combining the last two equalities, we can express the constraint in problem
10 as
max 1 a P x b) 5) Eyest (S,,
(b- w 2.)
which upon rearranging, becomes
w T Eyw S (b w TTyy)
max F, EBd ( 1 1
21

---

Under review as a conference paper at ICLR 2023
Using the same argument in Lanckriet et al. (2001) (see equation (4) and the discussions following it in Lanckriet et al. (2001)) ) we could show that the optimal = (w, b) must classify By correctly, i.e,
y sign(w w By 6),
which yields that
VuT My S s(w uy Byy b).
max
C Eye84 (p 1 SSy
As consequence, problem T0 is equivalent to
max a a Rdd be R y(w Fy - b) Z I-a
s.t.
max s, (P
Vwi Eye
Vy E E.
Using that rff(() (w) the above problem is further equivalent to
max
Vw w Eg and that a + V 1-a monotone increasing,
ERd s E ssp
max
K
S. t.
K E R4, w Rd b bEL I y(w Bly - b) TTf(ww
(12)
Vy V.
From the constraints, we get
w T41 1 (w) b وー (
(13)
So, can eliminate the variable and reduce problem 12 to
max
E R. W E Rd w M41 K (w) 2 w To + K xT (w).
(14)
The inequality constraint in problem
14 is equivalent to
Evey yww Fly
K 5
(15)
E Evey T (w)
Thus, we can eliminate the variable x and rewrite problem
EYEN (W)
min
Egey y ply
Using the definition of (w), we can see that the above problem is homogeneous w, which implies that could further re-write as
min
of (w)
y w By
1.
vEy
Finally, note that from
13 and 15 at optimality, we have
K Evey y w Fy
Egey Ty (w)
(w()
Σ EyEN Ty (w))
and
b = w P41 (w] w Po1 + (w))
This completes the proof.
22

---

Under review as a conference paper at ICLR 2023
Proof of Proposition 3.5 First, following exactly the same arguments as in the proof of Proposi- is equivalent to
tion 3.4
we see that problem
max
s.t.
a a w WER" bER
(16)
1 max (.
Polv(w X - b) S 0)
Vy e.
In the proof of Proposition 3.4 we handle the maximum in the constraint by decomposing it into two layers of maximization problems (see However, because of the Gaussian assumption, this case, we have
max Py(u(w' X P. PAE (B,)
0)
max By Ey (2 11,, (yy) "P,,,
Py(y(w - s 5).
For each fixed Ey, using elementary probability theory, we could calculate the Gaussian probability explicitly:
y(w My 6) Ve w Ey
(y(w(w X X b) 0) -
where & is the cumulative distribution function of the standard Gaussian random variable. Therefore, problem (16) can be re-written as
max a t. a E.R. W E Rd b R
(17)
a
max
+b
ylw ر.- V En
Vy E V
Using the monotonicity of 4, the constraints in problem become
Vui V En
v(w Fhy - b) 2 + (a)
min
Vy y.
E, E EeeR up (
Using that (w)
max Bg EB xp, (
w Mn w and that +b (a) is monotone increasing, prob-
lem 17 is further equivalent to
max
K
8. t.
K E R4, w wEE bER y(w Bg 2) (T)(
Vy E V.
which is same problem as problem the same optimal solution as problem
12 the proof of Proposition
3.4 Hence, problem 6
shares
This completes the proof.
B.2 PROOFS OF SECTION
4
We first prove Proposition
to lay the foundation for the proof of Theorem 4.2
Proof of Proposition By Nguyen et al.
22021
Proposition 2.8), we have
(w)2
inf 7/ w
T(p Tr [2,) + ( E,))
Using the Sherman-Morrison
Morrison formula [Bensttin 2009 Corollary 2.8.8), we find
wow
ww) -1 = I+
7 ||
Notice that the constraint 7I > ww is equivalent to 7 have
|| by Schur complement. Thus,
w E
B
(w))
inf
YPv +
y
18
w 1
23

---

Under review as a conference paper at ICLR 2023
The optimal y can be found by using calculus, which is given by
w T E, w || 12
> = 2012 +
Py
with the corresponding optimal value
y [ww)² (p + VV T ET
We thus have the necessary result.
We now prove Theorem 4.2
Proof of Theorem
4.2
Using the Bures divergence IB, the optimization problem
Eyey T (T)(w)
min
becomes problem 7
by exploiting the analytical form of ( (w) in Proposition 4.3
By invoking
Proposition 3.4 obtain the postulated results the optimal solution B for the case of the Bures
divergence.
Proof of Proposition 4.4 Note that problem 7 has a unique solution because the objective function strictly convex and coercive. Moreover, the optimal solution of coincides with the optimal solution w (A) of the following second-order cone program
min NEW
Σ NEY
w ETT + ||w||2,
where A = L.p. By a compactificattin of W and applying Berge's maximum theorem (Berge 1963 pp. 115-116). the function w² (A) is continuous on non-negative compact range of X, and converges w² (0) as À O. The optimal solution w" (0) coincides with the solution of
min ||w|| NEW
(18)
which is the Euclidean projection the origin onto the hyperplane W. An elementary computation confirms that
ΣBEy yfy w w0
1E y7
Letting B.B. (0) completes the proof.
B.3 PROOFS OF SECTION 5
We first provide the proof of Proposition 5.3
Proof of Proposition
3.3
Notice that
max w I Ey
[2)= =
s.t. |gog(Ey E f )]lF S Pg.
Using the transformation Zy Enj Ey En
have
Ty (w)² max Zyv log Z S pv}
with v 3h w. We now proceed to show that the above optimization problem admits the maximizer
zí = -U- UUT + exp(p,)
v0
24

---

Under review as a conference paper at ICLR 2023
where U is an d (d 1) orthonormal matrix whose columns are orthogonal First, by Nguyen et al. (2019) Lemma C.1), the feasible region is compact. Since the objective function v Zy u is continuous in Zy optimal solution Z exists. Next, we first claim that the constraint holds with equality optimality. Suppose that log Zille Py- Then, for some small ő the matrix Z + d uv" is feasible due the continuity the constraint function log Zy F and has a strictly better objective value than the optimal solution z This violates the optimality of 7/. Hence, log Zyllr- Py for any optimal solution Zy. and the problem is equivalent to
max V DDagg (A)QU L.
Σ (log )₂ = by. 1 2 da 0, Q Odd),
where ((d) is the set of d x d orthogonal matrices. For any orthogonal matrix Q, the objective function
QDia@ (A)Q" s Arllolla.
the right-hand side of which can be attained by setting
(1 V) O(d).
Q ||1|/2
Therefore, our problem is further reduced to
A /o12
(lgg pg. 2 2 0.
S.
is then easy see that at optimality, the optimal IRq must satisfy A2 Xa- 1 and (log )1)² Pg. Since d 2 X2 1, have log Å Py and hence λ1 exp(py)) In other words,
exp(px)
T
Z
U)
|0l|2" U)
||u||2"
vu
-U + exp(pv)
|Tul13
The corresponding optimal value is
T
(w)2 = u 2y = exp(py) ||1|2 exp(py) w -.y.
This completes the proof.
We are now ready to prove Theorem 5.2
Proof of Theorem
5.2 Using the Fisher-Rao divergence IF, the optimization problem
Eney T (w)
min
w WEW
becomes problem g by exploiting the analytical form of + (w) in Proposition 5.3 By invoking
Proposition 3.4 we obtain the postulated results on the optimal solution 8 for the case of the Fisher-Rao divergence.
Proof of Proposition 5.4 Note that problem 8 has a unique solution because the objective function
is strictly convex and coercive. Also, the optimal solution of (8) coincides with the solution w (()) of
min WEW
w T Eyw + A TS S_
25

---

Under review as a conference paper at ICLR 2023
where exp P=y-P2 ) By compactification of W and applying Berge's maximum theo- rem (Berge 1963 pp. 115-116), the function w' (A) is continuous non-negative compact range of X, and converges to (0) as À 0. The optimal solution w² (0) coincides with the solution of
min V www Syw. WEW
Because the square-root function is monotonically increasing, w* also solves
min
WEW
which is convex, quadratic program with single linear constraint. If is defined as in the statement, then convex optimization argument implies
w
(0)
Ey'a a,
1 a
which completes the proof.
C LOGDET MPM
In this appendix, we consider when to is the Log- Sog-Determinant (LogDet) divergence. The LogDet divergence is formally defined follows.
Definition C.1 (LogDet divergence). Given two positive definite matrices E, E E $4 the log- determinant divergence between them is
D | 5. = Tr [ - det det (X -
can be shown that is divergence because it non-negative, and vanishes to zero if and only = Σ. However, not symmetric, and in general we have D( Σ) = D( || 2)) The LogDet divergence DD is related to the relative entropy: it is equal to the Kullback-Leible divergence between two Gaussian distributions with the same mean vector and covariance matrices Σ and Σ.
We now provide the form of the LogDet MPM problem.
Theorem C.2 (LogDet MPM). Suppose that y D. Let wD be the optimal solution of the following second-order cone problem
min WEW
ΣV V w Eyw,
(19)
VEY
where c, --W-(--xxpp I and 6D be calculated
Pg 1)) and W_1 the Lambert W function for the branch -1. Let
1
Evey Vor T
1P = (1oP T44 RD Ve+i V S
then 0D (wD. the optimal solution of the distributionally robust MPM problem 3
Theorem shows that the LogDet divergence induces similar reweighting scheme as the Fisher- Rao MPM. The asymptotic analysis of the LogDet MPM follows similarly from the Fisher-Rao MPM and is omitted. The proof of Theorem C.2 follows trivially from the below result, which provides the analytical form of r (w.)
Proposition C.3 (LogDet divergence). Suppose that & = ID, then for any y E Y, we have
(0y-WW---xp(-21 1)) no T.
where W is the Lambert- W function for the branch -1.
26

---

Under review as a conference paper at ICLR 2023
Proof of Proposition C.3
By
Le al. 2022 Proposition 3.4), we have
(w)²
inf 7>0
Ppy 7 log det Σ www T Eg /n).
2 >ww"
Using the matrix determinant formula (Bernstein 2009 we have
del(1 1 E.j ww E. //) (1 w Enww/7).
Notice that the constraint
ybyy > ww T is translated into > w T Eyw. Thus, we have
D y (ww) inf TPy 7 log(1 w Eypo/))) <> E,
The first-order optimality condition for 7 is
w Ey
w T E,
p log (1
= 0, w Eyw
7
and the optimal solution for y is
Σ
W
y
w
1 1 cxp( Py 1))
Replacing the value of y" into the objective function leads to the necessary result.
27


Reviews:
[{"review_id": "6fM5n8YajrN", "reviewer": "Reviewer_33C8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper targets the problem of algorithmic recourse, which is to suggest how an input instance should be modified to alter the outcome of a predictive model. In particular, the paper proposes a pipeline to generate a model-agnostic recourse that is robust to model shifts. The main idea is to estimate a linear surrogate of the black-box model using covariance-robust minimax probability machines (MPM), then generate the recourse using this surrogate. The paper derives several theoretical analyses to show that the covariance-robust MPM correspond to the l2-regularization and class-reweighting schemes. Finally, experiments are conducted on various real-world datasets to confirm the effectiveness of the proposed approach.", "summary_of_the_review": "Overal, I think the paper targets an important problem. The key idea seems to be sound and novel to me. The experiments are also detailed and thorough. The paper's writing is very clear, and easy to understand.", "strength_and_weaknesses": "Strengths:\n+ The paper targets an important and interesting problem. The related work and existing literature are described in detailed and thorough.\n+ The paper's writing is very clear and easy to understand. Even though the paper has many complicated theoretical analyses, but thanks to the clear writing, these analyses could be followed easily.\n+ A lot of theoretical analyses are derived to understand the property of the MPM-based proposed approach. They seem to be sound to me, although note that I can't dig into detail of the proof, so I can't guarantee if these theoretical analyses are completely correct or not.\n+ The discussion around the experimental evaluation is thorough and detailed. The paper also compared their proposed approach with various existing and new baselines. Different metrics are used to evaluate different aspects of the proposed approach.\n+ The code is published in order to aid reproducibility. \n\nWeaknesses:\n+ The datasets used in the experimental evaluation seem to be simple and easy datasets. Although I completely understand that the research field of algorithmic recourse is new, and thus the evaluation can be done on some simple datasets.\n\nQuestions:\n+ Based on the experimental evaluation, it seems to me that the approach of using a robust surrogate then derive a recourse from this robust surrogate is much better compared to the approach of using a non-robust surrogate and then derive a robust recourse. Is there any explanation for this particular property? Does this mean the choice of surrogate model affects robustness property the most?\n+ There are several settings in the experiments that I feel unclear on why they are set that way. For example, in Section 6.1 - Stability, 10 neighbours data points are sampled in the distribution N(x, 0.001I). In Section 6.1 – Fidelity, r_fid is set to 10% of the maximum distance between instances in the training data. Or the radius r_p is set to 5% of the maximum distance between instances in the training data. Why are these values (10, 0.001, 10%, 5%) chosen? Will these values be sensitive to the performance of the proposed approach?\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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6YDtsLnVoL", "reviewer": "Reviewer_NHFj", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper introduces two variants of covariance-robust minimax probability machines (MPM) which the authors term as Bures MPM and Cramer-Rao MPM based on different statistical divergences between Gaussian distributions. The authors discuss how to estimate the parameter for these new variants of MPM and discuss the potential applications for algorithmic recourse.", "summary_of_the_review": "The authors do not provide strong motivation for proposing the two new MPM variants. The theoretical results are not technically hard and the empirical results are not strong.", "strength_and_weaknesses": "### Strength:\n* The MPM part is easy to follow.\n\n### Weaknesses:\n* From my point of view, I don’t think the derivation of the covariance-robust MPMs with these two statistical divergences is hard. And I think an extension to general f-divergence is also possible.\n* The authors spend most of the space on presenting the variants of covariance-robust MPMs, without discussing the necessity of studying these variants for algorithmic recourse.\n* The empirical results do not have significant improvement over the quadratic MPM.\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "5pwNyROcgNI", "reviewer": "Reviewer_CMDf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors consider the application of a distributionally robust minimax probability machine, relying on statistical distances defined on the space of Gaussian measures. The authors motivate this as a tool for finding algorithmic recourses that are robust to changes in parameters of a classifier, that might be induced by underlying changes in the distribution of covariates. Several experiments are considered to compare the method in terms of a cost-validity trade-off and actionability of the recourses.", "summary_of_the_review": "I am in favor of accepting the paper on balance. I think the presentation was reasonably good, the method seems practical and experiments seem thorough. However, I am not an expert in this area and have not read large portions of the related literature. I therefore have a low degree of confidence in my review and it is very possible I will change my score in light of future feedback and discussion with the other reviewers and authors.", "strength_and_weaknesses": "## Strengths\n- The experiments appear to be quite thorough, especially considering the detail provided in the supplement.\n- The method seems to be a reasonable minor adaptation of existing methods in MPM, and yet some benefit is still achieved in experiments. This suggests it might be quite practical.\n- The presentation is generally good.\n\n## Weaknesses\n\n- The authors claim that a major contribution of the work is an \"intuitive and interpretable approach to generate robust recourse\". However, not much of the paper is dedicated to the interpretation of what it means for robustness to be defined with respect to a MPM that is distributionally robust with respect to a particular distance between Gaussians. For example, how different are the Bures and Quadratic distances in practice; would figure 2 change much had you used quadratic distance? Intuitively when would I want to use a Bures MPM versus a Fisher-Rao MPM? In the fidelity/stability experiments, it seems the Fisher-Rao MPM often is more stable/higher fidelity. Can you convey intuition as to why this is the case? I think the geometric intuition in figure 2 and remark 4.6 is helpful, but you should go further in relating the distances chosen to robustness of the resulting recourse if a major claim of the paper is that the method is both intuitive and interpretable.\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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2PRxmVun2mF", "reviewer": "Reviewer_14wF", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper studies the problem of providing algorithmic recourses -- that is, providing users who were rejected by a model (e.g. denied a loan) a way to change themselves so that they will not be rejected in the future. The paper is specifically concerned with the setting where the model may change over time (e.g. by getting updated training data); in this setting, we would want old recourses to be valid for the new model. The authors propose to locally fit a linear surrogate model around the given model's decision boundaries. They specifically use \"minimax probability machines\" (MPMs) to make these linear surrogate models more robust to changing models. The authors propose a few modifications to existing MPMs; in particular, they propose different objective functions in fitting the MPMs and study the asymptotic behaviors of the resulting surrogate models. With a linear surrogate in hand, existing algorithmic recourse methods are applied to the surrogate model.", "summary_of_the_review": "I mainly think the paper needs to contain proofs for all of its claimed results and explain what the takeaways are from all of its claimed results. I think both of these things need to be included in a paper, so I've voted for reject.", "strength_and_weaknesses": "The provided experiments are interesting, and provide good evidence that their proposed method can outperform existing methods. I overall feel that the proposed method needs some more investigation and explanation before publication. I've tried to break issues down into categories below:\n\n\n**Theoretical development.** A number of theorems and propositions are stated about fitting various MPMs and the properties of MPMs. I found three proofs that were explicitly omitted and a couple more that I had a hard time following. First, I do not think it is OK to publish a paper with omitted proofs. Omitting proofs makes the paper extremely difficult to validate, reproduce, and build on in future work; I definitely cannot tell if the stated results are correct or not. I read through the proof of Proposition 3.4, and got stuck in a few places:\n1. \"note that the worst-case probability admits a two-layer decomposition\" I don't immediately see why this is true. I don't think the notation of taking a max over $P_y \\sim (\\hat\\mu_y, \\Sigma_y)$ was ever defined.\n2. The proof ends without reducing to something that looks like the objective $\\min_{w \\in W} \\sum_y \\tau_y^\\varphi (w)$. Is there some kind of extra dual argument needed? All of the steps should be made clear in the proof.\n\nI couldn't follow the proof of Proposition 3.5 for the same reasons as Proposition 3.5; I didn't check the rest of the proofs.\n\n**Motivation.** Some of the results didn't feel well-motivated.\n1. It seems that one major addition over Lanckriet et al. (2003) is the use of new metrics over covariance matrices in the MPM. But it's not clear why this is desirable. The authors note \"the [previously used] quadratic divergence ... does not coincide with any distance between probability distributions\". Why is this something we should want given the goal of producing algorithmic recourses that are stable to model shift? Why study both the Bures and Fisher-Rao MPM?\n2. What is the purpose of the asymptotics in the paper? It seems like the asymptotic regime studied requires at least one of the radii of the ambiguity sets to grow to infinity. Why should we be concerned about the model's performance when we are infinitely uncertain about things? What do the derived limits tell us about the suitability of these MPMs for algorithmic recourses? \n3. I'm not exactly sure what the experiments tell us about the proposed method. In Section 6.2, in some cases, it looks like one of the proposed methods is outperforming competing methods according to some metrics. Why is this happening? What about the datasets is causing FR-MPM-PROJ to succeed? Additionally, the experiments in Figure 4 only show the use of the Fisher-Rao distance; what about using Bures or quadratic distances?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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: Reject