Coverage-Validity-Aware Algorithmic Recourse

• 成果类型: Article; Early Access
• 署名作者: Bui, Ngoc; Nguyen, Duy; Yue, Man-Chung; Nguyen, Viet Anh
• 署名单位: Yale University; University of North Carolina; University of North Carolina Chapel Hill; University of Hong Kong; Chinese University of Hong Kong
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0629
• 发表日期: 2025

摘要

Algorithmic recourse emerges as a prominent technique to promote the explainability, transparency, and ethics of machine learning models. Existing algorithmic recourse approaches often assume an invariant predictive model; however, the predictive model is usually updated on the arrival of new data. Thus, a recourse that is valid respective to the present model may become in valid for the future model. To resolve this issue, we propose a novel framework to generate a model-agnostic recourse that exhibits robustness to model shifts. Our framework first builds a coverage-validity-aware linear surrogate of the nonlinear (black box) model; then, the recourse is generated with respect to the linear surrogate. We establish a theoretical connection between our coverage-validity-aware linear surrogate and the minimax probability machines (MPMs). We then prove that by prescribing different covariance robustness, the proposed framework recovers popular regularizations for MPMs, including the & ell; 2 regularization and class reweighting. Furthermore, we show that our surrogate pushes the approximate hyperplane intuitively, facilitating not only robust but also interpretable recourses. The numerical results demonstrate the usefulness and robustness of our framework.