  Counterfactual (CF) explanations for machine learning (ML) models are
preferred by end-users, as they explain the predictions of ML models by
providing a recourse (or contrastive) case to individuals who are adversely
impacted by predicted outcomes. Existing CF explanation methods generate
recourses under the assumption that the underlying target ML model remains
stationary over time. However, due to commonly occurring distributional shifts
in training data, ML models constantly get updated in practice, which might
render previously generated recourses invalid and diminish end-users trust in
our algorithmic framework. To address this problem, we propose RoCourseNet, a
training framework that jointly optimizes predictions and recourses that are
robust to future data shifts. This work contains four key contributions: (1) We
formulate the robust recourse generation problem as a tri-level optimization
problem which consists of two sub-problems: (i) a bi-level problem that finds
the worst-case adversarial shift in the training data, and (ii) an outer
minimization problem to generate robust recourses against this worst-case
shift. (2) We leverage adversarial training to solve this tri-level
optimization problem by: (i) proposing a novel virtual data shift (VDS)
algorithm to find worst-case shifted ML models via explicitly considering the
worst-case data shift in the training dataset, and (ii) a block-wise coordinate
descent procedure to optimize for prediction and corresponding robust
recourses. (3) We evaluate RoCourseNet's performance on three real-world
datasets, and show that RoCourseNet consistently achieves more than 96% robust
validity and outperforms state-of-the-art baselines by at least 10% in
generating robust CF explanations. (4) Finally, we generalize the RoCourseNet
framework to accommodate any parametric post-hoc methods for improving robust
validity.
