Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper examines the conditions under which equalized odds can be achieved from a theoretical perspective. The authors show that in general, equalized odds cannot be achieved in linear regression and clasisication tasks. However, when randomized prediction is allowed, they show that equalized odds can be achieved in binary settings.

Overall, I don't really see the motivation for this paper. Equalized odds isn't typically considered in linear regression tasks, and moreover, the generalization given in this paper is particularly restrictive -- it requires matching distributions across sensitive attributes conditioned on the target variable. One could imagine a less restrictive generalization like matching expectations, i.e., $E[\tilde Y | Y, A = a_1] = E[\tilde Y | Y, A = a_2]$.

In general, equalized odds can always be achieved with trivial, constant classifiers, so the authors specify that they're only interested in non-trivial classifiers. This paper only considers the question of whether classifiers can exactly satisfy equalized odds -- presumably, given that trivial classifiers satisfy equalized odds, something epsilon-close to a trivial classifier will satisfy an epsilon-approximation of equalized odds. What this paper doesn't answer, and what would in my mind be a far more interesting result, is the converse: if the conditions specified in the paper are not met, is it still possible to get an epsilon-approximation of equalized odds? If so, then this would imply that the conditions derived here are in a sense qualitatively necessary. If not, then these results would seem more brittle.

The techniques used to derive the positive result (that equalized odds can be satisfied with randomized classification) appear to just be a formal statement of the algorithm given by Hardt et al. (2016).

The paper itself is a little difficult to parse at times. Section 2.1 appears to be an attempt to specify a qualitative relationship between ideas about fairness, but I find it difficult to understand what the purpose is.

review_title: Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies under what conditions a classifier can satisfy the condition of equalized odds. The authors first prove an impossibility result which shows that (under linear non-gaussian case) any deterministic classifier	cannot achieve equalized odds across the protected groups. This leads to the question of randomized classifier. We can always satisfy equalized odds with randomized classifier  with a trivial classifier. However, the authors show two interesting results — (1) using the post-processing framework developed in Hard et. al. (2016) it is possible to obtain a non-trivial randomized classifier that satisfies EO, and (2) in-processing based classifiers are better than the post-processing based fair classifiers if we compare them in terms of accuracy.

I didn’t find the result about deterministic classifier to be surprising. However, it is interesting that the authors think that a similar result holds for non-linear regression. The experiments definitely suggests that but I am wondering if the authors have more intuition regarding this direction. At least, I don’t see how the proof for the linear case extends for the general non-linear setting.

The results for the randomized classifiers are interesting, however I think they are expected. Several prior papers have observed that in-processing based classifiers do perform better than the post-processing classifiers in practice (e.g. see experimental section in Agarwal et. al. 2018). But it is nice to see a formal proof of this fact. I have two questions regarding this result —

1. The result only proves weak inclusion of the Omega() sets. Is there any interpretable conditions when the inclusion is strict and in-processing is strictly better than post-processing?
2. I understand the focus of this paper is EO constraint, but does a similar result can be proven for other fairness constraints, perhaps extending the proof technique presented here?

Weaknesses:

Even though the results in this paper are interesting, the main weakness of the paper is that  the techniques are not novel. In fact, the proof relies on the ROC plane characterization of post-processing classifiers established in earlier papers. Additionally, I think a more interesting question to consider would have been the trade-off between EO fairness and accuracy. In fact, the plots in figure 3 does show such trade-offs. 

In summary, I think the paper makes interesting contributions in understanding the attainability of the EO fairness constraints. However, the results are not complete in its current setup and also the techniques are limited to the particular notion of fairness considered in this paper.

review_title: Interesting results in attainability of Equalized Odds fairness

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper studies the attainability of the equalized-odd fairness criteria introduced by Hardt et al'16 in classification and regression tasks. In particular, the paper claims that under certain conditions EQ is not even attainable. They proved the claim for the regression task but I could not find exactly where they discuss the classification attainability.  In fact, the (non)attainability claim about EQ is confusing to me since by definition, a *perfect* predictor (which is non-trivial) satisfies EQ. Intuitively, their result is meaningful for the task of linear regression as a perfect predictor may not exist. But as we consider classification or non-linear regression it becomes less believable. For instance as the authors mentioned, in a previous work, Woodworth et al.'17 showed that even checking a predictor is fair w.r.t. EO notion is not possible when we use *finite* many samples. 

The results on classification with deterministic prediction seems restrictive as condition (i) seems very strong. Assuming condition (i), Theorem 4.1 seems straightforward to prove. Also, what is the difference between Theorem 4.2 and the previous results on the existence of fair predictor w.r.t. EQ in Hardt et al.'16 (e.g., Proposition 4.4.). Please elaborate on this. Lastly, Theorem 4.3 seems very interesting.

Minor comments:
- The figure 1 which has been referred to several times of the paper is missing.
- Hardt et al. entry in References has typo.
- page 2: outputing -> outputting, utiziling ->utlizing
- page 3: Eqaulized -> Equalized
- page 4: Eqalized -> Equalized
- page 6: unconstrianed -> unconstrained, seperately -> separately
- page 8: convariance -> covariance, appximated -> approximated, numerial -> numerical
- page 13: quadractic -> quadratic
- page 15: insection -> intersection

=====POST-REBUTTAL COMMENTS========
I would like to thank authors for their clarifications. Accordingly, I have increased my score to 6.
review_title: clarify the setting in more detail

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
# Main claims and contributions

The authors study if Equalized Odds (EO) definition of fairness is attainable for regression and classification problems. In their paper, the authors make several contributions:
1. They provide an example of linear regression problem, for which EO can never be satisfied (Theorem 3.1)
2. For classification problem, the authors prove in Theorem 4.1 that if the predictor is deterministic, then EO is satisfied only under strict assumption on data distribution. In contrast, if the predictor is randomized, the authors show in Theorem 4.2 that EO is attainable under mild assumptions.  
3. The authors compare different techniques for obtaining EO-satisfying predictors. Namely, they compare in- and post-processing techniques. They prove in Theorem 4.3 that in-processing allows for better classification accuracy compare to the post-processing technique from Hardt et al. (2016).

The authors, perform numerical experiments to support their claims. For regression task, they learn linear and non-linear predictors on data with gaussian and non-gaussian noise and observe that EO is essentially impossible to satisfy in non-linear regression even if exogenous terms are gaussian. For classification problem, they compare different in-processing techniques with a post-processing technique from Hardt et al. (2016).

# Novelty

To the best of my knowledge, the question of attainability of EO for regression/classification for deterministic clarifier is novel in the literature.

On the other hand, the same question for randomized predictor (Section 4.2) seems to be already answered in the literature by Hardt et al. In particular, Theorem 4.2 seems already known and I did not understood clearly what is the contribution of 4.2.3.

# Clarity and soundness

The paper is relatively easy to follow, apart from Section 4.2.3 (and in general the discussion about the ROC curve, and the role of Figure 1). The assumption of infinite data allows the authors to simplify the exposition. Some details:

1. Lemma A.1. looks like a known fact. 
2. Theorem 3.1: make clear transitions steps by justifying what properties of random vectors are used.
3. Theorem 4.1: proof seems to be fine, no comments
4. Theorem 4.2: in Hardt et al. (2016), they show that the resampling probabilities can be calculated by solving an LP, need to justify the novelty of the result / emphasize the increment.
5. Theorem 4.3: to me, both the statement and the proofs are hard to parse.

# Reasons to accept

The authors ask an important question of whether the standard definition of fairness (EO) is attainable for any instance of problems even with infinite data. They provide a counterexample for regression problem. The authors give a condition under which EO is attainable for classification. The authors compare in- and post-processing techniques in terms of their efficiencies.

# Reasons to reject

The authors are encouraged to make clear which statements are novel and which were already known in the literature. For example, the result in Theorem 4.2 seems to be contained in Hardt et al. (2016).

The authors mention pre-, in- and post-processing techniques for fair classification/regression. However, only in- and post-processing are compared. It would be interesting to include also the pre-processing to the discussion.

The authors compare deterministic algorithms (Zafar et al. (2017a) , Rezaei et al. (2020)…) with a probabilistic algorithm from Hardt et al. (2016), which does not seem to be a fair comparison. 

## minor Typos:

P.4 Equalized Odds
P.5  Equalized Odds
P.6 separately
P.7 covariance, approximated

review_title: The negative results are interesting but the positive results seem known.

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: 

This paper studies the attainability of Equalized Odds fairness criterion in both the classification and regression problems. When the prediction function is deterministic, it shows that Equalized Odds may not be attainable under certain conditions. In contrast, if the prediction function is randomized, then Equalized Odds classifiers can always be achieved under some conditions. Moreover, it shows that the performance attained using the in-processing approach after exploiting all available features is always better than attained using the post-processing approach. 

Strengths:

1. The conditions under which perfect Equalized Odds can be attained are identified under various settings, including both regression and classification, and cases when prediction mapping is deterministic and randomized. 

2. Utilizing ROC feasible area, the paper builds a connection between two approaches used to achieve fairness: in-processsing approach and post-processing approach. Specifically, the constraint enforced by post-processing consists of the constraint enforced by in-processing and an additional constraint.  

Comments: 

1. In the experiments (Figure 3), how is the level of fairness violation selected? Are they the best attainable level? Because of the tradeoff between accuracy and fairness, it is possible to improve accuracy by adjusting the fairness guarantee. For example, according to Figure 1 in Agarwal et al. 2018, for many datasets, the reduction approach (in-processing) can achieve any desired fairness level between fairness of post-processing (Hardt et al. 2016) and fairness of unconstrained classifier. It means that it is possible to achieve perfect Equalized Odds using Agarwal et al. 2018. I hope the authors can explain this point. Moreover, the reduction approach returns a randomized classifier, rather than the deterministic function of features as mentioned in the paper. It is necessary to make clarifications in the paper. 

2. Related work: the attainability of perfect fairness (in addition to Equalized Odds) has been studied in the literature, which is highly related to this work. I suggest authors including them in related work. For example, "Cummings, R.; Gupta, V.; Kimpara, D.; and Morgenstern, J. On the compatibility of privacy and fairness, 2019". It shows that it’s impossible to train a differentially private classifier (a randomized classifier) that satisfies exact (perfect) Equal opportunity fairness and achieves a higher accuracy than a constant classifier.

3. It would be better if authors can add some explanations/intuitions of theorems, e.g., in Thm 3.1, how strong the assumption is that $f_2$ and $f_3$ are third-order differentiable.  

4. Conditions given in Theorem 4.1 seems to be the necessary and sufficient condition. It would be better if authors can clearly state it in the theorem (e.g., Equalized Odds holds if and only if conditions are satisfied).

5. Typos: in Eqn (5), $P_{\hat{Y}|AY}(1|a,y) —> P_{\hat{Y}|AY}(u|a,y)$ 


review_title: I would recommend for now weak accept. Attainability of Equalized Odds is an interesting topic and authors study this problem in various settings. My main concern is on experiments, and I hope authors can address it in rebuttal.  

Meta-review: The paper study under which condition a classifier can respect the condition of equalized odds. The reviewers find the paper interesting but they also raise some important concerns about it.

First, multiple reviewers pointed out that the results are not particularly novel or surprising and, even after discussing the rebuttal, they consider the result a bit incremental.

Second, the motivation of the paper are also questioned by multiple reviewers that suggested to study the tradeoff between trade-off between EO fairness and accuracy.

Overall, the paper contains some interesting ideas but it is below the high acceptance bar of ICLR.
Decision: Reject