Summary
The paper explores the fairness problem in machine learning when sensitive attributes (e.g., demographics and gender) are unavailable for practitioners. The authors focus on the Equalized-Odds (EOD), a well-known definition of fairness for classifiers. The authors provide bounds for EOD violation in a setting where sensitive attributes are unavailable. Additionally, they propose a post-processing method to control the worst-case EOD. Finally, the authors illustrate their results via synthetic and real-world datasets experiments.
Strengths
* The paper is very well written. Particularly the related work section is very informative.
* The authors explore an interesting problem for the community and propose a different view of the problem, i.e., a worst-case optimization.
* The theoretical guarantees provide a method for practitioners to access the quality of the method (assuming a worst-case scenario).
* The proposed method is simple, intuitive, and computationally inexpensive.
Weaknesses
* The evaluation in the main paper is limited. The authors only apply their method to one real-world example. I suggest adding at least two more examples and as many examples as possible in the appendix. These examples can convince us that: (i) Assumption 1 is followed in multiple scenarios and (ii) your method helps to improve fairness.
* The fact that the Naïve approach had a better "true" EOD is interesting, and it might indicate that your method is not very efficient, i.e., using the sharp upper bound as a proxy for the true value is too pessimistic. Performing more experiments in real-world datasets can help the authors and readers understand when minimizing the upper bound is better than the naïve approach.
* It needs to be clarified how to extend the approach to a setting where the sensitive attribute is not binary. In the introduction, the authors list examples of sensitive attributes as "demographics and gender," which are not binary. A subsection is recommended to discuss how your results would change when $A$ is not binary.
Questions
* Is it possible to extend this worst-case analysis to other post-processing methods? Combining it with the optimized method proposed in [1] would be very interesting.
* In Theorem 2 the authors assume that $\mathcal{F}$ is such that $ \forall f \in \mathcal{F}$ the Assumption 1 is followed. After that, they conclude that then, there exists a fair model in $\mathcal{F}$. This doesn’t seem correct. For example, take $\mathcal{F} = \{f_0\}$ where $f_0$ follows Assumption 1 but is not worst-case optimal. Then, there is no fair model in $\mathcal{F}$. Perhaps, the authors mean $\mathcal{F}$ to be the set of *all* models that follow Assumption 1. However, in this case, assuming knowledge of $\mathcal{F}$ does not sound reasonable. Could the authors clarify this point?
* Could you describe (in the main paper) when the worst-case bound is achieved?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The authors discuss their work limitations. I also suggest discussing the ethics of predicting users' sensitive attributes.