From Search to Sampling: Generative Models for Robust Algorithmic Recourse
Prateek Garg, Lokesh Nagalapatti, Sunita Sarawagi · 2025
Read From Search to Sampling: Generative Models for Robust Algorithmic Recourse by Prateek Garg, Lokesh Nagalapatti, Sunita Sarawagi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-07351.txt.
Introduction
Garg, Nagalapatti, and Sarawagi build fixes for folks turned down by a model's call in this twenty twenty-five paper. A good fix must be near, real, and sure to flip the call to yes. Past tools train for each aim apart, then hunt a fix at use time.
Inside, their tool is a breed net that trains on all three aims at once as one task. Fake drill pairs stand in for the true fix marks that no set holds. At use time the net just draws a fix in one pass, with no hunt step. That one-pass draw beat top kin tools on cost, real feel, and flip rate. Trade-offs among the three aims also came out best in the new tool.
Catalog record
| CREATOR | Prateek Garg, Lokesh Nagalapatti, Sunita Sarawagi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-07351
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
From Search to Sampling: Generative Models for Robust Algorithmic Recourse Prateek Garg, Lokesh Nagalapatti, Sunita Sarawagi Abstract Algorithmic Recourse provides recommendations to individuals who are adversely impacted by automated model decisions, on how to alter their profiles to achieve a favorable outcome. Effective recourse methods must balance three conflicting goals: proximity to the original profile to minimize cost, plausibility for realistic recourse, and validity to ensure the desired outcome. We show that existing methods train for these objectives separately and then search for recourse through a joint optimization over the recourse goals during inference, leading to poor recourse recommendations. We introduce GenRe, a generative recourse model designed to train the three recourse objectives jointly. Training such generative models is non-trivial due to lack of direct recourse supervision. We propose efficient ways to synthesize such supervision and further show that GenRe’s training leads to a consistent estimator. Unlike most prior methods, that employ non-robust gradient descent based search during inference, GenRe simply performs a forward sampling over the generative model to produce minimum cost recourse, leading to superior performance across multiple metrics. We also demonstrate GenRe provides the best trade-off between cost, plausibility and validity, compared to state-of-art baselines. Our code is available at: https://github.com/prateekgargx/genre . 1 Introduction Machine learning models are increasingly used in high-stakes decision-making areas such as in finance ( Josyula et al. 2024 ) , judiciary ( Elyounes 2019 ) , healthcare ( Burger 2020 ) , and hiring ( Schumann et al. 2020 ) , prompting the need for transparency and fairness in decision-making ( Barocas et al. 2023 ) . This has driven the development of tools and techniques to provide recourse , redress mechanisms for individuals adversely impacted by these model decisions, a legal requirement in certain jurisdictions ( Kaminski 2019 ) . For example, consider a loan applicant with profile {\bm{x}} who is denied loan. Recourse seeks to answer the question, ‘How should {\bm{x}} improve their profile to an alternative {\bm{x}}^{+} to secure a loan in the future?’ . A good recourse instance {\bm{x}}^{+} should be (1) valid, i.e., it achieves the desired label, (2) proximal to {\bm{x}} to minimize the effort involved in implementing recourse, and (3) be a plausible member of the desired class. The decision-making model is often proprietary and is kept hidden to safeguard enterprises from strategic gaming ( Hardt et al. 2016 ) , model theft ( Reith et al. 2019 ) , and other risks. We are given instead examples of individuals who got the desired label (positive instances), and those who did not (negative instances). Our goal is to learn a recourse mechanism using just these samples. The recourse problem has been widely explored under frameworks like algorithmic recourse ( Ustun et al. 2019 ) , counterfactual explanations ( Wachter et al. 2017 ) , and contrastive explanations ( Karimi et al. 2022 ) . Most prior work assume direct access to the decision-making model, and search for the recourse instance through constrained optimization during inference on objectives which encourage low cost and validity ( Karimi et al. 2022 ; Wachter et al. 2017 ; Mothilal et al. 2020 ; Laugel et al. 2017 ) . Others aim for robust recourse by searching for an {\bm{x}}^{+} that remains valid under small changes to either the model or to the proposed {\bm{x}}^{+} itself ( Pawelczyk et al. 2020b ; Rawal et al. 2020 ) . The plausibility criterion is often overlooked, and some methods propose to address it by training generative models ( Joshi et al. 2019 ; Pawelczyk et al. 2020a ; Downs et al. 2020 ) . Most recently, Friedbaum et al. 2024 attempts to increase the validity of {\bm{x}}^{+} by including a separate verifier model that checks whether ({\bm{x}},{\bm{x}}^{+}) belong to different classes after the optimizer generates a candidate {\bm{x}}^{+} . One significant limitation of all prior methods is that none of them are trained to jointly optimize the three conflicting recourse criteria of validity, proximity, and plausibility. Instead, during inference, they either ignore some recourse objectives or rely on non-robust gradient-based search on the joint objective to balance the trade-offs between them. We show in Figure 2 that this disconnect between training and inference leads to poor recourse outputs. In a significant departure from the existing paradigms, we take a generative approach to recourse. We train a novel recourse likelihood model \mathcal{R}_{\theta}({\bm{x}}^{+}|{\bm{x}}) , that when conditioned on any instance {\bm{x}} seeking recourse, outputs a distribution over likely recourse instances. Using such a model during inference, we just forward sample recourse instances, unlike existing methods that perform gradient descent optimization to find one {\bm{x}}^{+} . However, to train such a model we would need several instance pairs {( {\bm{x}}_{i},{\bm{x}}^{\prime}_{i}):i=1\ldots N )} where {\bm{x}}^{\prime}_{i} is a good recourse for any {\bm{x}}_{i} with an unfavorable outcome. Such direct supervision is lacking. We show how to leverage standard unpaired classification data to sample a training set of instance pairs. We theoretically show that the sampled pairs are consistent, and the error of the expected recourse instance converges at the rate \mathcal{O}(1/N_{+}) where N_{+} denotes the number of instances in the positive class. In terms of empirical validation, we first present a visual demonstration of the pros and cons of various methods using three 2-D datasets. We then evaluate on three large real-life datasets that are popularly used in the recourse literature and compare our results with eight existing methods. We show that our method achieves (1) the best score combining validity, proximity and plausibility, (2) is more robust to changes in the cost magnitude compared to SOTA likelihood-based methods, and (3) more faithfully learns the conditional density of recourse than methods that separately learn unconditional data density. 2 Problem Formulation Let {\mathcal{X}}\subseteq{\mathbb{R}}^{d} represent the input space and {\mathcal{Y}}=\{0,1\} the output space where the joint distribution between them is P(X,Y) . In the recourse task, one label, say 0 is an unfavorable outcome (e.g., loan rejection) and the other label {y^{+}}=1 denotes a favorable one (e.g., loan approval). We are given a training dataset of n instances {\mathcal{D}}=\{({\bm{x}}_{i},y_{i})\}_{i=1}^{n} sampled i.i.d. from P(X,Y) . We use {\mathcal{D}_{1}} and {\mathcal{D}_{0}} to denote the subset of {\mathcal{D}} with label 1 and 0 respectively. We assume that we have a pretrained classifier h:{\mathcal{X}}\mapsto[0,1] trained on the available dataset {\mathcal{D}} , serves as an approximation for P(Y=1|X) . Given an instance {\bm{x}}\sim P(X) , recourse is sought on instances where h({\bm{x}})<0.5 . Our objective is to design a mechanism, \psi:{\mathcal{X}}\mapsto{\mathcal{X}} , that outputs a recourse instance {\bm{x}}^{+} such that P({y^{+}}|{\bm{x}}^{+})>0.5 , while minimizing the cost of shifting {\bm{x}}^{+} measured in terms of a cost function C:{\mathcal{X}}\times{\mathcal{X}}\mapsto{\mathbb{R}}^{+} . \ell_{1} distance is a popular choice for C . Additionally, the recourse instance {\bm{x}}^{+} should be representative in the desired class distribution P(X|{y^{+}}) , and not an outlier. In real-life applications, weird unrepresentative profiles may not be achievable, and mislead the purpose of recourse. For instance, in domains such as banking, ensuring high P({\bm{x}}^{+}|{y^{+}}) is important because an user should not be gaming the system to get loan approval. Figure 1: The recourse pipeline starts with any instance {\bm{x}} that received an unfavorable label h({\bm{x}})=y^{-} . The recourse mechanism outputs an alternative {\bm{x}}^{+} such that h({\bm{x}}^{+})=y^{+}