Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper deals with the robustness of algorithmic recourse options given to users by common methods in the field, as models get updated over time. In particular, unlike previous works, this one proposes a solution that aspires to withstand distributional shifts in training data over time, space, correction to measurements, etc. The proposed solution, ROAR, is inspired by adversarial training. The work also introduces a lower bound on probability of invalidation of recourse options of models trained normally, as well as upper bound the added cost the output of ROAR might incur. Finally, the authors compare the performance of ROAR, as well as to a causal version of ROAR (combined with Karimi et al.'s MINT) to those of existing popular methods, and offer a sensitivity analysis, demonstrating on a synthetic dataset the effect of distributional shifts on validity of recourse options.
main_review: The paper seems overall novel to me, bearing great similarity to Rawal et al. (https://arxiv.org/abs/2012.11788v2), but being the more complete work of the two, promising greater contribution to the literature in my opinion. The proposed method and theoretical results seem like a good start to deal with the problem of algorithmic recourse and its validity over model updates.

Strengths:
1. Novel method proposed to deal with a recently identified possible concern in a relevant and impactful area of study.
2. Initial theoretical foundation proposed is interesting.

Weaknesses:
1. Choices in method and experimental setting could be discussed and justified more carefully (I'll include suggestions below). 

Questions to authors:
1. (minor) in section 2, you quickly describe your connection to other works on adversarial robustness. It seems to me Wachter et al. 2017 were of the first to mention the connection between counterfactual explanations (precursor to algorithmic recourse) and adversarial examples. Might be worth mentioning that connection briefly. 
2. (minor) line 126 - the objective function seems to directly relate to a classification setting, yet you write after it "denotes a differentiable loss function (e.g., mean squared error loss..."; why not just name binary cross entropy directly?
3. Section 3.2, choice of \Delta -- both here and in the following, the authors consider shifts in terms of *small* perturbations to parameter space or gradient of the model. What is *small* in this context? Can we bound it? what if not all shifts can be described in terms of additive perturbations of this kind? Can we demonstrate the additivity in parameters space or gradients following the shifts demonstrated in real world data in the experiment section?
4. line 165-6 - "in our framework, the perturbations are applied to model parameters as opposed to data samples". It is not immediately clear to me why one should choose to apply the perturbations in this case on the models rather than data samples. While I can see why it's reasonable, could the authors explain their choice more? I may have missed the point.
5. line 179-80 - "...when the model shifts can be characterized as additive shifts to model parameters". Similar to the question above -- can all perturbations occurring as a consequence of distribution shifts be characterized as additive shifts?
6. Section 5.1, Real world data - from the description of the SBA dataset and the student performance dataset it wasn't clear to me whether the distributional shifts as proposed would be quite enough to be called "temporal" and "geospatial" shifts, respectively. what is the temporal shift exactly for SBA? It doesn't seem like there were 2 different periods of collection, but a single continuous one? Not entirely clear to me what would be the data for M1 vs M2 without further discussion. As for the student performance dataset, are two collection points into schools in the same country reflect enough variation? Would be interesting to see what both these examples mean in terms of actual shifts occurring in model parameters/gradient, as well as in terms of variables, covariance matrices, etc. to get a better sense of what such shifts mean in practice.
7. Discussion of Karimi et al. and causal methods in the experimental section - first, the authors only compare results to MINT and MINT-ROAR for the German credit score, citing the fact that only this dataset "has an existing DAG" via Karimi et al. However, this DAG of the German credit dataset is also not official or appeared with the original dataset. It was proposed by Karimi et al. as a conjecture, which the authors of this work could have done with the other remaining dataset in this section if they wanted to achieve a more comprehensive comparison. On a related but different point, in line 344-45, the authors state "MINT and ROAR-MINT seem to exhibit highest avg costs.... likely because adhering to the causal graph incurs additional cost"; this is almost a tautological sentence, just repeating the experimental result, without attempting to provide any explanation of why that might happen. I believe one possible hypothesis could be that recommending interventions on nodes in the root or close to root nodes in a causal graph might incur additional costs to downstream features, as the effect needs to be propagated through the DAG. Non-causal methods would assume independence of features, thus no downstream propagation of intervention effects, and only "local" cost to intervened nodes would appear, although this is very likely unrealistic.

limitations_and_societal_impact: The authors did not discuss limitation of their work, or much of its societal impact. Even the proposed future work citing "tradoff between recourse robustness and cost to better understand impact..." has been already somewhat done in this work, and its sister manuscript Rawal et al. However, given that most of the work deals and is motivated clearly by societal impact of algorithmic decision-making/decision-support systems, I believe its impact in this area is overall positive.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an algorithm for the automatic generation of counterfactual examples, that are robust to a certain amount of model shift, e.g., by retraining. The probability of invalidation of counterfactuals and the cost of robust counterfactuals are analyzed theoretically and the algorithm is evaluated on 3 tabular real-world and on synthetic data sets.
main_review: The formulation of the Counterfactual problem under predictive multiplicity is already discussed in the literature (see for example Pawelcyzk). Nevertheless, the proposed method for generating robust counterfactual examples under model shift is novel, so this work advances the state-of-the-art. 

While the evaluation results show that the method leads to more robust counterfactuals, the evaluation was conducted on relatively small datasets (with 1000, 2102, 649 lines respectively). Benchmarking on a larger dataset (e.g., Give Me Some Credit, 150k lines) would additionally highlight the scalability of the method. The synthetic dataset evaluation supports the findings, but the setup is very simple. (Maybe cut the synthetic data part for more real data set experiments). 

Unfortunately, the theory part has some issues. In general, the theorems only consider very special cases (linear classifier and simple exponential-family distributions) and implications for the actual methodology are not clear. Furthermore, the interpretation of the theoretic results is missing. The derived quantities are not explained or put into context. There are some theoretical problems that should be clarified by the authors (see below). In general, even if the derivation was correct, the unintuitive condition (no interpretation given) and the appearance of the beta value (which should be optimized out), makes it hard to see the implication of Theorem 1. 

The bound in the second theorem linearly grows with the diameter of the dataset D, so the order of magnitude is the same as using a plain Lipschitz bound if c is Lipschitz-continuous. There are also some points in the derivation, which should be clarified. 

Theorem 1:
1. $x'$ is assumed independent of the decision boundary; this is not realistic.
2. What is the meaning of $\beta$? Can it be maximized?

Theorem 2:
1. $\delta$ is the worst case for each counterfactual (this is a coupled min max problem, so it is not enough to solve each problem on its own!)  which can be very different for $x'$ and $x''$. If you assume the same $\delta$ for both cases, your argument is not valid.
2. In equation 33 onwards, it should be clearly marked, that the result is only valid with probability 1-$\eta$
3. The bounds that lead to equation 34 are not valid in general. Assume a Dirac distribution (or very narrow normal distribution, i.e. around zero). Then $E_\mu[log(1+exp(-z))] = log(2)$ but $E_\mu[z]=0$


The acronym "ROAR" is already taken and might be misleading (see https://research.google/pubs/pub47088/).

In conclusion, I find the paper is well written and addresses a relevant problem, but the theory part needs further consideration before it is ready for publication.
limitations_and_societal_impact: The authors mention some limitations, e.g., higher counterfactual costs, but there could be discussion on additional limitations, e.g. that the argmax problem in Algorithm 1 may not be accurately solved in general, which may prevent convergence and on the computational cost that come with the proposed aproach or a general solution.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a method to construct recourses that are valid under worst case additive model shifts for linear models and applied to non-linear ones with LIME. The paper analyzes these robust recourses theoretically but not for the given algorithm. I think the paper overall is of great quality but it lacks in novelty in particular because of related work that shares the exact same problem formulation and experimental setup (see [25] as authors cite).  The algorithmic recourse problem is also of limited practical applicability, and thinking about robust (but much less realistic) recourses, does not help address the problems that help make algorithmic recourse more practically applicable. The proposed algorithm to solve the problem which is the main contribution of the paper is not analyzed theoretically, and empirical evidence do not discuss Theorem 2 which talks about the average cost of the recourses. 
I think the paper is borderline primarily because of how similar it is to prior work. 
main_review: Originality: The paper proposes a method to construct recourses that are valid under additive model shifts for linear models and applied to non-linear ones with LIME. The observation that recourses are invalidated with model shifts has been deeply explored in prior work that the authors reference heavily, moreover, the formulation of the problem and the experimental setup mimic exactly that of the related work [25]. Thus the main novelty here is the contribution of a method and worst-case formulation to obtain recourses. They also provide theoretical analysis for these robust recourses (but crucially not those obtained by the algorithm). I think there is limited novelty in the paper in terms of formulation and experiments and the nature of the approach, but it is an interesting combination of ideas. 

Quality: The experimental results are clear and very well compared to the baselines and well as the theoretical results are well argued for. However I have some important notes on Theorem 1 which caused a lot of confusion for me, notably how x' is sampled independently. Furthermore, I am a bit uneasy about the increase in avg cost in the experiments and the lack of experimental discussion about it. See comments below for more details. 

Clarity: The paper is very well written and easy to follow.

Significance: I think the lesson that recourses become invalidated when models change has already been discussed, so this paper tries to solve that problem with a worst case approach and propose a straightforward gradient method. I haven't seen practical uses for algorithmic recourse yet, nor are any cited (please prove me wrong on this point if I am mistaken). So deriving robust recourses with this approach that has no stated guarantees does not address practical or theoretical challenges that need to be solved first. I am not convinced from the point of average cost that the robustness guaranteed is worth future validity, from the empirical point of view, from the theoretical perspective Th2 is a nice guarantee. The empirical setup is also borrowed from prior work, so that researchers can look at older papers for this kind of setup. 

Limitations: 1) no guarantees on algorithm, 2) no empirical discussion of Theorem 2 and the increase in average cost, 3) limited form of model shifts that apply only to linear models. 

Comments:

Extension to multiclass? 

Can we define recourses in terms of probabilistic model? I.e. a recourse of \delta is that that increases the probability of a positive outcome by \delta, or sequential recourses that can be thought of as a curriculum for the individual.  That I think is a much more useful practical definition.

Supposedly as designers we control the model and have historical data on our users and recourses, why not update the model constrained by the fact that old recourses must still hold? This is arguably a cleaner approach that avoids worst case thinking. However, it makes a further assumption that we control the model, but this is reasonable in a lot of settings.

The choice of delta: clear typo of using n in definition? It is not written elsewhere that M’s weights are a single vector in R^p. The shifts are very limited, even for linear models, I would at least expect \delta_{min} and \delta_{max} to depend on each feature, is that extension easy to do? 

There is a big assumption of approximating a non-linear model by a linear one locally, I am not sure how much weight I put on the validity of LIME explanations. 

Algorithm 1 is an algorithm on the individual level, and so can be run independently which is nice.

In theorem 1, I don't understand what does it mean for x’ to lie on the original data manifold. In parentheses it is written that x’ is sampled from a normal distribution, the same as that of x, is that sampling independent? If so, then it is not possible that x’ is a recourse as x’ is only a function of x (which can be random, but the theorem says “THE” recourse which implies it is a deterministic map to add to the confusion). In the proof it is not clear how x’ is initially obtained, because if x’ is a recourse then it is a given that w^Tx’ >0! But you add that as a condition in \omega.  

There is no analysis to the performance of the given algorithm, as section 4 assumes to be able to fully solve the optimization problem. I would like to see some argumentation for why the algorithm performs well theoretically.

In table 1, M1 and M2 validity results are very promising, but the lack of discussion on what does the increase in average costs imply is a bit unsettling. I would have liked to see in the experiments what is the lower limit on costs to achieve this high of M1&M2 validity, without context, I am unsure how bad the increase in avg cost is. Figure 2 helps tell me that the increase in avg cost is not too high because with a mean shift of 1, validity becomes very low, so that x’ was not on the extremes. I would have liked to see visual examples in the synth setting of original points x and recourses x’ for the different methods to understand what is happening. 


---------------- 
Post response: I have read the authors response, the authors have given good responses to some of the concerns I had, my recommendation however remains a weak accept 
limitations_and_societal_impact: There is limited discussion to how realistic the recourses suggested in the paper can be applied in practice. There is limited proof that if we take a recourse from any of the datasets, then that recourse establishes a route for an individual to change their discussion, or how can they accomplish that change.
review_title: null

Meta-review: The expert reviewers for the most part appreciated the paper and were largely positive. There were many important issues raised but the reviewers felt the authors responded appropriately and suggested a reasonable path to addressing these within the scope of this review process. The authors are expected to carefully address the points raised by reviewers in a final version, including as they outlined in their response. This includes the points raised by about the theory and assumptions as well as justifying choices in the model -- the answers from the reviewers were adequate and they need to be incorporated into the paper.
Decision: Accept (Poster)