Logo image
Back
Optimal Robust Recourse with Lp-Bounded Model Change
Journal article

Optimal Robust Recourse with Lp-Bounded Model Change

Phone Myat Kyaw, Kshitij Kayastha and Shahin Jabbari
2026 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)
22 Sep 2026
DOI: https://doi.org/10.1109/SaTML68715.2026.00025

Abstract

Recourse provides individuals who received undesirable labels (e.g., denied a loan) from algorithmic decision-making systems with a minimum-cost improvement suggestion to achieve the desired outcome. However, in practice, models often get updated to reflect changes in the data distribution or environment, invalidating the recourse recommendations (i.e., following the recourse will not lead to the desirable outcome). The robust recourse literature addresses this issue by providing a framework for computing recourses whose validity is resilient to slight changes in the model. However, since the optimization problem of computing robust recourse is non-convex (even for linear models), most of the current approaches do not have any theoretical guarantee on the optimality of the recourse. Recent work by Kayastha et al. [32] provides the first provably optimal algorithm for robust recourse with respect to generalized linear models when the model changes are measured using the L∞ norm. However, using the L∞ norm can lead to recourse solutions with a high price. To address this shortcoming, we consider more constrained model changes defined by the Lp norm, where p ≥ 1 but p ≠ ∞, and provide a new algorithm that provably computes the optimal robust recourse for generalized linear models. Empirically, for both linear and non-linear models, we demonstrate that our algorithm achieves a significantly lower price of recourse (up to several orders of magnitude) compared to prior work and also exhibits a better trade-off between the implementation cost of recourse and its validity. Our empirical analysis also illustrates that our approach provides more sparse recourses compared to prior work and remains resilient to post-processing approaches that guarantee feasibility.

Metrics

1 Record Views

Details

Logo image