Abstract: This work provides several fundamental characterizations of the optimal classification function under the demographic parity constraint. In the awareness framework, akin to the classical unconstrained classification case, we show that maximizing accuracy under this fairness constraint is equivalent to solving a fair regression problem followed by thresholding at level $1/2$. We extend this result to linear-fractional classification measures (e.g., $F$-score, AM measure, balanced accuracy, etc.), highlighting the fundamental role played by regression in this framework. Our results leverage recently developed connection between the demographic parity constraint and the multi-marginal optimal transport formulation. Informally, our result shows that the transition between the unconstrained problem and the fair one is achieved by replacing the conditional expectation of the label by the solution of the fair regression problem. Finally, leveraging our analysis, we demonstrate an equivalence between the awareness and the unawareness setups for two sensitive groups.
Introduction
In standard machine learning, the relationship between regression and classification is well-established. To obtain an optimal classifier—one that maximizes accuracy—a common approach is to train a regression model to predict label probabilities and threshold the output at 0.5. For more complex, non-decomposable metrics like the F-score or Jaccard index, the same regression function is used, albeit with a mathematically derived, metric-specific cutoff.
However, introducing fairness constraints, such as Demographic Parity (DP), complicates this relationship. DP requires that predictions be independent of sensitive attributes (e.g., race or gender). Historically, fair classification algorithms have often relied on complex, black-box rules, leaving the theoretical link between fair regression and fair classification opaque. This paper bridges that gap, proving that the "thresholding principle" remains valid even under strict fairness constraints.
The Fair Thresholding Principle
The core contribution of this work is the demonstration that adding a demographic parity constraint does not break the fundamental link between regression and classification. By utilizing univariate optimal transport theory, the authors show that fair regression can be solved by mapping the predictions of different sensitive groups to their common Wasserstein-2 barycenter.
As illustrated in the figure above, the transition from an unconstrained Bayes classifier to a fair one involves replacing the standard Bayes optimal regressor with the optimal fair regressor ($f^*$). For accuracy, the optimal fair classifier $g^*(x, s)$ is simply the indicator function $\mathbf{1}(f^*(x, s) \ge 1/2)$. This result proves that optimizing for demographic parity naturally results in "strong demographic parity," where the underlying continuous score itself is fair, not just the final binary output.
Optimizing Non-decomposable Measures
The authors extend this thresholding principle to a broad family of "linear-fractional" performance measures. This family includes widely used metrics such as the F-score, AM measure, and balanced accuracy. The research provides a rigorous theoretical characterization of what an optimal fair classifier looks like for these metrics, which was previously missing from the literature.
For these metrics, the optimal fair classifier is defined as $g^*(x, s) = \mathbf{1}(f^*(x, s) \ge \theta^*)$, where $\theta^*$ is a specific threshold found by solving a fixed-point equation based on the parameters $(n, d)$ shown in the table above. This allows practitioners to derive exact thresholds to maximize complex metrics while maintaining demographic parity.
Unawareness and Implicit Guessing
A significant challenge in fair ML is the "unawareness" setup, where algorithms are forbidden from using sensitive attributes at prediction time. The authors introduce a novel theoretical reduction scheme using the Hahn decomposition theorem for signed measures. This scheme transforms the unawareness problem into an awareness problem, allowing the application of their optimal transport findings.
This provides a rigorous mathematical justification for "implicit guessing"—the phenomenon where unaware models attempt to reconstruct missing sensitive attributes from other features. The optimal unaware classifier mathematically relies on the conditional distribution of the sensitive attribute given the available features. Furthermore, the authors derive an exact expression for the "Price of Fairness," showing it is strictly bounded by the level of unfairness present in the original, unconstrained Bayes optimal predictor.
Conclusion
This work establishes that the fundamental tools of unconstrained classification—regression and thresholding—are equally powerful in the fair learning domain. While the current unawareness reduction is limited to binary sensitive attributes, the framework provides a clear path forward for interpreting and designing fair classifiers across a wide range of performance measures. Future research will aim to extend these interpretable theoretical studies to other constraints, such as Equalized Odds.
Summary updated