Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: In this paper, the authors propose a post-processing method for removing bias from a trained model. The bias is defined as conditional statistical parity — for a given partitioning of the data, the predicted label should be conditionally uncorrelated with the sensitive (bias inducing) attribute for each partition. The authors relax this strong requirement to an epsilon-constraint on the conditional covariance for each partition. As an example, race (sensitive attribute) should be conditionally uncorrelated to whether an individual will default on their loan (predicted target) for each city (data partition). The authors propose a constrained optimization problem that takes the input data, sensitive attribute, partitioning and a trained model to yield a probabilistic decision rule. Subsequently, they propose an iterative solution to the problem, proving some theoretical properties as well as showing how the method compares to different baselines.

Fairness is an important consideration as machine learning models find purchase in sensitive applications like loan approvals, job candidate filtering, compensation decisions, and so on. This clearly written paper summarizes the different ways of removing data bias, and proposes a sensible and fairly general post-processing solution. The paper is easy to follow, and while the main body skims on some details to assist readability (and adhere to the page limit), the appendix, which I only quickly scanned, is well-done. I did have some concerns:

1. The assumption that “the original classifier outputs a monotone transformation of some approximation to the posterior probability p(y = 1 | x)” needs further justification since models often tend to be overconfident of the wrong predictions violating the monotonicity assumption [Guo, Chuan, et al. "On calibration of modern neural networks." arXiv preprint arXiv:1706.04599 (2017)]. How central is this assumption to the analysis?

2. In section 3 (Algorithm subsection) doesn’t \tilde{h} represent probability? If so, the function range should be [0,1], and not {0,1}.

3. Right below, a bar is missing in the absolute value: “can be written as |.| < \epsilon”.

4. Theorem 2 notation: h(x) \neq y would be more cleanly written with an indication function: I(h(x) \neq y).

5. In baseline comparison, using only conditional statistical parity might be unfair to other methods which don’t optimize this notion of bias explicitly. Did you consider evaluating for other metrics?

Overall, this is a well-written paper that tackles an important problem, and it would make for a good addition to the conference. 
review_title: Well written. Timely.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper considers the fair classification problem with respect to conditional statistical parity. It proposes a near-optimal post-processing algorithm for debiasing trained machine learning models, including deep neural networks. The empirical results show that the algorithm outperforms existing post-processing approaches for fair classification. 

Overall, I vote for accepting. Existing post-processing algorithms usually lack theoretical guarantees but not this paper. My main concern is the clarity; see cons.

Pros:
    1. The paper provides provable guarantees from both the impossible side and the algorithmic side.
    2. The post-processing approach does not require retraining the classifiers, and the impact on the test accuracy is limited.

Cons:
    1. Several symbols or notions lack explanations. E.g., what $\gamma$ means in Eq. (1)? What $\eta$ means in Eq. (2)?
    2. Theorems lack explanations. E.g., in Theorem 2, it is better to explain each term of the right side, including why these terms exist and when they are small. 
    3. Equations lack explanations. E.g., why the update rules should be formulated as (2)? It is better to explain the intuition.
review_title: Overall, I vote for accepting. Existing post-processing algorithms usually lack theoretical guarantees but not this paper. My main concern is the clarity.

final_score: rating: 4: Ok but not good enough - rejection
review_content: Evaluation and improvement of fairness of machine learning algorithms is a very important issue. To this end, the authors of this paper propose a post-processing algorithm to enforce fairness in a narrowly defined notion of fairness. Unfortunately, I have serious concerns about the validity of the results and conclusions of the paper, and hence I cannot recommend the paper to be accepted.

[**Definition**] This entire paper is only applicable to a narrow definition of fairness in Definition 1. Given that $a$ and $b$ are binary, Definition 1 (page 2) is essentially equivalent to assuming that $P[a= b =1 |c] = P[a= 1 |c]  P[b= 1 |c]$ which is weaker than the well-known demographic (statistical) parity, and is only applicable to a binary setting. Hence, the applicability of the proposed algorithm is extremely limited.

[**Theory**] The theoretical exposure in this paper is confusing and not rigorous. The trouble begins from the unnumbered equation in page 4, where the authors define $\widetilde{h}$. It is unclear what $\widetilde{h}$ depends on. Also, the output is seemingly binary, but the authors claim this a _randomized prediction rule_ and $\widetilde{h}(\mathbf{x})$ represents the probability of predicting the positive class. **Proposition 1** is an obvious statement and not relevant to the claims of this paper, and hence should be removed. **Theorem 1:** In the proof of Theorem 1, the authors make an assumption about what the output of $f$ is. In different places the output is assumed to be in $[0,1]$ and $[-1, 1]$!! Even worse, they claim that the empirical average of some loss value is equal to its expectation (_what happened to generalization?_). That is where I stopped reading.

[**Experiments**] The experiments are very weak and not convincing. The paper only compares with Hardt et al. but in an unconvincing way as detailed here. **(a)** the comparisons should be made in terms of a tradeoff curve between _fairness_ and _performance_. In the currently reported results, there are instances where Hard et al. and the proposed method are not comparable, e.g., kNN. **(b)** The comparisons are unfair because they are done with respect to Definition 1, which is a very narrow sense of fairness while Hard et al. impose fairness either with respect to _equalized odds_ or _equal opportiunity_  which require conditional independence of $\widehat{Y}$ and $S$ given $Y (=1)$. Hence, the comparison with Hard et al. is unjustified. At the very least the authors should compare with a plethora of baselines designed for demographic parity (e.g., Kamiran et al. 2012, Zemel et al. 2013, Feldman et al. 2015, Zafar et al. 2017, Jiang et al. 2019, Baharlouei at al. 2020). Even then, the comparison should be done with respect to the statistical parity violation as defined in Dwork et al. 2012, which is a more established notion of fairness.

===== after rebuttal =====

I'd like to thank the authors for their revisions, which have significantly improved the readability of the paper, and the presentation of the results. The addition of fairness violation/accuracy tradeoffs and also (Kamiran et al. 2012) add a lot of value in putting this paper in the right context. After reading the rebuttal, I still remain unconvinced about the contributions of this paper. From a practical point of view, the performance of the proposed algorithm is on a par with (Kamiran et al. 2012), which is a baseline for demographic parity and has been improved on several times in the past 8 years. On the other hand, the main claim of the paper seems to be theoretical optimality. Unfortunately, although several previous mistakes have been corrected in the proofs, I cannot still follow the proofs of Theorems 1 and 2. New notation pops up all over the proof, and it is unclear how to follow some lines from the others. Given this, I am increasing my rating to 4 in acknowledgement of my previous misunderstanding of the definition of the statistical parity, which was cleared by the authors during the discussion period. However, I am still unable to recommend this paper in the current form for publication in the conference proceedings.
review_title: weak paper on an important subject

Meta-review: All reviewers feel this paper addresses and important topic, and has many merits. However, it is difficult to recommend publication at this time. The primary concern is that the paper has its theoretical optimality as an important contribution, but the reviewers and myself (in a non-public thread) were unable to verify the correctness of the proofs. In part unfortunately this is due to edits to the proofs happening late in the revision period, too late for further discussion with the authors. Some of the particular questions in the proof of theorem 1 (appendix B) include: clarifying the value of $\rho$ which makes the unnumbered equation above equation (6) equivalent to definition 1, and in particular whether the $1/|X_k|$ term should be inside or outside the absolute value; and clarifying various undefined symbols which are introduced in the equation at the top of page 13, but are never defined, including $M$, $b$, and $z_i$. Reviewers also had some concern that the algorithm should be benchmarked against more recent / better performant baselines than Kamiran et al. (2012).
Decision: Reject