On the Impact of Adversarially Robust Models on Algorithmic Recourse
Authors: Satyapriya Krishna
Chirag Agarwal
Himabindu Lakkaraju
Venue: Submitted to ICLR 2023 (2023)
Keywords: Algorithmic Recourse
Adversarial Robustness
Machine Learning

Abstract: The widespread deployment of machine learning models in various high-stakes settings has underscored the need for ensuring that individuals who are adversely impacted by model predictions are provided with a means for recourse. To this end, several algorithms have been proposed in recent literature to generate recourses. Recent research has also demonstrated that the recourses generated by these algorithms often correspond to adversarial examples. This key finding emphasizes the need for a deeper understanding of the impact of adversarially robust models (which are designed to guard against adversarial examples) on algorithmic recourse. In this work, we make one of the first attempts at studying the impact of adversarially robust models on algorithmic recourse. We theoretically and empirically analyze the cost (ease of implementation) and validity (probability of obtaining a positive model prediction) of the recourses output by state-of-the-art algorithms when the underlying models are adversarially robust. More specifically, we construct theoretical bounds on the differences between the cost and the validity of the recourses generated by various state-of-the-art algorithms when the underlying models are adversarially robust vs. non-robust. We also carry out extensive empirical analysis with multiple real-world datasets to not only validate our theoretical results, but also analyze the impact of varying degrees of model robustness on the cost and validity of the resulting recourses. Our theoretical and empirical analyses demonstrate that adversarially robust models significantly increase the cost and reduce the validity of the resulting recourses, thereby shedding light on the inherent trade-offs between achieving adversarial robustness in predictive models and providing easy-to-implement and reliable algorithmic recourse.

Under review as a conference paper at ICLR 2023
ON THE IMPACT OF ADVERSARIALLY ROBUST MODELS ON ALGORITHMIC RECOURSE
Anonymous authors Paper under double-blind review
ABSTRACT
The widespread deployment of machine learning models in various high-stakes settings has underscored the need for ensuring that individuals who are adversely impacted by model predictions are provided with means for recourse. To this end, several algorithms have been proposed in recent literature to generate recourses. Recent research has also demonstrated that the recourses generated by these al- gorithms often correspond adversarial examples. This key finding emphasizes the need for a deeper understanding of the impact of adversarially robust models (which are designed to guard against adversarial examples) on algorithmic recourse. In this work, we make one of the first attempts at studying the impact of adver- sarially robust models on algorithmic recourse. We theoretically and empirically analyze the cost (ease of implementation) and validity (probability of obtaining positive model prediction) of the recourses output by state-of-the-ar algorithms when the underlying models are adversarially robust. More specifically, we con- struct theoretical bounds on the differences between the cost and the validity of the recourses generated by various state-of-the-art algorithms when the underlying models are adversarially robust vs. non-robust, We also carry out extensive empiri- cal analysis with multiple real-world datasets to not only validate our theoretical results, but also analyze the impact of varying degrees of model robustness on the cost and validity of the resulting recourses. Our theoretical and empirical analyses demonstrate that adversarially robust models significantly increase the cost and reduce the validity of the resulting recourses, thereby shedding light on the inherent trade-offs between achieving adversarial robustness in predictive models and providing zasy-to-implement and reliable algorithmic recourse.
INTRODUCTION
As machine learning (ML) models are increasingly being deployed in high-stakes domains such as banking, healthcare, and criminal justice, it becomes critical to ensure that individuals who have been adversely impacted (e.g., loan denied) by the predictions of these models are provided with a means for recourse. To this end, several techniques have been proposed in recent literature to provide recourses to affected individuals by generating counterfactual explanations which highlight what features need to be changed and by how much in order to flip model's prediction (Wachter
et al. 2017: Dhurandhar et al. 2018: Ustun et al.) 2019a Pawelczyk et al.] [020a] Karimi al.
2021b Verma et al. 2020 For instance, Wachter et al. (017)) proposed a gradient-basee based approach which returns the nearest counterfactual resulting in the desired prediction. [Ustun et al. (2019a)
proposed integer programming- based approach to obtain actionable recourses for linear classifiers. More recently. Karimi et al. (2021b) 2020c) leveraged the causal structure of the underlying data for
generating recourses (Barocas et al. 2020 Mahajan al. 2019
Pawelczyk et al. 2020a).
Prior research has also theoretically and empirically analyzed the properties of the recourses generated by ofate-of-the-art algorithms. For instance, several recent works (Rawal et al.) [021] Pawelezyki et af.] 2020a; Dominguez-Olmede
et al.] 2022] Upadhyay et al.] 2021b) demonstrated that the recourses output by state-of-the-art algorithms are not robust to small perturbations to input instances, underlying model parameters, and to the recourses themselves. More recently, Pawelczyk et al.
'The terms counterfactual explanations Waccher al. 2017). contrastive explanations (Karmmi et al. 2020b)
and recourse (Ustun al. 2019a) have often been used interchangeably in prior literature.

---

Under review as a conference paper at ICLR 2023
(202a)) demonstrated that the recourses output by state-of-the-art algorithms are very similar to adversarial examples. This finding is critical because there have been several efforts in the literature on adversarial ML (Huang et al. 2011 Kurakin et al., 2016) Biggno & Roli 2018) to build adversarially robust models that are not susceptible to adversarial examples. However, the impact of such models on the quality and the correctness of the recourses output by state-of-the-art algorithms remains unexplored. The aforementioned connections between adversarial examples and recourses underscore the need for deeper investigation of the impact of adversarially robust models (which are designed to guard against adversarial examples) on algorithmic recourse. Such an investigation becomes particularly critical as the need for adversarial robustness of predictive models as well as the ability to obtain easy-to-impee -impleettm and reliable recourses have often been touted as the cornerstones of trustworthy and safe MI. both by prior research as well as recent regulations Voigt & Von dem Bussche (2017): Hamon et al. (2020). However, there is no prior work that investigates the relationship and/or the trade-offs between these two critical pillars of trustworthy and safe ML.
In this work, we address the aforementioned gaps by making the first ever attempt at studying the impact of adversarially robust models on algorithmic recourse. We theoretically and empirically analyze the cost (ease of implementation) and validity (probability of obtaining positive model prediction) of the recourses output by oftte-of-the-rtt algorithms when the underlying models are adversarially robust. More specifically, we construct theoretical bounds the differences between the cost and the validity of the recourses generated by various state-of-the-art algorithms (e.g.. gradient-based (Wachter et al., 2017: Laugel et al. (017)) and manifold-basee (Pawelczyk al. 2020b) methods) when the underlying models are adversarially robust vs. non-robust (See Section 4). To this end, we first derive theoretical bounds on the differences between the weights (parameters) of adversarially robust vs. non-robust models and then leverage these to bound the differences in the costs and validity of the recourses corresponding to these two sets of models.
We also carried out extensive empirical analysis with multiple real-world datasets from diverse domains. This analysis not only validated our theoretical bounds, but also unearthed several inter- esting insights pertaining to the relationship between adversarial robustness of predictive models and algorithmic recourse. More specifically, we found that the cost differences between the recourses cor- responding to adversarially robust vs. non-robust models increase as the degree of robustness of the adversarially robust models increases. We also observed that the validity of recourses worsens as the degree of robustness of the underlying models increases. We further probed these insights by visualiz- ing the resulting recourses in low dimensions using t-SNE plots, and found that the number of valid re- courses around given instance reduces the degree of robustness of the underlying model increases.
2 RELATED WORK
Algorithmic Recourse. Several approaches have been proposed in recent literature to provide
recourses to affected individuals (Dhurandhar et al. 2018 Wachter et al., 2017 Ustun et al. 2019a
Van Looveren & Klaise| 2019 Pawelczyk et al. 2020at Mahajan et al.) 2019 Karimi et al. 2020a
Dandl et | 2020). These approaches can be broadly categorized along the following dimensions
Verma al. (2020): type of the underlying predictive model (e.g., tree based vs. differentiable
classifier), rype of access they require to the underlying predictive model (e.g.. black box vs. gradient access), whether they encourage sparsity in counterfactuals (i.e., only a small number of features should be changed), whether counterfactuals should lie on the data manifold, whether the underlying causal relationships should be accounted for when generating counterfactuals, and whether the output produced by the method should be multiple diverse counterfactuals or single counterfactual. In addition. RRwal & Lakkaraju (2020) also studied how to generate global, interpretable summaries of counterfactual explanations. Some recent works also demonstrated that the recourses output by state- of-the-art art techniques might not be robust, i.e., small perturbations to the original instance (Dominguez. Olmedo et al. 2021 Slack al., (221). the underlying model (Upadhyay et al. 202 Rawal et al., 2021), or the recourse (Pawelczyk et al. 2022ch itself may render the previously prescribed recourse(s) invalid. These works also formulated and solved minimax optimization problems to find robust recourses to address the aforementioned challenges.
Adversarial Examples and Robustness. Prior works have shown that complex machine learning models, such as deep neural networks, are vulnerable to small changes in input (Szegedy et al. 2013). This behavior of predictive models allows for generating adversarial examples (AEs) by
2

---

Under review as a conference paper at ICLR 2023
adding infinitesimal changes imput targeted to achieve udversary-selectee outcomes (Szegedy et al. 2013) Goodfellow et al.] 2014). Prior works have proposed several techniques to generate AEs using varying degrees of access to the model, training data, and the training procedure (Chakraborty et al., 2018). While gradient-base based methods (Goodfellow et al. 2014; Kurakin et al. 2016) return the smallest imput perturbations which flip the label as adversarial examples, generative methods (Zhao ct al., (017) constrain the search for adversarial examples to the training data-manifold. Finally, some methods (Cisse et al. 2017) generate adversarial examples for non-differentiable and non- decomposable measures in complex domains such as speech recognition and image segmentation. Prior works have shown that Empirical Risk Minimization (ERM) does not yield models that are robust to adversarial examples (Goodfellow et al. adversarially robust models, Madry et al. (2017) minimizes the worst-case loss within some e-ball perturbation region around the input instances.
2014, Kurakin et al. 2016). Hence, to reliably train proposed the adversarial training objective which
Intersections between Adversarial ML and Model Explanations. There has been a growing interest in studying the intersection of adversarial ML and model explainability (Hamon et al. 2020). Among all the existing works focusing on this intersection, two explorations are relevant to our work (Shah et al.) 2021 Pawelczyk et al. 2022b). [Shah al. (2021) studied the interplay between adversarial robustness and post hoc explanations (Shah et al.) (021) and demonstrated that gradient-based feature attribution methods (e.g., vanilla gradients, gradient times input, integrated gradients, smoothgrad) may severely violate the primary assumption of attribution - features with higher attribution are more important for model prediction - in case of non-robust models. However, their results also demonstrate that such a violation does not occur when the underlying models are robust lg and line input perturbations. More recently, PPaweleyyk al. (2022a) demonstrated that recourses generated by certain state-of-the-ar methods are very similar to adversarial examples, and also argued that the methods proposed to output recourses and adversarial examples are designed with similar goals of changing the input minimally in order to achieve the desired outcome. While the aforementioned works explored the connections between adversarial ML and model explanations, none of these works focus analyzing the impact of adversarially robust models on the recourses output by state-of-the art algorithms.
3 PRELIMINARIES
Notation. In this work, we denote a classifier f : y' mapping features x E X' labels y E y, where is d-dimensional feature vector. We define non-linear activation function o(.) such that fx) = (x(())), where h(x) is the logits of the linear model of the form -(x)=w* x, for parameter weights w. In addition, represent the non-robust and adversarially robust models using fNR(x) and fR (x). Below we describe the methodological frameworks used for comparing recourses generated from non-robust and adversarially robust models.
Adversarially Robust models. Despite the superior performance of machine learning (ML) models, they are susceptible to adversarial examples (AEs), i.e., inputs generated by adding infinitesimal perturbations to the original samples targeted to change prediction label (Agarwal et al.) 2019). One standard approach ameliorate this problem is training model using adversarial training which minimizes the worst-case loss within some perturbation region (the perturbation model) (Kolter & Madry). In particular, for a classifier, f parameterized by weights 9, loss function E(-), and training data {x,, Vi (1.2(1......m)) E Duain the optimization problem of minimizing the worst-case loss within lp 2p-none norm perturbation with radius é is:
min
Σ
max E(fo(x + 8)), v), SEDp.e
Pirain
where Dirain denotes the training dataset and Ap.c = (6 : | e) is the lp ball with radius e centered around sample x. We use p for our theoretical analysis resulting in closed-fom solution of the model parameters 0.
Algorithmic Recourse. One of the ways in which recourse can be realized is by explaining to affected individuals what features in their profile need to change and by how much in order to obtain a positive outcome. Counterfactual explanations which essentially capture the aforementioned information can therefore be used to provide recourse. The terms "counterfactual explanations" and "algorithmic recourse" have, in fact, become synonymous in recent literature (Karimi et al. 2020b Ustun et al.
3

---

Under review as a conference paper at ICLR 2023
2019b Venkatastubramanian & Alfano 2020). More specifically, algorithms that try to find algorith- mic recourses do so by finding a counterfactual x' = x + [ that is closest to the original instance and change the model's prediction f(x + <) to the target label. Next, describe three methods we use to understand the implications of adversarially robust models on algorithmic recourses.
Score CounterFactual Explanations (SCFE). Given the classifier f(x) ((h(x)) and distance function : Rd x Rd +R,, Wachter et al. (2017) define the problem of generating a recourse x' C for sample by minimizing the following objective:
arg min(h(x')) - s)² 2 + Ad(x'xx).
x'
where s is the target score for x', À is the regularization coefficient, and d(-) is the distance between sample and its counterfactual counterpart x'.
Given a Variational AutoEncoder (VAE) model with encoder E,y and decoder Go trained on the original data distribution Duain: C-CHVAE (Pawelczyk al.) 2020b) aims generate recourses in the latent space Z. where E, : - Z. The encoder &., transforms a given sample x into latent representation z Z and the decoder Go takes z as input and produces & as similar as possible x. To this end, given a sample C-CHVAE generates the recourse using the following objective function:
C-CHVAE.
5" = arg min|/</| such that f(G + <)) + f(x).
(3)
CEZ
where & allows to search for counterfactuals the data manifold and Go projects the latent counterfactuals to the feature space.
Growing Spheres Method (GSM). While the above techniques directly optimize specific objective functions for generating counterfactuals, GSM (Laugel et al., 2017) uses search-base algorithm to generate recourses by randomly sampling points around the original instance x until a sample with the target label is found. In particular, GSM first draws fg-sphere around given instance x, randomly samples point within that sphere, and checks whether any sampled points result in target prediction. Finally, they contract or expand the sphere until a (sparse) counterfactual is found and finally returned. GSM defines a minimization problem using function X x X - R4, where c(x, x') the cost of moving from instance x to counterfactual x'.
x
arg min x') f(x) + f(x)), x'EX
(4)
where x' sampled from the ball around x such that (xx) + c(x, -x|x'x|||+771X>
xllo- and E R4 is the weight associated to the sparsity objective.
4 THEORETICAL ANALYSIS
Next, we carry out a detailed theoretical analysis to bound the cost and validity differences of recourses generated by state-of offte--f-the-art recourse methods when the underlying models adversarially robust vs. non-robust, for the case of linear classifiers. More specifically, we compare the cost differences the recourses obtained using 1) gradient-based methods such as SCFE (Wachter al.) (Sec. 4.1.I) and 2) manifold-based methods such as C-CHVAE (Pawelczyk et al.) (020b) (Sec. 4.1.2 Finally, we show that the validity of algorithmic recourse generated using existing methods for robust models is lower compared to that of non-robust models (Sec. 4.2
4.1 COST ANALYSIS
The cost of generated algorithmic recourse is defined the distance (c.g., l or & distance) between the input instance x and the counterfactual x' obtained using a state-of-the-ar recourse finding method (Verma et al. 2020). Algorithmic recourses with lower costs are considered better since they enable minimal changes to input to achieve the desired outcome. Here, we theoretically analyze the cost difference of generating recourses using algorithmic recourse methods when the underlying models are non-robust and adversarially robust.
4.1.1 GRADIENT-BASED METHOD: SCFE
Next, we carry out a detailed theoretical analysis to bound the cost and validity difference recourses generated by state-of-the-ar recourse methods when the underlying models adversarially robust
4

---

Under review as a conference paper at ICLR 2023
vs. non-robust. We derive the lower and upper bound for the cost difference of recourses generated by the SCFE (Wachter et al. 2017) method when the underlying models are adversarially robust vs. non-
robust. Following previous works (Garreau & Luxburg 2020 Hardt & Ma 2017 Pawelezyk et al.) 2022b; Rosenfeld et al. 2020 Ustun et al., 2019b)) we focus on locally linear model approximations this lays the foundation for understanding non-linear model behavior. For the cost difference, first define the closed-form solution for the optimal cost Ç* required to generate a recourse.
Definition 1. (Optimal Cost from Pawelezyk el al. (2022b)) For given scoring function f with weights w the SCFE method generates a recourse x' for an input x using cost Ç such that:
5* =
(5)
where s h(x') approximation, and is a given hyperparameter.
) is the target residual, s is the target score for x, h(x)) is a local linear score
Theorem 1. (Cost difference for SCFE) For a given instance x, let XxR and x be the recourse generated using Wachter's 's algorithm for non-robust and adversarially robust models. Then, for normalized Lipschitz activation function a (.), the cost difference for the recourse generated for both models can be bounded as:
VNNR
S GRll2S
A
|NNR|
À || ||Wll:
(6)
WNR
[RR
A+ W
where WNR and Wg are the weights of the non-robust and adversarially robust models, X is the regularization coefficient in Wachter's algorithm, mNR=s-hNRR (x'), mR=s- ha (x') are the target residuals for robust (JR(x)= = ((()R(x)) and non-robust models (JwR (x)==((((n))) (x)))x))), respectively.
Proof Sketch. We derive the cost difference of recourses generated for non-robust and adversarially robust models by comparing their optimal solutions. Similar to (Pawelczyk al. (2022b), the upper bound results follow from Cauchy-Schwartz and triangle inequality. In addition, we also leverage reverse triangle inequality to derive a lower bound for the recourse difference. The equality of Equation entails that the upper bound of the recourse difference will have tighter bound if the fg-norms of the weights Wg and WB are bounded, and the lower bound of the recourse difference will be tighter if the output score of the non-robust and adversarially robust models is similar for the
given sample x. See Appendix A.I for the complete proof.
4.1.2 MANIFOLD-BASED METHOD: C-CHVAE
We extend our analysis of bounding the cost difference of generated recourses using manifold-based methods for non-robust and ad adversarially robust models. In particular, we leverage C-CHVAE (Pawel czyk et al., 2020b) that leverages variational autoencoders to generate counterfactuals. For a fair comparison, assume that both models the same encoder I, and decoder Go networks for learning the latent space of the given input space X.
Definition 2. (Bora et al. (2077)) An encoder model E is L-Lipschitz if Vz1, 22 Z, we have:
[|E(zı) E(z2) L L
Zzllp-
Using Definition 7 we now derive the lower and upper bounds of the cost difference of recourses generated for non-ro and adversarially robust models.
Theorem 2. (Cost difference for C-CHVAE) Let znR and ZR be the generated recourse from C- CHVAE (Pawelczyk et al.) (2226b) method in the latent space using an L-Lipschitz generative model ((-) for a non-robust and adversarially robust model. Then, by definition of C-CHVAE, ( SSR and xg= = + SR are the corresponding recourses in the input space. The cost difference between the recourses can then be bounded as:
L(ri - I ||<R [NKllp L(ră r
where L is the Lipschitz constant of the generative model, and roR and r be the corresponding radii chosen by the algorithm such that they successfully return a recourse for the non non-robust and adversarially robust model.
5

---

Under review as a conference paper at ICLR 2023
Proof Sketch. The proof follows from Definition 7 and the triangle inequality. It shows that the cost difference for generating recourses using C-CHVAE is bounded by the product of the Lipschitz constant of the generative model and the radii chosen by the C-CHVAE generate counterfactuals for the underlying non-robust and adversarially robust models. See Appendix A.2 for detailed proof. I7
4.2 VALIDITY ANALYSIS
The validity of a given recourse x' is defined as the probability that it results in the desired out- come (Verma et al. 2020), denoted by Pr(J(x') = 1). Below, we analyze the validity of the recourses by first deriving the upper bound of the difference non-robust and adversarially robust model weights, and then use this lemma to show that the validity of non-robust model is higher than for the adversarially robust model.
Lemma 1. (Difference between non-robust and adversarially robust model weights) For given instance x, let WNR and Wg be weights of the non-robust and adversarially robust model. Then, for normalized Lipschitz activation function (-)), the difference the weights Aw can be bounded as:
|1wll25 nn(ulix (12+evd)
where 1 is the learning rate, is the number of training epochs, and d is the dimension of the input features.
l to-norm perturbation ball, y is the label for x, n. the total
Proof Sketch. We derive the upper bound of the difference in non-robust and adversarially robust model weights, denoted by Aw: and show that is proportional to the dimension of the input features times the & perturbation ball around the sample See Appendix A.3 for the detailed proof.
Next, we show that the probability of a recourse action resulting in the desired outcome is greater for non-robust model compared to that of the adversarially robust model.
Theorem 3. (Validity Comparison) For given instance x E dR and desired target label denoted by unity, let XR and XNR be the counterfactuals for adversarially robust fR(x) and non-robust fNR (x) models respectively. Then, Pr(ffu(XN))
1) Pr(fR(XR) =1) if [fNR [Xx) fru (X S
nn(yy ||? 1|2-te d) xx|], where ii is the learning rate, is the f2-norm pertarbation ball, is the label for x. and n is the total number of training epochs.
Proof Sketch. We derive the difference between the probability that a valid recourse exists for a non-robust and adversarially robust model. Using data inequalities and Cauchy-Schwand we show that the condition for the validity is dependent on the weight difference of the models (Lemma I See Appendix A.4 for the detailed proof.
5 EXPERIMENTAL EVALUATION
In this section, empirically analyze the impact of adversarially robust models on the cost and validity recourses. First, we empirically validate our theoretical bounds on differences between the cost and validity of recourses output by state-of-the-ard recourse generation algorithms when the underlying models are adversarially robust vs. non-robust. Second, we carry out further empirical analysis to assess the differences in cost and validity of the resulting recourses the degree of the adversarial robustness of the underlying model changes on three real-world datasets.
5.1 EXPERIMENTAL SETUP
Here, we describe the datasets used for our empirical analysis along with the predictive models, algorithmic recourse generation methods, and the evaluation metrics.
Datasets. We use three real-world datasets for our experiments:
1) The German Credit dataset P comprises demographic (age, gender), personal (marital status), and financial (income, credit duration) features from 1000 credit applicants, with each sample labeled as "good" or "bad" depending on their credit risk. The task is to successfully predict if given individual is "good" or "bad" customer
https://archiii iss uci edu/ml http:///maaaaaatttteeeem /tttt log (germantcredi t+data)

---

Under review as a conference paper at ICLR 2023
in terms of associated credit risk. 2) The Adult dataset contains demographic (e.g., age, race, and gender). education (degree), employment (occupation, hours-per week), personal (marital status, relationship), and financial (capital gain/loss) features for 48,842 individuals. The task is to predict if an individual's s income exceeds $50K per year. 3) The COMPAS dataser has criminal records and demographies features for 18,876 defendants who got released on bail the U.S state courts during 1990-2009. The dataset is designed to train a binary classifier to classify defendants into bail (i.c., unlikely to commit violent crime if released) vs. no bail (i.e., likely to commit a violent crime).
Predictive models. We generate recourses for the non-robust and adversarially robust version of Logistic Regression (linear) and Neural Networks monn-lneea) models. We use two linear layers with sigmoid activation functions as our predictor and set the number of nodes in the intermediate layers to twice the number of nodes in the input layer, which is the size of the input dimension in each dataset.
Algorithmic Recourse Methods. We analyze the cost and validity for non-robust and adversarially robust models w.r.t. three popular classes of recourse generation methods, namely, gradient- based (SCFE), manifold-based (C-CHVAE), and random search-based (GSM) methods (described in Sec. 3)
Evaluation metrics. To concretely measure the impact of adversarial robustness on algorithmic recourse, we analyze the difference between cost and validity metrics for recourses generated using non-robust and adversarially robust model. To quantify the cost, we measure the average cost incurred to act upon the prescribed recourses across all test-set instances, i.c., Cost(x, x') [Pessl x
x2112. where x is the input and x' is its corresponding recourse. To measure validity, we compute the probability of the generated recourse resulting in the desired outcome, i.e., Validity (x, x')
(a':f(a)) a' =f=9(f.)) where g(x, returns recourses for input x and predictive model f.
Presa
Implementation details. We train non-robust and adversarially robust predictive models from two popular model classes (logistic regression and neural networks) for all three datasets. In the case of adversarially robust models, we adopt the commonly used min-max optimization objective for adver- sarial training using varying degree of robustness, i.e., c E {0, 0.02, 0.05, 0.10, 0.15, 0.20, 0.25, 0.3). Note that the model trained with e=0 is the non-robust model. Following Ballet et al. (2019) and Erdemir et al.) (202T), we pre-processed the input data by removing categorical features for efficient training of our models. We follow Pawelczyk et al. (002bb) to set the hyperparameters for the algorithmic recourse methods.
5.2 EMPIRICAL ANALYSIS
Next, we describe the experiments that we carried out to understand the impact of adversarial robust- ness of predictive models on algorithmic recourse. More specifically, we will discuss (I) empirical verification of our theoretical bounds, (2) empirical analysis of the differences between the costs of recourses corresponding to non-robust vs. adversarially robust models, and (3) empirical analysis to compare the validity of the recourses corresponding to non-robust vs. adversarialyy robust models.
Empirical Verification of Theoretical Bounds. We empirically validate our theoretical findings from Section on real-world datasets. In particular, we first estimate the empirical bounds (RHS of Theorems 22 for each instance in the test set by plugging the corresponding values of the parameters in the theorems and compare them with the empirical estimates of the cost differences between recourse methods (LHS of Theorems 2
recourses generated using gradient- and manifold- Figure @Jshow the results obtained from the aforementioned analysis of cost differences. We observe that our bounds are tight, and the empirical estimates fall well within our theoretical bounds. Similarly, observe that the validity of the non-robust model, denoted by Pr (z) = 1) in Theorem 3. was higher than the validity of the adversarially robust model for all the test samples in Adult,
German Credit, COMPAS datasets, following the condition in Theorem 3 90% samples for the three datasets) ) for large number of training iterations used for training ad adversarially robust models with E {0, 0.02, 0.05, 0.1, 0.15, 0.2, 0.25, 0.3).
Cost Analysis. To analyze the impact of adversarial robustness on the cost of recourses, we compute the difference between the cost for obtaining a recourse using non-robust and adversarially robust model and plotted this difference for varying degrees of robustness e. Results in Figure show a
7

---

Under review as a conference paper at ICLR 2023
Lowr Round Emsirical
1,0
Empinical Upper Bound
PrtfelMoodl prifate)))
1K Gills
Ii Gil
0.0
(b)
(c)
Figure I: Empirically calculated cost differences (in orange) and our theoretical lower (in blue) and up- per (in green) bounds for (a) C-CHVAE and (b) SCFE recourses corresponding adversarially robust (trained using 0-3.3 non-robust models trained on the Adult dataset. Figure (c) is the empirical difference between the validity of recourses for non-robust show violations of our theoretical bounds. See Appendix B for results using different values.
adversarially robust model. Results
scle
sale
scft
gom
gam
Cost Difference
Cost Difference
Cost Difference
2
0.00
0.00
0.55
0.10
0.16
0:26
0.30
0.00
0:02
0.16
0
0:15
0.0
020
0.20
02
0.05
0.15
0.20
0.25
0.30
Epsilon
Epsllon
Epsilon
(a) Adult
(b) COMPAS
(c) German Credit
Figure 2: Analyzing cost differences between recourse generated using non-robust and adversarially robust neural networks for (a) Adult (b) COMPAS (c) German Credit datasets. We find that the cost difference (i.e., & norm) between the recourses generated for non-robust and adversarially robust models increases for increasing values of
significant increase in incurred costs to find algorithmic recourse for adversarially robust models compared the non-robust model for all the datasets with increasing degrees of robustness. We observe a similar trend for the case of logistic regression, as shown Figure 6 in Appendix B Further, observe relatively smoother increasing trend for cost differences in the of SCFE compared to others, which can be attributed to the stochasticity present C-CHVAE and GSM. We also observe a higher cost difference in SCFE for most datasets, which could result from the larger sample size used in C-CHVAE and GSM. We observe a similar trend in cost differences when the sample size per iteration is reduced, which also resulted in more iterations find recourse.
Validity Analysis. To analyze the impact of adversarial robustness on the validity of recourses, we compute the fraction of recourses resulting in the desired outcome, generated using non-robust and adversarially robust model under resource constraints, and plot it against varying degrees of robustness e. Results in Figure 3 show that there an even stronger impact of adversarial training on validity for neural networks trained the three datasets. We observe a similar pattern for the case the logistic regression model trained on the three datasets, shown in Appendix B On average, observe that the validity drops to zero for models adversarially trained with > 0.2. To understand this further, we use t-SNE visualization (Van der Maaten & Hinton 2008) a non-linear dimensionality reduction technique to map points in the dataset to two -wo-dimensional space and demonstrate a gradual decline valid recourses around a local neighborhood with increasing in Figure where and y be the names of reduced dimensions. This decline suggests that large
8

---

Under review as a conference paper at ICLR 2023
1.0
1.0
1.0
scfe
sofe
sofe
0.8
08
0.8
2006
Validity
Validity
0.6
0.4
02
02
0.0
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.02
0.00
0.10
0.20
0.28
0.30
0.00
0.02
0.06
0.10
t0 Epsilon
0.30
Epsilon
Epsilon
(a) Adult
(b) COMPAS
(c) German Credit
Figure 3: Analyzing validity of recourse generated using non-robust and adversarially robust neural networks for (a) Adult (b) COMPAS (c) German Credit datasets. We find that the validity decreases for increasing values
Epsilon:
Epsiion
Epsilon 0.25
Recourses musid Wild
Recoummes Incolit
Recoummes
Inceld
70
Valld
Velld
20-
10
10
0-
-30
10
-40
-40 -20
20
-10 -20
Figure A t-SNE visualization of the change in availability of valid recourses (orange) for adversar- ially robust models trained using [0, 0.15, 0.25], where non-robust model is model trained using e = 0. Results are shown for neural network model trained on the Adult dataset. We observe fewer valid recourses for higher values of in this local neighborhood.
number of recourses in the neighborhood of the input sample are now being classified with the same class as the input. Hence, this supports our hypothesis that adversarially robust models severely impact the validity of recourses and make the recourse search computationally expensive.
6 CONCLUSION
In this work, we theoretically and empirically analyzed the impact of adversarially robust models on algorithmic recourse. We theoretically bounded the differences between the costs of the recourses output by two state-of-the- counterfactual explanation methods (SCFE and C-CHVAE) when underlying models are adversarially robust vs. non-robust. In addition, we also bounded the differences between the validity of the recourses corresponding to adversarially robust and non- robust models. We empirically validated our theoretical results using three real-world datasets (Adult, COMPAS, and German Credit) and two popular model classes (neural networks and logistic regression). Our theoretical and empirical analyses demonstrated that adversarially robust models significantly increase the cost and reduce the validity of the resulting recourses, thereby highlighting the inherent trade-off's between achieving adversarial robustness in predictive models and providing casy-to-impllment and reliable algorithmic recourses. Our work also paves the way for several interesting future research directions at the intersection of algorithmic recourse and adversarial robustness predictive models. For instance, given the aforementioned trade-offs, it would be interesting to develop novel techniques which enable end users to navigate these trade-off's based on their personal preferences e-g., an user may choose sacrifice the adversarial robustness the underlying model in order to secure lower cost recourses.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Chirag Agarwal, Anh Nguyen, and Dan Schonfeld. Improving robustness to adversarial examples by encouraging discriminative features. In ICIP. IEEE, 2019.
Vincent Ballet, Xavier Renard, Jonathan Aigrain, Thibault Laugel, Pascal Frossard, and Marcin Detyniecki. Imperceptible adversarial attacks on tabular data, arXiv preprint urXiv:1911.03277. 2019.
Solon Barocas, Andrew D. Selbst, and Manish Raghavan. The hidden assumptions behind coun- terfactual explanations and principal reasons. In Proceedings of the Conference on Fairness, Accoumtaillity and Transparency (FAT*), New York, NY, USA, 2020. ACM.
Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. Pattern Recognition, 84:317-331, 2018
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using generative models. In ICML. PMLR, 2017.
Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopad- hyay. Adversarial attacks and defences: A survey, arXiv preprint arXiv: 1810.0009, 2018.
Moustapha Cisse, Yossi Adi, Natalia Neverova, and Joseph Keshet. Houdini: Fooling deep structured prediction models. arXiv preprint 170.70037.33 2017.
Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl. Multi-objectinn counterfactual explanations. In International Conference on Parallel Problem Solving from Nature, pp. 448-469. Springer, 2020.
Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. In Advances Neural Information Processing Systems (NeurIPS), 2018
Ricardo Dominguez-Olmedee Amir- Hossein Karimi, and Bernhard Schölkopf. On the adversarial robustness of causal algorithmic recourse. arXiv:2112.11311 2021.
Ricardo Dominguez-Olmedo. Amir H Karimi, and Bernhard Schölkopf. On the adversarial robustness of causal algorithmic recourse. In International Conference on Machine Learning, pp. 5342. PMLR, 2022.
Ecenaz Erdemir, Jeffrey Bickford, Luca Melis, and Sergul Aydore. Adversarial robustness with non-uniform perturbations. Advances in Neural Information Processing Systems, 34:19147-19159, 2021.
Damien Garreau and Ulrike Luxburg. Explaining the explainer: A first theoretical analysis of lime. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1287-1296. PMLR, 2020.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572. 2014.
Ronan Hamon, Henrik Junklewitz, and Ignacio Sanchez. Robustness and explainability of artificial intelligence. Publications Office of the European Union, 2020.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. In International Conference on Learning Representations (ICLR), 2017.
Ling Huang, Anthony D Joseph, Blaine Nelson, Benjamin IP Rubinstein, and Doug Tygar. Ad- versarial machine learning. In Proceedings of the 4th ACM workshop on Security and artificial intelligence, pp. 43-58 2011.
Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Model-agnostic counterfactual explanations for consequential decisions. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020a.
10

---

Under review as a conference paper at ICLR 2023
Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: definitions, formulations, solutions, and prospects. arXiv:2010.04050, 2020b.
Amir-Hossein Karimi, Julius von Kügelgen, Bernhard Schölkopf. and Isabel Valera. Algorithmic recourse under imperfect causal knowledge: a probabilistic approach. In Conference on Neural Information Processing Systems (NeurlPS), 2020c.
Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: contrastive explanations and consequential recommendations, ACM Computing Surveys (CSUR), 2021a.
Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counter- factual explanations to interventions. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pp. 353-362, 2021b.
Zico Kolter and Aleksander Madry. Adversarial robustness theory and practice. models/
https://
Alexey Kurakin, Ian Goodfellow, Samy Bengio, et al. Adversarial examples in the physical world, 2016.
Thibault Laugel, Marie-Jeanne Lesot, Christophe Marsala, Xavier Renard, and Marcin Detyniecki. Inverse classification for comparison-basee interpretability in machine learning. arXiv, 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 2017.
Divyat Mahajan, Chenhao Tan, and Amit Sharma. Preserving causal constraints in counterfactual explanations for machine learning classifiers. arXiv preprint arXiv: arXiv: 1912.03277, 2019.
Martin Pawelezyk, Klaus Broelemann, and Gjergji Kasneci. Learning model-agnostic counterfactual explanations for tabular data. In Proceedings of The Web Conference 2020 (wwW). ACM, 2020a.
Martin Pawelczyk, Klaus Broelemann, and Gijerji Kasneci. Learning model-agnostic counterfactual explanations for tabular data. In Proceedings of The Web Conference 2020, pp. 3126-3132, 2020b.
Martin Pawelczyk, Chirag Agarwal, Shalmali Joshi, Sohini Upadhyay, and Himabindu Lakkaraju. Exploring counterfactual explanations through the lens of adversarial examples: theoretical and empirical analysis. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022a.
Martin Pawelczyk, Chirag Agarwal, Shalmali Joshi, Sohini Upadhyay, and Himabindu Lakkaraju. Exploring counterfactual explanations through the lens of adversarial examples: theoretical and empirical analysis. In AISTATS. PMLR, 2022b.
Martin Pawelezyk, Teresa Datta, Johannes van-den Heuvel, Gjergji Kasneci, and Himabindu Lakkaraju. Algorithmic recourse in the face of noisy human responses. arXiv preprint 0676:22003.0666,, 2022c.
Kaivalya Rawal and Himabindu Lakkaraju. Interpretable and interactive summaries ofactionable recourses. In Advances Neural Information Processing Systems (NeurIPS), volume 33, 2020.
Kaivalya Rawal, Ece Kamar, and Himabindu Lakkaraju. Algorithmic recourse in the wild: Under- standing the impact of data and model shifts. arXiv:2012. 2021.
Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to label- flipping attacks via randomized smoothing. In International Conference on Machine Learning, pp. 8241- PMLR, 2020.
Harshay Shah, Prateek Jain, and Praneeth Netrapalli. Do input gradients highlight discriminative features? Advances in Neural Information Processing Systems, 34:2046-200 2059, 2021.
11

---

Under review as a conference paper at ICLR 2023
Aaron Sidford. sidford mss213 1aclll__s29o__11 lec4 v5 share. htsps://xeb swwnfora....... edu/ MitEorra/courss/22EEE opt theory/sidfora 2020fa mse213 cs269o. 1ec4.pdi
(Accessed on 09/06/2022).
Dylan Slack, Sophie Hilgard, Himabindu Lakkaraju, and Sameer Singh. Counterfactual explanations can be manipulated. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv, 2013.
Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorithmic recourse. In Advances Neural Information Processing Systems (NeurIPS), volume 34, 202 la
Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorithmic recourse. NeurIPS, 2021b.
Berk Ustun, Alexander Spangher, and Y. Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Faimess, Accountability, and Transparency (FAT*), 2019a.
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, 2019b.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Arnaud Van Looveren and Janis Klaise. Interpretable counterfactual explanations guided by proto- types. arXiv preprint arXiv: 19t.:0997000000 2019.
Suresh Venkatasubramanian and Mark Alfano. The philosophical basis of algorithmic recourse. In Proceedings of the Conference on Fairness, Accountabiliry, and Transparency (FAT*), New York, NY, USA, 2020. ACM.
Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning: A review. arXiv:2010. 10596, 2020.
Paul Voigt and Axel Von dem Bussche. The general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 1033152676;11--5555, 2017.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harvard JL & fech.,2017
Zhengli Zhao, Dheeru Dua, and Sameer Singh. Generating natural adversarial examples. arXiv preprint arXiv: 1342, 2017.
A PROOF FOR THEOREMS IN SECTION 4
Here, provide detailed proofs of the Lemmas and Theorems defined in Section
A.1
PROOF FOR THEOREM 1
Theorem 1. (Cost difference for SCFE) For given instance X. let Xxa and x'2 be the recourse generated using Wachter's 's algorithm for the non-robust and adversarially robust models. Then, for normalized Lipschitz activation function o.)), the difference in the recourse for both models can be bounded as:
A A 7 (/s WNR, WR) S ||SRR 2 A WNNR
|| |1 +
wRll
(10)
A
WR
where WNR and wa the weights of the non-robust and adversarially robust models, X is the regularization coefficient Wachter's 's algorithum, (p()) is a function that measures the shift in the model weights using the target and predicted scores.
12

---

Under review as a conference paper at ICLR 2023
Proof. Following the definition of SCFE in Equation "closest" to the original instance x by minimizing the following objective:
find counterfactual sample x' that
arg migm(((((') - y²)² + Ad(x'xx),
(11)
x
where s the target score, is the regularization coefficient, and d(-) is the distance between the original and counterfactual sample x'.
Lower bound. Using Lemma 1, the optimal cost for generating valid recourse for non-robust RC and adversarially robust (Cx) model can be written as:
SNR MNN X+ [[WNR
WNR
(12)
CR = YR X+ wRIB
WR.
(13)
where MNR s X and my w x. Subtracting and taking l2 mo-m on both sides of we get:
Eqn. 12
and Eqn. 13
A
X
||
<Rll2
MNN
WNR
WR
[NNR A
WR
||&RR - 1Rll2 2
MNN
WNR
1/R
WR (Using reverse triangle inequality)
WNR
+
|| [R
||CRR - 1Rll2 2
MNN + [wwRR
WNR
||GRR 1Rll2 IA
MNN
WNR
17R
WR
(Since, À << ||w
WNR
[R
|R - 1ill2 N A
|W ll2
|WR
|
[wR]
||SRR
l2ll2
2
MNR
WR
[NNlll2
WRll2
Upper bound. Again, using the optimal recourse cost (Definition D we can derive the upper bound of the cost difference for generating recourses using non-robust and adversarially robust models:
(s W x)
(s w x)
||5R =
lRll2
A + || WNRl
A ||wR|1?
(s x
(W x - s)
A + WNRl|
WNR
A + ||wR| 11
WR
(s wf x)
(s w x)
|wNl
|wlll
(Using Triangle Inequality)
A |NNR|
X ||]/
Note that the difference between the target and the predicted score for both non-robust and adversari- ally robust models is upper bounded by term that always positive. Hence, we get:
A
A
[RR
GEll2 <
|wNlll
+
|Rll |l
WNRll
+
A.2 PROOF FOR THEOREM 2
Theorem 2. (Cost difference for C-CHVAE) Let ZnR and Zg be the solution returned by the C- CHVAE (Pawelezyk al. 2020b) algorithmic recourse method by sampling from ly-norm ball in
13

---

Under review as a conference paper at ICLR 2023
the latent space using L-Lipschitz generative model g(-) for non-robust and adversarially
robust model. By definition of the recourse method, let XNR = ((NNK) and Xg. = [(zx) be the corresponding recourses in the input space. The difference between them then be bounded
MLTR T S ||XR - XNR 1 L(rk + (iR),
(14)
where the Lipschitz constant of the generative model, and VāR and ri be the corresponding radii chosen by the algorithm such that they successfully return recourse for the non-robust and adversarially robust model.
Proof. From the formulation of the counterfactual algorithm, we can write the difference between XR and XNR as:
XR
XNR|I p (Zg) Go (ZNR))l
(15)
Lower bound. Here, we present a lower bound on the lp norm of the cost difference between baseline and robust model. Using Equation [5] we get:
XR XNR|IP 1|p
= | (ZR) Go (z) Go (ZRR) + Go (z)
(16)
2 (ZR) - Go (z) 11p 11 (ZNR) Go (z)
(since ||a b|bp> || (|6||p)
2 L IZR z z|Ip- | z|Ip
(17)
X xl 2 L(rR -(R))
(Using (Sidford)
where z is the latent space representation for the original point x, rR and FNR the radius of the f--norm for generating samples from the robust and baseline model. Note that using the radius of the
bp norm in the above equation provides tighter lower bound.
Upper bound. Using Equation inequality.
15
we can derive the upper bound using Lemma and the triangle
|R XxRXXRl l1p S 90 (ZR)
x|I Go ((ZRR))le
(Using triangle inequality)
Go (zz) (z) [g (o(ZN)]lp
(18)
< L||ZR ZII - ZNRllz
(Using Lemma 1)
XR XNR ll S L(r + rkR);
(19)
where r and "NR is the radius of the lp ep-norm for generating samples from the robust and baseline model, respectively.
A.3 PROOF FOR LEMMA 1
Lemma 1. (Difference between non-robust and adversarially robust model weights) For given instance x, let WNR and wg be weights of the non-robust and adversarially robust model. Then, for a normalized Lipschitz activation function a()), the difference in the weights Aw can be bounded as:
|Awll refeallx (e2+
(20)
where y is the learning rate, is the fz-norm perturbation ball, y is the label for x, is the total number of training epochs, and is the dimension of the input features.
Proof. Without loss of generality, we consider the case of binary classification which uses the binary cross entropy or logistic loss. Let denote the baseline and robust models as fNR (x)= x and f where we have removed the bias term for simplicity. We consider the class label as E [+1,-11, and loss function (x)( log(1 + exp( - (x))). Note that an adversarially robust model fR(x) is commonly trained using min-max objective, where the inner maximization
problem is given by:
max L(wT(x + +),)))))))))) [
(21)
where 5 is the adversarial perturbation added to a given sample x and c denotes the the perturbation norm ball around x. Since our loss function is monotonic decreasing, the maximization of the loss function applied to a scalar is equivalent to just minimizing the scalar quantity itself, i.e.,
max L (y (w](x + 6))) = c ( min y (w + +0)) = -c(u (V(((x) [
+ min
w
[
(22)
14

---

Under review as a conference paper at ICLR 2023
The optimal solution minjs Se y- wid is given by -c/ (Kolter & Madry). Therefore, instead of solving the min-max problem for an adversarially robust model, we can convert it to a pure minimization problem, i.c.,
min L (y- (Wxx) <([wll]) Wa
(23)
Correspondingly, the minimization objective for a baseline model is given by mill C (3/ (w3Rx)) Looking into the training dynamics under gradient descent, we can define the weights at epoch 't' for a baseline and robust model as a function of the Jacobian the loss function with respect to their corresponding weights, i....
WNR Wo
V wxR L (JV-NN (x))
(24)
WR- Wo
V Wa C (v.SR(x) - <l|ww]l1),
(25)
where 77 is the learning rate of the gradient descent optimizer, Wo is the weight initialization of both models.
exp(-v-fNR(x)) (xx((-v-fN(xx)
V Wine (y. fxR(x))
y.x!
exp( f. sep(--y.x(x4 (x) + c||wwlll) (12)
V Ws L (v.JR(x) - <||wR|li)
(-y.x" e.sign(wR))
exp( sxp(--yfR(( + + w[|l]]
where sign(x) return +1, -1, for x > 0, x < 0, x = 0 respectively and oxx)= T+exp( x) is the sigmoid function. Let us denote the weights of the baseline and robust model at the n-th iteration as WäR and w respectively. Hence, we can define the n-th step of the gradient-descent for both models as:
w TI
V LNR (-)
(26)
NR
WNR
WR
W
1
V
Lx()),
(27)
where 77 is the learning rate the gradient descent optimizer. Taking n = 1, we get:
WNR
WNR = 17 wh CNR(.)
(28)
R WR V Lxx
(29)
where w and w are the same initial weights for the baseline and robust models. Subtracting both equations, we get:
w NR
w
wit
PNR()
V wi (-)
(30)
1
Similarly, for 2 and using Equation 30 get the following relation:
2
w
w
wk
Vwi LNR (.) V (.x())
77
17
2
NR
w
Vwo
LNR (-) + Vwwg CNR( (-) wwg VwzC2()
77
15

---

Under review as a conference paper at ICLR 2023
Using the above equations, now write the difference between the weights of the baseline and robust models at the n-th iteration as:
WNR
WR
wks (NR(.)
Σ
v wi
LR(-)
7
1=0
(o(v-[R((x))
1)yxx
- -(wwall) 1)xxx (ggn))
i=0
(x))xx Σ
(o(.ff(()) -eff((x))>lllw/lbbbG <llwillb)lxxx sign(w'n)) + sign(wir)
(()J)n(x))xx'
(d(vff(x))((xx - sign( (wxk)) + sign(w'x))
(Using ola - b) s o(a) for > 0)
-oU,f((()) y.x²
(((xf((x)) - 1) sign(w'r)
Using no-m on both sides, we get:
|| -w
(((xf((x)) - 1) sign(w -o(.ff(()))( yxx"
(oly.fie(x) - ( - yxx²
12+
(oly.f((x)) - -)) sign( sign(w (w))))l
(Using Triangle Inequality)
(x)-fir()) -x y.x" 122evd d
1o (x( 1||2
(o(u-Ri((x) - yxx Ilatevd l
fR - -1ll2
1
- 0 (() (x)) Ilatex Σ lo 11/2
==0
S n 12tevd
(x()f((x)) 11/2
S <nllyx'
2 +
((){{(x)))
(since the term inside ||: scalar)
<nlyyx dn
|| ||wlla |l2 < nn(y||*? (n(u)x>21l=eeev (|2+eVd)
A.4 VALIDITY
Theorem (Validity Comparison) For given instance x E TRd and desired target label denoted by unity, let xR and XNR be the counterfactuals for adversarially robust fx(x) and non-robust fNR (x) models respectively. Then, Pr (x = 1) z Pr(fR(xR) = 1) if [xNR(xR) - .NRR (xx(xN)) nn(yl)x tey d) [[ xx lb. where nj is the learning rate, e is the f2-norm perturbation ball, is the
label for and is the total number of training epochs.
16

---

Under review as a conference paper at ICLR 2023
Proof. In a logistic regression case, Pr(f(x)= = T+o=ix which is the sigmoid of the model output. Next, derive the difference in probability of valid recourse from non-robust and adversarially robust model:
eWR MAR
Pr(JNR (T(JNN(XNR) = Pr([R(xx)=
(31)
1 1 e e.W Xx
e Wi
(32)
(1+ 6 xx) + ewhn
Since (1 + ew xxunn))) > 0, so Pr(JNR(XXX)) 1) 2 Pr(fR(xR) 1)) occurs when,
"iaxxR > e wxxx xR
(33)
WNR (XNR XR) (wk. WNR XR
(Taking natural logarithm both sides)
WIRR (xR XNR) - (WNRR wikl )RR
(34)
w (xR XNR) - |( wi )xRR
(Taking norn on both sides)
WIR (xR XNR) )| < | wR|l|xx| ||
(Using Cauchy-Schwand
W (XRR XNR) - m0]2v||==122+ee< [
(From Lemma
[FNR(XR) (XNR)) - nn/(y//x 1lee=l/eeee/lll
(35)
B ADDITIONAL EXPERIMENTAL RESULTS
In this section, we have plots for cost differences, validity, and adversarial accuracy for the two logistic regression and neural network models trained on three real-world datasets.
17

---

Under review as a conference paper at ICLR 2023
1.0
1.0
10
gam
gam
gam
saal Balidit
00.8
Valliity
Vellinn
0.6
0.4
64
02
0.00
0.05
0.10
0.5
0.20
0.23
0.30
0d8
0110
0.gg
0:00
0.28
0.30
0.6
010
0ig
0m
Epsilon
Epsilon
Epsilon
(a) NN Adult
(b) NN German Credit
(c) NN COMPAS
1.0
1,0
gki
gam
0.8
validity
0.8
Validity
Valldity
6.6
0.4
3.4
C44
02
C3
gam
0000
0.05
0.55
0.20
0.2
0.30
0,02
010
0
0.0
025
0.0
0.0
0.10
0.0g
0.5
0.30
Epsilon
Epsilon
Epsilon
(d) LR Adult
(e) LR German Credit
(I) LR COMPAS
Figure 5: Analyzing validity of recourse generated using non-robust and adversarially robust Logistic Regression(LR) and Neural Networks (NN) for Adult, COMPAS, and German Credit datasets. We find that the validity decreases for increasing values of c.
18

---

Under review as a conference paper at ICLR 2023
seto
siee
sotc
Cost Difference
Cost Difference
Cost
0.02
0:0
1.00
000
0.02
0.05
0:5
0:0
0.25
0.00
0.02
0.05
0.10
0.20
025
0.30
Epsilon
Epsilon
Epallon
(a) NN Adult
(b) NN German Credit
(c) NN COMPAS
catvoe
5afe
scfe g6m
scl
Cost Cost Difference
Cost Difference
0.6
0000
002
005
0110
015
0.20
025
0.30
0.15
0.20
0.25
0.30
0.06
0.10
0.20
0.2
0.3
Epalion
Epsilon
Epellon
(d) I.R Adult
(c) LR German Credit
(f) LR COMPAS
Figure 6: Analyzing cost differences between recourse generated using non-robust and adversarially robust Logistic Regression (LR) and Neural NetWorks(NN) for Adult, COMPAS, and German Credit datasets. We find that the cost difference (i.e., l norm) between the recourses generated for non- robust and adversarially robust models increases for increasing values
19

---

Under review as a conference paper at ICLR 2023
0.80
Accurscy
Accuracy
0.8
Accuracy
PROLLO
POOLL mode
066
RE0ML 9-1
D:55
mode002
FRONLO.2
0.25
model 0.25
modLL
0.80
0.2
Buts
10
0.20
022
0.40
0.00
0.30
Epsiion
Epsilon
Epsllon
(a) NN Adult
(b) NN German Credit
(c) NN COMPAS
0.70
Acouracy
0.70
modelL
0012
Accuracy
Accursoy
3.00
888
model 0
model
1s00.0.11
ruckL.0.5
0.55
n054
mwvel n
m05e.0
0.80
redel 0.2
nood 0.25
0.50
0.00
1.10
0.50
0.30
Epslion
Epsilon
Epsilon
L.R Adult
(c) LR
German Credit
LR
COMPAS
Figure 7: Here we plot the adversarial accuracy of the different models we trained on varying degree of robustness (c). As expected, observe the adversarial accuracy for the non-robust model is lowest out of all, and gradually gets better when the model is adversarially trained.
10
1.0
CCHWRE 1.0
CICHAEE
(rfss Prtfiiaal
0.5
0.0
0.0
0.0
(a) c=)= 0.05
(b) 0.2
(c) (c) 0.3
Figure 8: Comparison between the validity of recourses generated for non-robust and adversarially robust model for varying degrees of robustness (e)
20

---

Under review as a conference paper at ICLR 2023
4
Lower Bound
1.0
C-CHVAE
tmpirical
SCFE
Upper Bound
3
(XxR)) Pr(fa(xa))
2
0.5
115uR
Prifin (
1
0
0.0
(b)
Figure 9: (Linear Approximation Bound Verification) (a) Empirically calculated cost differences (in orange) for the original model and our thcoretical lower (in blue) and upper (in green) bounds for SCFE recourses corresponding to adversarially robust (trained using c=0.3) vs. non-robust linear approximation of neural networks corresponding to test samples of the Adult dataset. Figure (b) the empirical difference between the validity of recourses for non-robust and adversarially robust linear approximated model. Results show no violations of our theoretical bounds. See Appendix B for results using different values.
21


Reviews:
[{"review_id": "neLOk8K_xJ", "reviewer": "Reviewer_aAvX", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the cost and validity of algorithmic recourse when the model is adversarially robust. It first shows upper and lower bounds for cost and a theorem showing that the validity of non-robust model is higher than that of a robust counterpart. Then the paper shows the empirical result on three datasets, which shows the correctness of the bounds and validity theorem. ", "summary_of_the_review": "I think the major contribution of this major is not substantial given the previous paper [1], so I give a negative score at this phase.", "strength_and_weaknesses": "Strength:\n\nThe structure of the paper is clear. Both theoretical analyses and empirical study are carried out to study the connection between adversarial robustness and algorithmic recourse. \n\n\nWeaknesses:\n\nThe contribution is not significant, since the connection between adversarial robustness and algorithmic recourse has been unveiled by a previous paper [1]. It seems that this submission is a simple extension of [1]: proving the upper and lower bound for cost distance assuming a linear model and running the experiment on the same datasets. \n\nMore importantly, I cannot agree with the argument that improved adversarial robustness leads to harder recourse for a general deep neural network. If the features are disentangled and model is linear, the adversarial robustness is only related to the $l_p$ norm of weight, where $p$ depends on the attack budget norm. I guess the mentioned trade-off in this paper is related to the $l_p$ norm of weight: if the norm is large, the robustness is weak but the attack (recourse) is simple; if the norm is small, the opposite holds. But this logic is possibly not true for deep neural nets, where the features are entangled and the model is highly nonlinear. Adversarial training for a deep NN aims to purify the features so that the features are correlated with the target labels. This does not conflict with algorithmic recourse, since the adversarial robustness helps learn a meaningful feature space. If the paper only cares the simple case, please clarify it at the abstract or introduction. But if this paper only studies a simple linear model, I cannot see a major contribution here compared with [1].\n\n[1] Martin Pawelczyk, Chirag Agarwal, Shalmali Joshi, Sohini Upadhyay, and Himabindu Lakkaraju. Exploring counterfactual explanations through the lens of adversarial examples: A theoretical and empirical analysis. In International Conference on Artificial Intelligence and Statistics (AISTATS)\n\n\n1. All of the theoretical analysis seem to assume the model is a linear one. So I think there is a gap between the analysis and empirical study, where a neural network is used to show the correctness of the bound. \n\n2. Does the assumption in Theorem 3 generally hold in the real datasets?\n\n3. Some references are duplicates:\n\nMartin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. Learning model-agnostic counterfactual explanations for tabular data. In Proceedings of The Web Conference 2020 (WWW). ACM, 2020a.\n\nMartin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. Learning model-agnostic counterfactual explanations for tabular data. In Proceedings of The Web Conference 2020, pp. 3126–3132, 2020b.\n\nMartin Pawelczyk, Chirag Agarwal, Shalmali Joshi, Sohini Upadhyay, and Himabindu Lakkaraju. Exploring counterfactual explanations through the lens of adversarial examples: A theoretical and empirical analysis. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022a.\n\nMartin Pawelczyk, Chirag Agarwal, Shalmali Joshi, Sohini Upadhyay, and Himabindu Lakkaraju. Exploring counterfactual explanations through the lens of adversarial examples: A theoretical and empirical analysis. In AISTATS. PMLR, 2022b.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SUxJHx3N5n", "reviewer": "Reviewer_em4b", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Algorithmic recourse techniques search for a valid recourse in the vicinity of a point, while adversarial robustness ensures that the model outputs do not change in the vicinity of a point! Algorithmic recourse techniques for models trained to ensure adversarial robustness have a larger work to do than the non-robust counterparts. This paper aims at understanding just how difficult and different are the recourses generated for models that are adversarially robust. The authors derive theoretical (lower and upper) bounds on the differences in the reccourses generated by popular recourse generation techniques for adversarial robust models and their non-robust counterparts. These bounds are empirically tested using three datasets popular in the algorithmic recourse community.\n", "summary_of_the_review": "Overall, the authors do a thorough job of connecting two similar (yet with seemingly conflicting objectives) lines of work - algorithmic recourse and adversarial robustness. The theoretical bounds on differences in the recourses generated on models that are adversarially robust and their non-robust counterparts, and their thorough empirical validation is a good contribution to the algorithmic recourse community. \n", "strength_and_weaknesses": "Strengths\n\nIt is obvious that ensuring adversarial robustness in models will have a bearing on algorithmic recourse techniques, seemingly making it harder to find valid recourses. The paper does a good job of theoretically analyzing this aspect. It does not propose a new technique, rather analyses the impact of a model’s adversarial robustness on algorithmic recourse. The accompanying experiments are exhaustive and validate the bounds. \n\n\nWeaknesses\n\nThe authors mention that categorical features are removed for efficient training of their models. It is unclear why is this so? Excluding a certain category of features that are typical in datasets for studying algorithmic recourse is not a good idea. If the adversarial robustness algorithm cannot handle categorical features, then it is a major limitation of the analysis. \n\nThere are recourse generation techniques that are not gradient descent/ascent based and involve discrete optimization (to manage categorical attributes). A discussion on how adversarial robustness impacts these algorithms will make the paper more comprehensive. \n\nDisclaimer: I did not carefully check the proofs in the appendix. I only glanced through them.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BxBoWWZSow", "reviewer": "Reviewer_T2PC", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies whether adversarially robust models will provide algorithmic recourses with higher costs than normal models. Evidently, the prediction of adversarially robust models is more robust than normal models under input perturbations, so changing the prediction will take a higher cost. The authors present a theoretical analysis of the cost and validity difference between robust and normal models, based on linear classifiers. Both theoretical and experimental results show model robustness can harm the feasibility of algorithmic recourse.", "summary_of_the_review": "The problem studied in the paper (i.e., the trade-off between adversarial robustness and algorithmic recourse) is worth exploring. However, many assumptions used by the theoretical analysis are not explicitly stated in the lemmas and theorems. More importantly, in this paper, the metrics used by adversarial training and algorithmic recourse are inconsistent, and this inconsistency is not addressed or discussed.", "strength_and_weaknesses": "Strengths:\n\n- It is important to study the trade-off between the model's adversarial robustness and the feasibility of algorithmic recourse. Adversarial robustness pursues the cost of adversarial examples to be high, while algorithmic recourse searches low-cost modifications. There seems to be an inherent trade-off between the two goals.\n- Experiments are thorough.\n\nWeaknesses:\n\n- All of the theoretical results in the paper essentially rely on the assumption that the considered classifier is linear. This assumption is important, and thus should be explicitly stated. For example, in Definition 1, it is not enough to write \"$f(x)$ is a local linear score approximation\", in which $f(x)=w^Tx+b$ should be explicitly stated, as Pawelczyk et al did.\n- Lemma 1 and Theorem 3 also heavily rely on the assumption that the classifier is linear. The assumption should be explicitly written in the statement.\n- Moreover, Lemma 1 relies on the assumption that the adversarially robust model is trained to minimize the worst-case loss with $\\ell_{\\infty}$ norm perturbation. This assumption should also be explicitly stated in the main text.\n- Similarly, Definition 1 relies on another assumption that SCFE is generated using $\\ell_2$ norm as the distance metric. This point should also be explicitly stated. Otherwise, readers have to look for the details of this definition in Pawelczyk et al, 2022. \n- After I notice the above implicit assumption by myself, an important yet secret issue surfaced. That is, the norm used to measure adversarial robustness and the norm used to generate algorithmic recourse are not consistent. This inconsistency is unpleasant, because the norm defines what adversarial robustness really means. It would be misleading to draw rough conclusions based on the relationship between $\\ell_{\\infty}$ robustness and $\\ell_2$-based recourse. Before that, the relationship between $\\ell_{2}$ robustness and $\\ell_2$-based recourse should be studied first.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BufW4NnNg8", "reviewer": "Reviewer_G7SB", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the effect of adversarial training on the algorithmic recourse  by deriving both cost bounds and validity bounds. The correctness of the proposed bounds are verified through numerical simulation.  ", "summary_of_the_review": "Before rebuttal: Due to the comments in \"Clarity, Quality, Novelty And Reproducibility\" especially serious errors in the proof, I recommend \"Strong reject\".\n\nAfter rebuttal: The authors have conducted a careful revision and fixed a serious error in the proof. However, the novelty as well as the writing seems still not so satisfactory. As a result, I updated my score from \"1: strong reject\" to \"3: reject\".", "strength_and_weaknesses": "Strength:\n\nS1) Effects of adversarial training on algorithmic resource are analyzed by establishing bounds on the differences in cost and validity performance of the non-robust and adversarially robust models. \n\nS2) The proposed error bounds are verified by numerical experiments.\n\nWeakness: \n\nW1) The analyzed classification model $f(\\boldsymbol{x})=\\phi(h(\\boldsymbol{x}))$ seems somewhat simple, and may not well reflect the properties of modern deep models.  \n\nW2) There may be serious errors in the proof.\n\nFor example, in Page 13, the authors use the following inequations \n$$\\zeta^*_{NR}\\ge (s-\\boldsymbol{w}\\_{NR}^{T}\\boldsymbol{x} )\\frac{\\lambda}{\\lambda+1}\\boldsymbol{w}\\_{NR}$$\nand \n$$\\zeta^*_{R} \\ge  (s-\\boldsymbol{w}^{T}\\_{R}\\boldsymbol{x} )\\frac{\\lambda}{\\lambda+1}\\boldsymbol{w}\\_{R}$$\nto obtain the inequality in Line 15 as follows: \n$$\\zeta^*_{NR}-\\zeta^*_{R} \\ge \\frac{\\lambda}{\\lambda+1}\\big(  (s-\\boldsymbol{w}^{T}\\_{NR}\\boldsymbol{x} )\\boldsymbol{w}\\_{NR} - (s-\\boldsymbol{w}^{T}\\_{R}\\boldsymbol{x} )\\boldsymbol{w}\\_{R}\\big)$$\n\n\nHowever, this derivation may not be correct because we cannot directly get $a-b\\ge x-y$ from $a\\ge x$ and $b\\ge y$. Did I miss something?\n\n(After rebuttal: The authors have conducted a careful revision and fixed this serious error in the proof which of course changed the original theorem. )", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject