A Theoretical Approach to Characterize the Accuracy-Fairness Trade-off Pareto Frontier

Hua Tang, Lu Cheng, Ninghao Liu, Mengnan DuSubmission to ICLR 2024 · Rejected

TL;DR

While the tension between model accuracy and fairness is well known empirically, its mathematical geometry remains poorly understood. This paper theoretically characterizes the accuracy–fairness Pareto frontier (FairFrontier) under the Equalized Odds criterion, proving that while fairness can almost always be steadily improved, pushing too hard for perfect fairness can cause accuracy to plummet sharply. The authors then formalize conditions under which this trade-off can be eliminated altogether through a two-step decoupling of data and model unfairness.

What Problem Does This Paper Address?

In fair machine learning (FairML), researchers and practitioners frequently observe that making an algorithm fairer (e.g., ensuring equal error rates across demographic groups) degrades overall predictive accuracy. However, most prior work approaches this tension empirically or focuses purely on whether a trade-off exists, rather than analyzing what the optimal boundary looks like.

Without understanding the geometry of this frontier:

  1. Practitioners cannot tell whether an accuracy drop is an inevitable theoretical limitation or merely an artifact of poor model optimization.
  2. It remains unclear whether extreme pursuit of fairness causes smooth, predictable compromises or catastrophic collapses in accuracy.

The authors set out to map the exact shape of this trade-off curve—the FairFrontier—by analyzing the decision boundaries of Bayes-optimal classifiers under the Equalized Odds metric.

Methods

The authors analyze binary classification with a binary sensitive attribute ($A \in \{0, 1\}$) under Equalized Odds (measuring discrepancies in True Positive Rate [TPR] and True Negative Rate [TNR]). Their theoretical approach centers on the geometry of decision boundaries rather than specific model architectures:

  • Pareto Optimality & Frontier Shapes: They define the FairFrontier as the set of non-dominated classifiers in the accuracy–fairness plane and analyze four possible continuity profiles: continuous, sharp decline in accuracy, sharp decline in fairness, or sharp decline in both.
  • Ideal vs. Practical Settings:
  • Ideal setting: The non-sensitive features $X$ fully encode the sensitive attribute $A$.
  • Practical setting: $X$ only partially proxies $A$, leading to overlapping group distributions.
  • Unfairness Decomposition: They decompose total unfairness ($F_U$) into data unfairness ($F_{DU}$, stemming from inherent label/feature imbalances across groups) and model unfairness ($F_{MU}$, originating from disparities induced by the decision boundary): $$F_U \le F_{DU} + F_{MU}$$
  • Streamlined Elimination Strategy: A proposed two-step procedure that first neutralizes $F_{DU}$ (via data augmentation/sampling) and then aligns group decision boundaries to drive $F_{MU} = 0$.

Datasets

Because this is a foundational theoretical paper studying Bayes-optimal classifiers under known distributions, the authors evaluate their formulations exclusively on synthetic datasets:

  • Gaussian mixtures: 1D synthetic setups with distinct group means and variances (e.g., $X|A=a, Y=y \sim \mathcal{N}(\mu, \sigma^2)$) to simulate both balanced and imbalanced demographic scenarios.
  • Triangular distributions: Controlled setups ($\text{Triang}(a, b, c)$) designed to explicitly test whether group-specific optimal decision boundaries coincide or diverge.

No real-world benchmark datasets were used in the paper.

Key Insights and Ideas

  • Fairness drops are impossible: Neither a sharp cliff in fairness alone nor a simultaneous cliff in both accuracy and fairness can occur. Sacrificing accuracy will always allow continuous, steady gains in fairness.
  • The "Over-pursuing Fairness" Cliff: When features are imperfect proxies for the protected attribute, demanding strict, complete fairness can trigger a discontinuous collapse in accuracy (an empirical drop of $>0.20$ accuracy in their synthetic example). Mathematically, forcing Equalized Odds across conflicting distributions can trivialize the classifier into making constant predictions regardless of input features.
  • Non-Convexity: The existence of sudden accuracy drops proves that the FairFrontier can be non-convex, directly challenging the ubiquitous assumption in fair ML optimization that fair loss landscapes are convex.
  • Eliminating the Trade-off: Maximum accuracy and perfect fairness can simultaneously coexist if and only if data unfairness is zero ($F_{DU} = 0$) and the optimal decision boundaries for both protected groups are identical ($T^*_{A=0} = T^*_{A=1}$).

Key Results

  • Discontinuity Proofs: The authors prove analytically that the FairFrontier is strictly continuous when $X$ fully captures $A$, but exhibits a sharp accuracy drop under partial observability bounded by: $$\text{Acc}(T_\theta) \le \max\{\text{Acc}(T^*_{A=0}), \text{Acc}(T^*_{A=1})\}$$
  • Decomposition Validation: In synthetic Gaussian experiments, $F_{DU}$ remains invariant ($0.017$) across varying thresholds, while total unfairness directly tracks changes in $F_{MU}$, validating that $F_U = F_{DU} + F_{MU}$ holds tightly under well-defined boundary conditions.
  • Exact Pareto Alignment: Using triangular distributions, they demonstrate that when group-specific Bayes optimal boundaries are aligned, classifiers achieve perfect accuracy and complete fairness ($F_U = 0$) simultaneously without any trade-off penalty.

Limitations and Future Work

  • Known Distributions Assumption: The derivations rely on knowing the true underlying data distributions, which is impossible in real-world deployment.
  • Metric and Task Scope: The mathematical guarantees are restricted to binary classification, binary sensitive attributes, and the Equalized Odds metric. Other criteria (such as Demographic Parity or Predictive Parity) and multi-class/continuous settings remain uncharacterized.
  • Absence of Real-World Benchmarks: While synthetic data validates the mathematical lemmas, validating how these bounds behave on high-dimensional, empirical datasets (e.g., tabular or vision benchmarks) is left to future research.

Summary updated

Abstract

While the accuracy-fairness trade-off has been frequently observed in the literature of fair machine learning, rigorous theoretical analyses have been scarce. To demystify this long-standing challenge, this work seeks to develop a theoretical framework by characterizing the shape of the accuracy-fairness trade-off Pareto frontier(FairFrontier), determined by a set of all optimal Pareto classifiers that no other classifiers can dominate. Specifically, we first demonstrate the existence of the trade-off in real-world scenarios and then propose four potential categories to characterize the important properties of the accuracy-fairness Pareto frontier. For each category, we identify the necessary conditions that lead to corresponding trade-offs. Experimental results on synthetic data suggest insightful findings of the proposed framework: (1) When sensitive attributes can be fully interpreted by non-sensitive attributes, FairFrontier is mostly continuous. (2) Accuracy can suffer a \textit{sharp} decline when over-pursuing fairness. (3) Eliminate the trade-off via a two-step streamlined approach. The proposed research enables an in-depth understanding of the accuracy-fairness trade-off, pushing current fair machine-learning research to a new frontier.
BibTeX
@misc{tang2023theoretical,
  author = {Hua Tang and Lu Cheng and Ninghao Liu and Mengnan Du},
  title = {{A Theoretical Approach to Characterize the Accuracy-Fairness Trade-off Pareto Frontier}},
  year = {2023},
  eprint = {2310.12785},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.12785},
}

Loading related content...

Figure