Robust Algorithmic Recourse Design Under Model Shifts

Reply for weaknesses 1 and 2:

1. Novelty and Importance: We appreciate your concern about the novelty and importance of our work, and we would like to emphasize several key points to clarify the significance of our contribution. Firstly, our research uniquely addresses the challenge of modeling recourse invalidation rates under potential model shifts in dynamic decision systems. This specific focus, along with our comprehensive analysis, differentiates our work from prior studies in the field. Secondly, we derive theoretical upper bounds on the recourse invalidation rate. Our approach, tailored to model updates, stands out for its cost-efficiency compared to other methods. Importantly, our paper introduces a novel framework that empowers users to set their desired recourse invalidation rate. This user-centric design allows for the creation of tailored recourses that meet specific invalidation criteria, addressing a key aspect of efficiency in recourse design.

2. Theoretical Analysis: We appreciate the reviewer's suggestion for additional theoretical clarification regarding efficiency and robustness. Here is how our paper addresses these aspects:

   (1) Robustness with Model Shifts: Throughout the paper, especially in Section 4, we derive theoretical results that specifically characterize the recourse invalidation rate under potential model shifts. This analysis offers valuable insights into how our method is designed to maintain robustness when confronted with changes in the underlying model, effectively addressing the reviewer's concern about robustness.

   (2) Efficiency Considerations: While our primary focus in this paper is on robustness, we acknowledge the importance of efficiency. We provide a foundation for exploring trade-offs between cost-efficiency and robustness within the context of dynamic decision systems. For the presented work, the efficiency of our proposed algorithm is characterized by its ability to allow users to specify the recourse invalidation rate and to design recourses that achieve this rate. This flexibility and adaptability in recourse design represent a significant advancement in the field. Although we do not extensively delve into efficiency concerns theoretically, we recognize it as a crucial area for future research and intend to investigate it further.

Reply for weakness 3: Our definition of robustness is focused on the variation of predictors. This is based on the premise that in dynamic decision systems, model shifts-such as updates or changes in data distributions-are common. Our approach quantifies robustness by measuring how well recourses adapt to these shifts in predictors. We believe this is a crucial aspect in predictive modeling, especially given the prevalence of model updates in practice.

We appreciate the reviewer's suggestion to consider more sophisticated description of how the data changes, and to bring LLM into the discussion. These considerations will be very valuable and will be one of our future research directions.

Dear reviewer LkRN,

Thank you for dedicating your time to reviewing our manuscript. Your insights have been invaluable, and we've crafted a detailed response to address the points you raised and polish the paper accordingly. We're confident that our responses and modifications have effectively addressed your concerns. With these changes in mind, we hope you might reconsider and adjust your evaluation of our work.

Should there be any remaining issues, we're more than ready to provide further clarifications. As the rebuttal phase is nearing its deadline, we're looking forward to engaging in a timely discussion. Thank you again for your expertise and guidance!

Reply for weakness 1: The main contributions of this paper are summarized as:

(1) Characterization of Recourse Invalidation Rate: We introduce a novel approach to characterize the recourse invalidation rate in the context of potential model shifts. This characterization is crucial in dynamic systems where models are frequently updated or where data distributions change over time.

(2) Model-Agnostic Recourse Framework: We develop a model-agnostic framework for generating recourses. This framework allows for recourses that are adaptable to changes in the model, thereby maintaining their effectiveness over time.

(3) Recourse In validation Estimation: In Section 4, we propose a method for uncertainty quantification that calculates a theoretical upper bound for the recourse invalidation rate. This method is applicable to any counterfactual plan and prediction model, enhancing its utility across various scenarios.

(4) Cost-Efficiency and Robustness Trade-off: In Section 5, we tackle the crucial trade-off between cost-efficiency and robustness in the design of recourses. Utilizing the derived bounds on the recourse invalidation rate, our method empowers users to tailor this trade-off to meet their specific needs.

(5) Practical Implications: We present numerical results using multiple datasets to validate the effectiveness of our theoretical bounds and the efficiency of our proposed algorithms. These results underscore the practical applicability of our research in real-world settings.

We have included this summary of contributions in the introduction section of our revised paper to provide a clear overview of our research's impact and significance in the field.

Reply for weakness 2: We acknowledge the reviewer's point that simply having access to the training dataset ($D_{\text{train}}$) and calibration dataset ($D_{\text{calib}}$) does not inherently solve the problem of distributional shifts in the data. However, they are instrumental in our approach for quantifying the effects of model shifts on the validity of algorithmic recourse. Specifically, the theoretical bounds on recourse invalidation rates in our model are based on the assumption that the difference in the scoring function values is bounded before and after the model shifts. To convert this perturbation into quantifiable recourse invalidation rates, $D_{\text{train}}$ is utilized to derive upper and lower bounds on the likelihood ratio between $P$ and $P'$. The calibration dataset $D_{\text{calib}}$ is then employed to assess the nonconformity of $s'({x}^{\text{CF}},1)$ in the context of the updated model. This step is crucial to understand how ${x}^{\text{CF}}$ with a positive result in the updated model may appear anomalous compared to the patterns in $D_{\text{calib}}$. Through this process, we can establish both lower and upper bounds on the coverage probability of $s'({x}^{\text{CF}},{y}^{\text{CF}})$. These bounds are integral to determining the theoretical limits on the recourse invalidation rate under model shifts.

Reply for weakness 3: Recall that $P$ and $P'$ represent the distributions for the nonconformity random variable $S$, which takes values between 0 and 1. The nonconformity score function value is either $h({x})$ or $1 - h({x})$, resulting in a concentrated distribution of the random variable $S$ for a given dataset. The concentration of the density of $S$ depends on the model's predictive performance on the specific dataset. In regions where the density is sparse, the value of $\hat{L}(s)$ approaches 1. Conversely, in areas where the density is high, employing $\hat{L}(s) = \frac{\epsilon}{\hat{p}(s)}$ with the empirical probability mass function (PMF) $\hat{p}$ might result in a significantly smaller value of $\hat{L}(s)$. For $\hat{U}(s)$, given that the value of $\tau$ is small, its value exceeds 1 but remains within a reasonable range. Furthermore, in numerical examples, to mitigate extreme values of $\hat{L}$, we don't examine each possible value of $s$ in isolation. Instead, we divide the range $[0, 1]$ into multiple bins, calculate the probability mass in each bin, and use this as $\hat{p}$ for calculating $\hat{L}$ and $\hat{U}$. This approach ensures that the ratio between $\hat{U}$ and $\hat{L}$ typically remains below 10 for all $s$, making these bounds both practical and informative. The construction details of $\hat{L}$ and $\hat{U}$ have been moved from the main context to Appendix B. Additionally, the discussion mentioned above has been included in the appendix for comprehensive reference.

Reply for weakness 4: In our approach, we utilize two datasets: $D_{\text{train}}$ and $D_{\text{calib}}$. It's important to note that both of these datasets are typically collected before the model is deployed in a real-world scenario. These datasets are an integral part of the standard machine learning pipeline. Given that the data required for deriving the upper bound on the recourse invalidation rate is essentially the same data used for model training, we believe that our approach does not introduce additional privacy concerns beyond those already associated with typical machine learning practices. As such, we did not explicitly discuss privacy concerns in our paper. However, we understand the importance of privacy in machine learning applications. If you have any specific privacy-related questions or concerns about our method that you would like us to address, please feel free to provide more details, and we would be happy to provide further clarification.

Reply for weakness 5: Section 4 is mainly about the theoretical analysis on the recourse invalidation rate. We have worked to enhance the coherence of the section by providing clearer connections between each lemma, proposition, and theorem. We have also revised the writing of Section 4 to make the concepts more understandable by the readers.

Reply for weakness 6: We appreciate the opportunity to discuss the performance of our proposed method, PiRR, in comparison to DiRRAc. In our numerical experiments, PiRR demonstrates notable improvements over DiRRAc in certain instances. For example, on the Criminal Justice dataset, PiRR (with a parameter setting of 0.05) achieves a significantly lower average cost than DiRRAc. Moreover, in the Student Performance dataset, while PiRR and DiRRAc show similar mean recourse invalidation rates, PiRR (0.05) presents a substantially smaller variance in the invalidation rate, indicating more consistent performance. Additionally, it achieves this with a lower average cost, suggesting an overall better trade-off between effectiveness and efficiency.

Moreover, it's crucial to note that the primary contribution of our paper extends beyond designing a new algorithm for generating robust recourses. We aim to address the critical real-world problem of characterizing the recourse invalidation rate under potential model shifts. This issue is important in practical applications where model updates and distributional shifts are common. As such, this paper provides valuable insights into the behavior of recourse methods in dynamic settings, which goes beyond the scope of algorithmic performance comparisons. Furthermore, we acknowledge that there is room for improvement in designing robust recourses by potentially combining our method with other techniques in the recourse design stage. This flexibility allows us to explore opportunities for achieving even better performance in real-world scenarios.

Reply for questions: We appreciate the reviewer's suggestion for a seemingly simpler three-step approach involving empirical score values, kernel density estimators, and robust formulation via perturbation. However, there are several considerations that make this approach challenging in the context of our research. Firstly, careful consideration is required in constructing a kernel density estimator, particularly in terms of selecting the right kernel and bandwidth. These choices can have substantial effects on the performance and interpretability of the estimator. Secondly, the selection of an appropriate divergence metric for perturbing the kernel density estimator is crucial and non-trivial. This choice significantly influences the resultant robustness and associated costs of the recourses. For model changes, characterizing an appropriate divergence or variation metric that accurately reflects the nature of the model shifts is complex. Furthermore, our work primarily addresses the intricacies associated with model shifts. These shifts can be multifaceted and may not be adequately captured by straightforward perturbations in a kernel density estimator. While we acknowledge the potential benefits of a more interpretable and straightforward approach as you suggested, our method was designed to specifically address the nuanced challenges presented by model shifts. Nevertheless, we find the proposed three-step procedure intriguing and see it as a valuable avenue for future research. Exploring this method could potentially complement our current work and contribute to the broader understanding of robust recourse design under model shifts.

Dear reviewer rDRT,

Thank you for dedicating your time to reviewing our manuscript. Your insights have been invaluable, and we've crafted a detailed response to address the points you raised and polish the paper accordingly. We're confident that our responses and modifications have effectively addressed your concerns. With these changes in mind, we hope you might reconsider and adjust your evaluation of our work.

Should there be any remaining issues, we're more than ready to provide further clarifications. As the rebuttal phase is nearing its deadline, we're looking forward to engaging in a timely discussion. Thank you again for your expertise and guidance!

Reply for weakness 1: We have revised the writing of Section 4 to make the concepts more understandable by the readers. In Section 4, since we have proposed an assumption and derived theoretical results based on such assumption, we compare the applying scenario of the proposed methods and also compare the bounds with other related methods. However, it is also a good idea to include these comparisons in Section 2.

Reply for weakness 2: We appreciate the reviewer's concern regarding the absence of theoretical performance guarantees and specified runtime for Algorithm 2. The minimization problem defined in (1) is inherently non-convex with multiple constraints, which presents significant challenges in solving it exactly. Non-convex problems, by their nature, are known for potential local minima, making it difficult to guarantee global optimality. In the paper, we transform the initial optimization problem to a format represented by (2), which seems more tractable and inspires the use of the Alternating Direction Method of Multipliers (ADMM) for solving the optimization problem. While ADMM is a powerful tool for certain types of optimization problems, demonstrating its convergence for multi-block problems, like the one we address, is exceptionally challenging. In the ADMM literature, although convergence rates are characterized for simpler structured problems, the generalization to more complex, multi-variable problems introduces significant complications. Not only is proving convergence itself difficult, but also characterizing the convergence rate in such scenarios is even more daunting.

Reply for question 1: The runtime of Algorithm 1 in our study is closely tied to the computational complexity of the processes involved, which depends on the number of samples in the training and calibration datasets. Suppose that there are $N$ samples in $D_{\text{train}}$ and $n$ samples in $D_{\text{calib}}$. Initially, Algorithm 1 iterates over all $N$ samples in $D_{\text{train}}$ to construct the point-wise bounds $\hat{L}(\cdot)$ and $\hat{U}(\cdot)$. For each of the $n$ samples in $D_{\text{calib}}$, the algorithm computes values $S_i, L_i, U_i$. For $k$ from $1$ to $n$, the algorithm performs computations for $\hat{F}(k)$. Considering these steps, the total computational complexity of Algorithm 1 can be approximated as $O(N+n)$. This linear complexity suggests that the runtime will scale proportionally with the total number of samples in datasets. In practical terms, the runtime typically spans several minutes, depending on the specific sizes of $N$ and $n$.

Reply for question 2: The runtime of Algorithm 2 is influenced by several factors due to the nature of ADMM, which updates one variable at a time while keeping others constant. These factors include: initial point, dataset structure, penalty constant, model and model shift variables, etc. In particular, the convergence speed of ADMM heavily relies on the initial point. A starting point that is closer to the optimal solution can significantly reduce the convergence time, thus shortening the overall runtime of the algorithm. Moreover, the choice of the penalty constant in ADMM is crucial. An optimal penalty constant can facilitate quicker convergence, while other choices may lead to slower convergence rates. Furthermore, the variables associated with the predictive model and model shifts, such as the type of predictive model and parameters defining the model shifts, affect the algorithm's efficiency. These elements determine the complexity of the problem that ADMM needs to navigate, impacting the runtime. In our experimental observations, the runtime for Algorithm 2 varied between 5 to 60 minutes.

Reply for question 3: Please refer to our response for weakness 2.

Dear reviewer NqmB,

Thank you for dedicating your time to reviewing our manuscript. Your insights have been invaluable, and we've crafted a detailed response to address the points you raised and polish the paper accordingly. We're confident that our responses and modifications have effectively addressed your concerns. With these changes in mind, we hope you might reconsider and adjust your evaluation of our work.

Should there be any remaining issues, we're more than ready to provide further clarifications. As the rebuttal phase is nearing its deadline, we're looking forward to engaging in a timely discussion. Thank you again for your expertise and guidance!

Reply for question 1: Thank you for raising the question regarding Assumption 3 and its practical applicability. In our theoretical framework, Assumption 3 serves as a guideline rather than a strict requirement for all practical applications. Specifically, for a counterfactual example ${x}^{\text{CF}}$, it is not necessary that the difference between the scoring functions before and after a model shift is smaller than $\tau$ for every sample. Instead, the more practical condition we use is: $\mathbb{P}(h'({x}^\text{CF})\geq \eta-\tau \vert (h'({x}^\text{CF})\geq \eta)=1.$ This condition reflects a more realistic scenario where the bound $\tau$ serves as a probabilistic rather than an absolute constraint.

Our decision to introduce Assumption 3 is based on common occurrences in dynamic decision systems, such as model updates or changes in data distribution. We recognize that these shifts are typically not extreme, hence the theoretical assumption that perturbations are bounded by $\tau$.

While our theoretical model assumes bounded perturbations for simplicity and tractability, we acknowledge the complexities of real-world data and model shifts. In light of this, one of our key future research directions is to relax this assumption, allowing for a broader range of perturbations. By loosening this assumption, we aim to further bridge the gap between theoretical robustness and the practical variability encountered in real-world applications.

Reply for question 2: Theorem 12 (Theorem 11 in the revised paper) derives its upper bound from the inequality presented in Proposition 8 (Proposition 7 in the revised paper), which characterizes the lower bound of the coverage probability. This approach offers a simpler and computationally more efficient solution, as it involves only the computation of $\hat{L}(S)$. The simplicity and lower computational demand make Theorem 12 (Theorem 11 in the revised paper) particularly useful in scenarios where computational efficiency is a priority, even though it might offer a less tight bound compared to Theorem 13 (Theorem 12 in the revised paper).

Conversely, Theorem 13 (Theorem 12 in the revised paper) provides a tighter bound by integrating both inequalities from Propositions 8 and 10 (Propositions 7 and 9 in the revised paper), utilizing the lower and upper bounds on the coverage probability. This results in a tighter upper bound on the recourse invalidation rate. However, this increased precision comes at the cost of higher computational complexity, as it requires calculating both $\hat{L}(S)$ and $\hat{U}(S)$. Additionally, deriving $k^*$ from Proposition 8 (Proposition 7 in the revised paper) or $t^*$ from Proposition 9 (Proposition 8 in the revised paper) requires multiple evaluations of $\hat{F}(k)$ and $\hat{E}(t)$, respectively, for different values, roughly doubling the computational resources compared to Theorem 12 (Theorem 11 in the revised paper). Thus, Theorem 13 (Theorem 12 in the revised paper) is more appropriate in situations where the accuracy of the bound is a critical factor, despite the higher computational cost.

In our numerical examples, we observed that the performance difference between the bounds derived from Theorems 12 and 13 (Theorems 11 and 12 in the revised paper) is relatively minor. Therefore, we have included results from both theorems to offer readers a choice. This inclusion allows practitioners and researchers to select the theorem that best aligns with their specific needs regarding accuracy and computational resources.

Reply for question 3: (Nguyen et al., 2022) introduces a unique Bayesian recourse framework that focuses on minimizing the odds ratio between posterior probabilities of different outcomes. This approach, termed Bayesian recourse, diverges from the more general setting of ensuring a positive prediction result for generated recourses. Moreover, their robustification process involves smoothing samples and solving a min-max optimization problem within a Wasserstein-Gaussian mixture conditional ambiguity set. This specific approach to robustness, centered around a minimax problem, is quite distinct from the methods employed in our work. Given the unique and non-generalizable aspects of Nguyen et al.'s definition of Bayesian recourse and their specific robustification technique, we chose not to include a comparison with their method in our initial paper. However, we acknowledge the relevance of their work and are open to incorporating a comparative analysis in the revised version of our paper.

Reply for question 4: Thank you for bringing the reference update to our attention. We have revised the reference in our paper accordingly.

Reply for question 5: Thanks for pointing out these robust recourse baselines. We have included them in our revised paper.

Reply for weakness 1: Thanks for pointing this out. We have updated the citing style in the revised paper.

Reply for weakness 2: We appreciate the reviewer's concern regarding the absence of a traditional cost-validity trade-off performance evaluation for PiRR in our paper. The main focus of our work is on analyzing the impact of potential model shifts and designing model-agnostic recourses that can maintain their effectiveness in the face of future model changes. In light of this primary objective, we chose to prioritize the evaluation under model shift scenarios rather than the conventional cost-validity trade-off performance. Moreover, in conventional settings, many existing methods, including PiRR, can achieve near-perfect performance, as indicated in Table 2 and Table 8, column ``Invalidation rate before shift". In such cases, the differences between various methods, including PiRR and others, are marginal. Focusing on these conventional settings may not effectively highlight the advantages of PiRR. Given the marginal differences in performance under traditional settings, we believed that an evaluation focusing on these aspects would not adequately highlight the unique strengths of PiRR, especially in the context of model shifts. Therefore, our evaluation strategy was specifically designed to emphasize PiRR's performance in response to updated models, which we consider to be a more critical and challenging aspect of recourse design in dynamic environments.

Reply for weakness 3: Thank you for your feedback on Section 4. We have worked to enhance the coherence of the section by providing clearer connections between each lemma, proposition, and theorem. We have also revised the writing of Section 4 to make the concepts more understandable by the readers.

Dear reviewer C8WR,

Thank you for dedicating your time to reviewing our manuscript. Your insights have been invaluable, and we've crafted a detailed response to address the points you raised and polish the paper accordingly. We're confident that our responses and modifications have effectively addressed your concerns. With these changes in mind, we hope you might reconsider and adjust your evaluation of our work.

Should there be any remaining issues, we're more than ready to provide further clarifications. As the rebuttal phase is nearing its deadline, we're looking forward to engaging in a timely discussion. Thank you again for your expertise and guidance!