Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper focuses on detecting "individual unfairness" in supervised learning.

The main contributions are:
1.  A method to generate "adversarial" examples, that is, the examples that are very close to the original input, but get a very different outcome. An optimization problem is used formulated by leveraging the DRO framework. The authors then point out the difficulty in solving the problem (specially with continuous features) and propose an ODE based solution to find the adversarial examples.
2. After finding the adversarial examples, a hypothesis testing framework is proposed to test the model for individual unfairness. The main idea here to compute the mean and variance of the test statistic on a given set of data points and then construct the confidence intervals using the Normality assumption.

On a high level, the idea of testing for individual unfairness is an interesting one, specially given that there aren't many metrics of it individual unfairness out there. However, it feels like many important design choices are not very clear. For these reasons, this reviewer is split between a weak accept and a weak reject. See the detailed comments below:

1. Intuitively, it seems like the need for hypothesis testing arises when one is working with a small test set (if the test set is large enough, then assuming IID samples, one could already be quite confident of the point estimate of the amount of individual unfairness as measured in Eq. 3.2). However, the paper then assumes that the distance metric is learnt from the test set. Now if the test set is already quite small, how good a metric do we expect to learn? It is not clear how to reconcile these two problems. 

2. How much "interpretability" does the hypothesis test really add? The test statistic does really provide a whole lot more interpretability on on top of the quantity measured in Eq. 3.2 (which itself it very closely related to that in Eq. 2.4). Essentially, the main insight seems to be to monitor the change in loss from an example to an adversarial version of it. So that additional benefit does the hypothesis testing bring here, specially when working with reasonably sized test sets (also, see the point about the need for hypothesis testing above)? Given that the paper does not offer any discussion into the tradeoff between type I and II errors, it is not clear that advantages does the hypothesis testing bring for us.

3. Perhaps it would be worth discussing how the scale of the loss (<<0) might make the ratio in Eq. 3.2 unstable in practice.

4. This reviewer is a bit confused about the Normality result derived in Theorem 3.1. True that the distribution here tends to a Normal when $n \to \infty$. However, with small test sets, how well does this assumption hold? If it does not, the interval constructed in Eq. 3.6 may not be very accurate. In general, an empirical analysis of the intervals as in (https://arxiv.org/pdf/2007.05124.pdf) would be a great addition to the paper.

5. The paper seems to take the assumption that the distance metric specified by the user is differentiable (for solving the problem in Section 2). Is that true? It is quite possible for domain experts to specify distance metrics with discontinuities in them (e.g., if education level of x1 is higher than education level of x2, upweigh the distance by 1). Can such user-specified metrics be handled by the methods in the paper?

6. This reviewer is not very sure about the usage of four-fifth rule for the hypothesis test. While I am not a legal expert, the four-fifth rule seems to apply to groups instead of individuals as suggested by the paper. Moreover, applying the four-fifth rule on well-understood and well-bounded quantities (acceptance rate of the two groups), as is done in the group fairness literature, indeed makes sense. However, applying the same ratio threshold on a quantity such as loss that can be arbitrarily high or low might not be very interpretable (also see point 3). For instance, if the original loss is very low (<<0) or very high (in the order of 10's), does it make sense to apply the ratio test. Similarly, the test might lead to very different behavior when the loss changes from say hinge loss to squared loss to logistic loss. Is this behavior indeed desirable? Some explanation here would be greatly helpful in convincing the readers of the usefulness of the ratio test. 

------------------

Post-rebuttal comments: Thanks for the detailed answers. Many of my concerns were addressed, and I am increasing my score as a result. A follow-up thought: It would be nice to add some discussion on the runtime of the proposed framework.
review_title: Interesting direction, but design choices can use more work

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper introduces a framework to statistically test whether a given model is individually fair or not. In particular, given a model, a distance metric over individuals, and a data point z, the authors propose an algorithm that finds a new data point z' such that z' is similar to z but their corresponding losses are different under the model -- if the model is not individually fair. They provide experimental results to show how their proposed method can detect unfairness in practice.

I think the paper tackles an interesting problem and has nice results, both theoretically and experimentally. My major concern about this paper is a fundamental one: what do you exactly mean by "individual fairness"? I think there should be a formal definition for the fairness notion you have in mind. According to the Individual Fairness notion of Dwork et al., even one couple of similar examples on which the given model performs differently constitutes unfairness. But it looks like the fairness notion in this paper requires that *on average over the input data distribution* the model is treating similar individuals similarly which is different/weaker than the notion proposed by Dwork et al.. Please clarify if I'm missing something, or else formally define the fairness notion you used in this work.

Other comments which are mostly about the technical development early on in the paper that I find hard to follow:

-I don't quite understand Eq. 2.2 and how it is solving an individually fair learning problem. Isn't that just the maximum expected loss on distributions that are epsilon far from the empirical distribution? If so, how does this help with fairness? Should W(P,P_n) be defined somewhere?

-Also, how is the dual problem obtained in Eq. 2.3? The authors say “it is known” but I think this requires more explanation/derivation.

-In Eq. 2.4, the function \ell_\lambda^c is defined as getting f(x_i) (a label) as input, but looking at the right hand side of the equation, this function actually depends on x_i itself, not f(x_i).

-How is the gradient flow attack related to the dual problem in Eq. 2.3 and 2.4? What happened to “epsilon” in this continuous formulation? It looks like that the primary objective now is to solve Eq. 2.4, and not the actual dual problem in 2.3, right? If that’s the case then what happened to primal and dual problems?

-How should one pick the stopping time T in Eq. 2.6 and how that affects the proposed method for finding the unfair map? Shouldn’t there be a theoretical statement about X(T), or the unfair map?

Overall I found section 2 of the paper very confusing. I will raise my score if the issues raised above are addressed.
review_title: Weak Accept

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a test to determine whether an ML model violates individual fairness. The main contribution beyond existing work is that this method allows for continuous feature spaces.

Conceptually, this paper rests on the "gradient flow attack," which produces a mapping that, given an example, produces another example which violates the inviddual fairness constraint. Thus, given a distribution, one can compute the change in loss between the original distribution and the mapped distribution. The ratio of these quantities is what the authors use for their hypothesis testing problem: is it below a the limit of tolerance or not?

For the most part, the paper is farily well-written, though it gets a little more difficult to understand towards the end. The basic premise is interesting -- using a gradient flow attack to discover pairs of elements that are similar but have different predicted outcomes.

I don't fully understand the motivation behind the loss ratio statistic. Why compare $\ell(f(\Phi(x, y)), y)$ and $\ell(f(x), y)$ instead of simply $f(\Phi(x, y))$ and $f(x)$? Does this become very sensitive when $\ell(f(x), y)$ is close to 0? If so, then it seems as though worse models might more easily pass the test, since the denominator of the loss ratio would generally be larger. I think the gradient flow attack is promising here, but I'm not convinced that this is the right test to run.

I'm not completely convinced by the claim that this test is interpretable: while the authors point to the 4/5 rule as a measure of impact, the loss ratio proposed here is clearly measuring something quite different from what a disparate impact test would traditionally measure. I don't see this as making the test results interpretable.

review_title: Review

Meta-review: This paper studies how to statistically test if a given model violates the constraint of individual fairness. This is an interesting and novel problem, and the paper leverages the technique of gradient flow to identify a "witness" pair for individual fairness violation. 
During the rebuttal, the authors have addressed many concerns raised in the reviews. The author should also consider discussing the runtime and improving the exposition to resolve some of the presentation issues raised in the reviews.
Decision: Accept (Poster)