Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper extends the individual fairness definition in order to (i) do statistical analysis (e.g., generalization bound) (ii) have the form of regularization so the practitioner can tune the parameter. Theorem 2.3 shows how to do stochastic optimization on the new definition, and Theorem 3.1 shows that that the new definition generalizes. 

The paper is extremely well written, it was effortless to follow the arguments, and I enjoyed reading it. The theory part is sound and interesting, and the authors did a thorough experimental analysis on three datasets and compared their work with two baselines.


The authors motivate this work as a new formulation of individual fairness that decouples accuracy and fairness with a regularization term, enabling the practitioner to tune the parameter. I found this argument unconvincing. It is much easier for the practitioner to tune epsilon and delta, and the algorithm finds the minimum error while satisfying DIF. Tuning \ro after setting epsilon and delta is not very intuitive for practitioners. 

Minor concerns:
In the related work, the authors argue that their work is different from previous extensions of the IF since they use the metric instead of the oracle. What is the big difference between using oracle and having access to metric? Can one serve instead of the other?
In the experiment section, the number reported for CLP is very different from their paper on comment toxicity detection. 
I think having a few sentences on how to learn the individual metrics would be really good. (Right now, you refer to many work on learning metrics multiple times, but it’s never clear how they learn the similarity metric).
Comparing equation 2.1 and definition 2.1 is somewhat confusing. I think it would be more clear if you say 2.1 and 2.2 instead.
review_title: Good paper, the authors might use other reasons to motivate their paper.

final_score: rating: 7: Good paper, accept
review_content: 
Quality
- This paper is largely well-written with clearly stated theoretical results, and a range of experiments on three datasets.

Clarity
- What is the notation $\Delta(\mathcal{X} \times \mathcal{X})$?
- In the experiments section, SenSeI is compared with CLP, which is a method that uses hand-crafted counterfactuals. However, it appears that SenSeI’s implementation of individuals crucially requires hand-crafted counterfactuals as well? It was not clear to what the distance metric used in the experiments was. If the SenSeI implementation also uses the same counterfactuals, please comment on whether this is a fair comparison with CLP, and if other implementations of SenSeI (with different metrics) would yield the same results.
- Why are group fairness metrics compared in the experiments section? None of the methods studied target group fairness in general so the connection and relevance of group fairness should be elaborated upon.

Originality/Significance
- This paper’s original contribution is variant definition of Dwork et al’s “individual fairness” notion, that circumvents its computational intractability, by making it smooth. This is a significant enough contribution to the study of individual fairness, that makes it more applicable in practice.
review_title: contribution is more tractable variant of Dwork et al’s “individual fairness" definition

final_score: rating: 7: Good paper, accept
review_content: ############# Summary of contributions ##############

This paper tackles the problem of enforcing individual fairness. They define a notion of “distributional individual fairness” (DIF) which related to Dwork et al. 2011’s definition of individual fairness. They then provide an algorithm that enforces their DIF definition of individual fairness. They take as given the similarity metric required for evaluating individual fairness. 

Specifically, contributions include:

- Theoretical: This paper proposes an “average case” definition for individual fairness which they call “distributional individual fairness” (DIF) (Definition 2.1). They theoretically compare DIF to the previous definition of individual fairness from Dwork et al. (Equation 2.1). DIF has the advantage of being computationally easier to enforce.

- Algorithmic: This paper proposes an algorithm for enforcing DIF using stochastic gradient methods.

- Theoretical: They provide a generalization bound for their algorithm (Theorem 3.1).

- Empirical: Using three real-world datasets, they evaluate their algorithm’s ability to satisfy both individual and group-based fairness constraints. 

############# Strengths ##############

- The experiments are well set up and reflect real-world problems. The toxic comment detection experiment includes a counterfactual individual fairness metric that is reasonable and has precedent. 

- Experiments evaluate group-based fairness metrics in addition to individual fairness metrics. These metrics are all relevant to their respective datasets and problem setups. 

- The paper also discusses the theoretical relationship between their definition of “distributional individual fairness” (DIF) and the existing individual fairness definition proposed by Dwork et al. (Equation 2.1). This comparison is presented well. 

- The paper provides theoretical analysis of the proposed algorithm. Theorem 3.1 provides a generalization bound for the SenSeI algorithm. Theorem 2.3 provides the dual form of the DIF regularizer which is used to solve their optimization problem for enforcing distributional individual fairness. 

- The related work is well organized. It covers related work in enforcing individual fairness and learning similarity metrics.

- The hyperparameter selection procedure is well documented in Appendix B. 

############# Weaknesses ##############

- It would be nice to have a clearer picture of the cases in which satisfying DIF actually leads to satisfying the individual fairness definition of Dwork et al. (Equation (2.1)), and vice versa. Currently, the theoretical comparison of DIF and Equation (2.1) feels a bit abstract and difficult to translate into real-world applications. Are there some distributional assumptions under which satisfying DIF implies satisfying Equation (2.1) (or vice versa)? 

############# Recommendation ##############

Overall, my recommendation is 7: Good paper, accept. This paper provides a theoretically-backed algorithm for enforcing their definition of “distributionally individual fairness.” Their analysis is understandable, and their experiments appear detailed enough to be reproducible. My only major ask is for a more concrete and practically actionable description of the difference between DIF and Dwork et al.’s individual fairness.

############# Questions and clarifications ##############

- After Equation (2.3) on page 2, the authors state that the T(x) map corresponding to Equation (2.1) may not be an optimal point of Equation (2.3). Can the authors give a concrete example of a probability distribution P in Equation (2.3) when this T(x) is not optimal? This would give us further intuition for the difference between DIF (Definition 2.1) and Dwork et al.’s individual fairness (Equation (2.1)). 

- The notation in Equation (2.4) is unclear. Is x’ a random variable with distribution P’, and if so, why is x’ lowercase (it seems that up to this point the paper has kept the convention that random variables are upper case and fixed values are lowercase)? What about the random variable Y? Is P’ the joint distribution of X’, Y’? If that’s the case, why does it say that W_{dX}(P, Q) is the Wasserstein distance between distributions on \mathcal{X}? It seems there are some typos here that the authors should clarify.

- In Definition 2.2, Is \Delta(\mathcal{X} \times \mathcal{X}) supposed to represent the set of all probability distributions over \mathcal{X} \times \mathcal{X}? I don’t see this defined explicitly anywhere.

- Is the \hat{h} notation really necessary at the top of page 6 in the last sentence before Section 4? The \hat{h} notation has not been defined or used up to this point. It seems that it would be sufficient to just use h in this sentence, as h has already been referred to as the trained ML model. 

- Figure 1 is hard to read. The red/blue dots are not colorblind-friendly -- maybe you can use different symbols in addition to different colors, e.g. x’s for the red dots and o’s for the blue dots. The x and y axis labels are also extremely tiny.

review_title: Well documented and theoretically-backed method for enforcing individual fairness.

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a variant of individual fairness, develops an algorithm to enforce this definition, and evaluates it. The fairness definition is based on transport, considering the maximum difference in outcomes for individuals drawn from a distribution "close" to the original data distribution in terms of a similarity metric.

The paper is well-written and thorough. The technical definition of individual fairness is a natural one, and it is amenable to stochastic optimization. Compared to other methods, SenSeI enforces the fairness constraint more strongly, at the cost of accuracy.

SenSeI comes with reasonably strong theoretical guarantees, which I appreciate.

The individual fairness constraints used in the experiments are all essentially counterfactual in nature -- certain pairs or groups of examples should get the same outcome, and there are no other constraints. Are there scenarios (even synthetic) where one could use more continuous similarity metrics?

This may be outside the scope of this work, but it would be interesting to dig deeper into which examples lead to fairness violations. For example, in the toxicity classifier, could an investigation into fairness violations tell us something about which counterfactuals are hard to treat equally, and therefore something about the way language is used?
review_title: Review

Meta-review: All of the reviewers agree that this paper is well-written, and provides sound theoretical analyses and comprehensive empirical evaluations. Overall, this paper makes a useful contribution in the direction of individual fairness. The authors have also addressed the concerns raised by the reviewers in their response.
Decision: Accept (Oral)