- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper presents a series of three impossibility results related to fairness in machine learning. The authors identify three separate sources of disparity and analyze their impact:
- Task-specific (Theorem 2.1): they show that, given a problem that is inherently uncertain for a subgroup, no model can achieve both exact parity and Bayes-optimal performance.
- Algorithmic and Statistical (Theorem 2.2): for a binary classification task with a 0-1 loss, the authors provide a minimax lower bound on the "cost ratio" quantity and the overall population risk; they also argue that overall risk and fairness are in conflict when learning from finite data.
- Structural (Theorem 2.3). In a similar result to Theorem 2.1, they provide a lower bound on the performance of a model that satisfies exact parity based on the model's capacity.
The authors place their work in the context of well-known prior impossibility results (e.g., Kleinberg et al., 2017; Chouldechova, 2017). The paper is purely theoretical and contains no experiments.
Critical strengths
- The paper identifies significant impossibility results in fair machine learning.
- Theorem 2.1 establishes the price of parity, giving a task-dependent lower bound on the performance of any model that achieves exact parity across subgroups.
- Theorem 2.3 obtains a similar result with respect to model capacity.
- The paper is clearly written and easy to parse, with well-structured proofs.
Critical weaknesses
The sample complexity and convergence results, presented among the main contributions of the paper, are not supported.
The results are presented in detail in Section 2.3.1, and are derived from Corollary 2.2, which states that
The authors then claim, e.g., that "enforcing a relatively strict and slowly decaying floor (e.g., $ c(n) = 1/ \log n $) yields correspondingly slow convergence rates", and "achieving vanishing cost necessitates ".
However, the left-hand side of Corollary 2.2 does not depend on . Since the statement of the corollary holds for any choice of , we may substitute , which gives
Neither side depends on . Same result can be obtained by combining (28) and (30) in Theorem B.1, then taking the sup and inf on both sides as in the existing proof.
This shows that uniform statistical consistency over realizable distributions $ \sup_{P \in \mathcal{P}_{real}(p_b)} \mathbb{E}[a(h_s)] \rightarrow 0 $ is impossible for any learner regardless of the choice of . As a consequence, the sample complexity would be infinite for any $ \nu < \frac{1-p_b}{4} $. All results in 2.3.1 concerning the convergence rate and sample complexity depend on the premise that varying influences the minimax risk on the left-hand side, when it does not.
Minor issues:
- Note that the definition of statistical consistency after Corollary 2.2 does not refer to the uniform-over-realizable-distributions, or indeed "distribution-free" consistency, as it lacks the supremum over distributions.
Questions for authors
Regarding the sample complexity and convergence results (see Weaknesses):
-
The left-hand side of Corollary 2.2 is independent of the regularization parameter $ c $ or $ c(n) $. Could the authors clarify if $ c $ is meant to constrain the set of learners in the statement of the Corollary? If so, this should be stated explicitly.
-
Theorem B.1 yields $ \inf_{\mathcal{A}} \sup_{P \in \mathcal{P}_{real}(p_b)} \mathbb{E}_S[a(h_S)] \geq \frac{1-p_b}{4} $. This is a stricter lower bound than that in Corollary 2.2, overriding the sample complexity results of Section 2.3.1. Could the authors clarify how are the sample complexity results obtained?
-
Lines 310, 311 state:
Bounding the maximum possible disparity requires a non-vanishing ''.
This claim is not substantiated explicitly. One can suppose this refers to the trivial upper bound
However, as evident from the derivation, this result does not put a bound on the actual cost ratio $ \frac{a_{\bar b}(h_S)}{ a_b(h_S) } $. Could the authors state how exactly is the maximum possible disparity bounded by in this context?
Conclusion
I would be willing to raise my score if the authors could either (i) remove the sample complexity and convergence results from the paper entirely (in my opinion, the contributions of Theorem 2.1 and 2.3 are valuable enough to warrant acceptance), or indeed (ii) provide corrected sample complexity and convergence estimates, which would enhance the paper's contributions even more.