  Counterfactual explanations (CEs) enhance the interpretability of machine
learning models by describing what changes to an input are necessary to change
its prediction to a desired class. These explanations are commonly used to
guide users' actions, e.g., by describing how a user whose loan application was
denied can be approved for a loan in the future. Existing approaches generate
CEs by focusing on a single, fixed model, and do not provide any formal
guarantees on the CEs' future validity. When models are updated periodically to
account for data shift, if the generated CEs are not robust to the shifts,
users' actions may no longer have the desired impacts on their predictions.
This paper introduces VeriTraCER, an approach that jointly trains a classifier
and an explainer to explicitly consider the robustness of the generated CEs to
small model shifts. VeriTraCER optimizes over a carefully designed loss
function that ensures the verifiable robustness of CEs to local model updates,
thus providing deterministic guarantees to CE validity. Our empirical
evaluation demonstrates that VeriTraCER generates CEs that (1) are verifiably
robust to small model updates and (2) display competitive robustness to
state-of-the-art approaches in handling empirical model updates including
random initialization, leave-one-out, and distribution shifts.
