Source-linked AI summary
Inherent Tradeoffs in Learning Fair Representations
Han Zhao, Geoffrey J. Gordon
TL;DR
The paper asks how much accuracy fair classification necessarily sacrifices, particularly when group base rates differ. It analyzes this through information-theoretic lower bounds and constructive randomized classifiers, extending the results to approximate parity and multiple groups. It also shows that close group-wise Bayes classifiers can support accuracy parity.
Problem
The paper addresses the unclear exact tradeoff between quantitative fairness constraints and accuracy in classification.
Method
The authors use information-theoretic analysis of fair classifiers and fair representations, plus a randomized construction with oracle access to Bayes classifiers and a linear program for multiple groups.
Results
The paper derives tight lower bounds on joint group-wise error, extends them to approximate statistical parity and finite multiple-group settings, and constructs an optimal fair randomized classifier.
Takeaways & Limitations
When group-wise Bayes optimal classifiers are close, learning fair representations can achieve accuracy parity, with error rates close across groups.
Takeaways & Limitations
The classifier is assumed not to use the protected attribute directly, although redundant encoding can still introduce bias.
Abstract
from arXiv · showhide
Real-world applications of machine learning tools in high-stakes domains are often regulated to be fair, in the sense that the predicted target should satisfy some quantitative notion of parity with respect to a protected attribute. However, the exact tradeoff between fairness and accuracy is not entirely clear, even for the basic paradigm of classification problems. In this paper, we characterize an inherent tradeoff between statistical parity and accuracy in the classification setting by providing a lower bound on the sum of group-wise errors of any fair classifiers. Our impossibility theorem could be interpreted as a certain uncertainty principle in fairness: if the base rates differ among groups, then any fair classifier satisfying statistical parity has to incur a large error on at least one of the groups. We further extend this result to give a lower bound on the joint error of any (approximately) fair classifiers, from the perspective of learning fair representations. To show that our lower bound is tight, assuming oracle access to Bayes (potentially unfair) classifiers, we also construct an algorithm that returns a randomized classifier that is both optimal (in terms of accuracy) and fair. Interestingly, when the protected attribute can take more than two values, an extension of this lower bound does not admit an analytic solution. Nevertheless, in this case, we show that the lower bound can be efficiently computed by solving a linear program, which we term as the TV-Barycenter problem, a barycenter problem under the TV-distance. On the upside, we prove that if the group-wise Bayes optimal classifiers are close, then learning fair representations leads to an alternative notion of fairness, known as the accuracy parity, which states that the error rates are close between groups. Finally, we also conduct experiments on real-world datasets to confirm our theoretical findings.
1. Introduction
The paper studies how fairness constraints trade off against classification accuracy, especially when groups have different base rates. It develops tight lower bounds, constructive fair classifiers, and a positive result for accuracy parity.
- Motivation: Different group base rates create an inherent tradeoff between statistical parity and accuracy.The paper frames this tradeoff as a limit applying to fair classifiers rather than merely a weakness of particular algorithms.
- Main results: The paper gives an information-theoretic, algorithm-independent lower bound on joint group-wise error under statistical parity.The bound applies when base rates differ between groups.
- Main results: Assuming oracle access to potentially unfair Bayes classifiers, the paper constructs a randomized classifier that is both accuracy-optimal and fair.This construction demonstrates tightness of the lower bound.
- Extensions: When groups number more than two, the lower bound lacks an analytic solution but can be computed efficiently through the TV-Barycenter linear program.The TV-Barycenter is defined as a barycenter problem under total variation distance.
- Main results: For approximate statistical parity, the authors derive a family of lower bounds quantifying the accuracy cost of the approximate constraint.This extends the tradeoff analysis beyond exact parity.
- Positive result: If group-wise Bayes optimal classifiers are close, learning fair representations supports accuracy parity, meaning similar error rates across groups.Experiments on a real-world dataset corroborate the paper’s positive and negative theoretical results.
2. Preliminaries
The preliminaries define the classification setting and fairness criteria, then introduce divergences used in the paper’s analysis. They distinguish demographic parity from accuracy parity and review related incompatibility results.
- Notation: The setup uses a joint distribution over input X, protected attribute A, and binary target Y, with classifiers unable to directly access A.The paper notes that fairness through blindness can still be biased because of redundant encoding.
- Notation: The base rate is the probability of a positive target, and base-rate difference measures the absolute gap between two distributions’ positive-label probabilities.The notation is used to compare groups with different outcome prevalences.
- Notation: A feature map g pushes the input distribution into a feature space, where a classifier h produces the prediction; identity g includes simple classifiers.This transformation supports the paper’s fair-representation formulation.
- Group Fairness: Demographic parity requires predictions to be independent of group membership, equivalently assigning positive outcomes at equal rates across groups.Its approximate version is measured by the demographic parity gap.
- Group Fairness: Accuracy parity requires equal error rates across groups and does not eliminate a perfect predictor when the target equals the protected attribute.This contrasts with demographic parity when group base rates differ.
- Group Fairness: Equalized odds matches positive prediction rates conditional on each target value, while equal opportunity matches them only for positive outcomes.Predictive rate parity instead equalizes positive-label probabilities conditional on predicted scores.
- Related results: With unequal base rates, prior work establishes incompatibility between equalized odds and predictive rate parity or calibration for non-perfect predictors.These results motivate the paper’s broader analysis of fairness constraints.
- Information theory: f-divergence measures differences between probability distributions; total variation is the only f-divergence listed here that is also a metric.The paper uses these information-theoretic concepts in its later tradeoff analysis.
3. Tradeoff between Fairness and Accuracy
The paper characterizes how demographic parity constrains accuracy, showing that differing group base rates impose algorithm-independent error lower bounds. It extends the analysis to multiple groups and classes through an efficiently solvable TV-Barycenter linear program.
- The paper asks how much accuracy fair classifiers must sacrifice and how this minimum error depends on coupling between targets and protected attributes.
- A Simple Example: In the binary example where Y = A and Bayes error is zero, every fair predictor has group-wise errors summing to at least 1, unlike an unfair perfect predictor.
- 3.1 An Accuracy Lower Bound for Fair Classifiers: Err_µ0(h ◦ g) + Err_µ1(h ◦ g) ≥ ∆BR(µ0, µ1) for every demographic-parity predictor, regardless of the feature transformation or classifier.The bound is tight in instances such as Y = A, and ∆BR reaches 1 exactly when Y and A are bijectively related.
- 3.1 An Accuracy Lower Bound for Fair Classifiers: The joint-error bound additionally scales with the zero-one entropy H0-1(A), which can be small for skewed group proportions and make joint accuracy conceal subgroup harm.
- 3.1 An Accuracy Lower Bound for Fair Classifiers: At least one subgroup incurs error ∆BR(µ0, µ1)/2, so larger base-rate differences force a larger worst-group error under demographic parity.
4. An Optimal Fair Classifier
The paper constructs a randomized classifier that achieves demographic parity while attaining the tight lower bound on joint group-wise error, assuming access to group-wise Bayes classifiers. This optimal fair-classifier problem is at least as hard as learning a Bayes-optimal classifier, and the construction requires explicit access to the protected attribute.
- Scope and limitation: The lower bound remains valid when classifiers explicitly access the protected attribute A.However, constructing an optimal classifier without such access remains an open question.
- Construction: Algorithm 1 returns a possibly randomized fair classifier for any distribution over (X, A, Y).The construction uses oracle access to the group-wise Bayes-optimal classifiers h*_0 and h*_1.
- Computational relationship: The optimal fair-classifier problem is at least as hard as learning a Bayes-optimal classifier.A reduction uses identical group-conditional distributions so that a fair optimal classifier also solves the Bayes-optimal problem.
- Optimality: The constructed classifier satisfies demographic parity and is optimal by attaining the lower bound from Theorem 8.The result is formalized in Theorem 14 and Corollary 15.
- Construction: For group base rates α and β, the optimal fair classifier randomizes decisions to equalize positive-outcome probabilities across groups.The proof uses an independent uniform random variable and assumes α ≥ β without loss of generality.
5. Approximate Fairness via Learning Fair Representations
The paper extends fairness–accuracy lower bounds to approximate demographic parity in learned representations using divergence-based information-theoretic arguments. Approximate parity can reduce, but does not eliminate, the inherent tradeoff between representation invariance and joint prediction error.
- Motivation: Limited discriminator capacity means that fair-representation methods generally achieve only approximate demographic parity in practice.The section therefore analyzes representation fairness through lower bounds on joint target-prediction error.
- Lower bounds: Theorem 18 gives total variation, Jensen–Shannon, and Hellinger lower bounds on joint error under divergence constraints on group representations.The assumptions compare representation divergences with divergences between the groups’ target distributions.
- Exact invariance: When representations are group-invariant, the lower bounds increase and reduce to the exact-demographic-parity result of Theorem 8.This follows from data processing, which equalizes the predictor distributions across groups.
- Approximate parity: If dTV(g♯µ0, g♯µ1) ≤ ϵ, then the DP gap is at most ϵ and joint error is at least ∆BR(µ0, µ1) − ϵ.This is Corollary 19’s quantitative reconciliation between approximate fairness and accuracy.
- Limitation: The lower bound is only a necessary condition for small joint error, so it does not provide a sufficient guarantee.The paper leaves open whether a small-error guarantee can keep the DP gap no larger than that of the perfect predictor.
6. Fair Representations Lead to Accuracy Parity
The paper shows that group-invariant representations can support accuracy parity when group-wise Bayes-optimal decisions are similar. An error-decomposition theorem bounds cross-group accuracy discrepancy using noise, representation distance, and Bayes-classifier discrepancy.
- Error components: The analysis treats Bayes error as unavoidable noise arising from stochastic group-conditional distributions.For binary classifiers, disagreement probabilities can be expressed through expected absolute prediction differences.
- Error decomposition: Theorem 20 bounds accuracy discrepancy by group-wise noise, representation distance, and discrepancy between group-wise Bayes-optimal classifiers.The bound applies to any hypothesis in the considered hypothesis class.
- Accuracy parity: If group-wise Bayes-optimal decisions are close, minimizing dTV(µ0(X), µ1(X)) with group-invariant representations suffices to guarantee accuracy parity.Accuracy parity means that error rates are close between groups.
- Scope and caveat: Representation learning must also avoid sharply increasing the noise term or the discrepancy between optimal decision functions.Changing the representation can alter both quantities in the decomposition bound.
7. Empirical Results
Experiments on the UCI Adult dataset test adversarial debiasing for group-invariant representations and show the predicted fairness–accuracy tradeoff. Increasing adversarial emphasis improves demographic parity while increasing joint error, with accuracy parity improving more slowly.
- Experimental setup: The UCI Adult experiment uses gender as the binary sensitive attribute for income prediction from 114 processed features.The dataset contains 30,162 training instances and 15,060 test instances.
- Experimental setup: AdvDebias differs from NoDebias only by adding an adversarial classification loss for predicting the sensitive attribute, while other training factors remain fixed.The controlled comparison fixes learning rate, optimizer, epochs, and batch size.
- Results and analysis: As adversarial-loss coefficient ρ increases, both overall error Err_μ and joint error Err_μ0 + Err_μ1 increase.Joint error is insensitive to imbalance in the sensitive attribute, whereas overall error is sensitive to its marginal distribution.
- Results and analysis: As ρ increases, demographic-parity gap ΔDP(Ŷ) decreases drastically, while group-error difference |Err_μ0 − Err_μ1| decreases more slowly.The slower accuracy-parity improvement is attributed to data noise and shifts between group-wise optimal decision functions.
- Results and analysis: The empirical results are consistent with the paper’s theoretical findings about fairness and accuracy.Table 2 reports demographic parity, joint error across groups, and accuracy parity.
8. Related Work
Related work studies fairness through tradeoff analysis, regularization, and representation learning. The paper situates its classification results alongside regression barycenter analyses and work showing that fairness constraints can improve accuracy under specific sampling-bias assumptions.
- Tradeoff between fairness and accuracy: Prior work has empirically observed an inherent tradeoff between accuracy and statistical parity, but precise characterizations remain less explored.The cited literature spans classification and regression settings.
- Tradeoff between fairness and accuracy: For regression with ℓ2 loss and sensitive-attribute access, prior analyses characterize the price of statistical parity using the W2 barycenter of group distributions.The paper presents its classification result as complementary to this line of work.
- Tradeoff between fairness and accuracy: Under labeling bias, Equality of Opportunity can help recover the Bayes optimal classifier, showing that fairness constraints may improve accuracy under particular data-generating assumptions.The paper distinguishes these results from its assumption-free focus on statistical parity and accuracy parity.
- Regularization techniques: Fairness-aware regularization includes prejudice-remover methods because deleting sensitive features alone may not eliminate bias when attributes correlate with sensitive information.This work traces that regularization line to Kamishima et al. (2012).
- Fair representations: Fair-representation methods seek representations that support accurate prediction while obfuscating protected-group membership.This competing-objectives formulation underlies representation-learning approaches to group and individual fairness.
9. Discussion and Conclusion
The paper establishes lower bounds on the accuracy cost of statistical parity and constructs a fair classifier attaining that bound under oracle access to Bayes classifiers. It also gives a polynomial-time multi-group computation, an accuracy-parity result under close group-wise Bayes classifiers, and empirical confirmation.
- Discussion and conclusion: When group base rates differ, any method satisfying statistical parity faces an information-theoretic lower bound on joint error, including under approximate parity.The bound is algorithm-independent and concerns accuracy across population groups.
- Discussion and conclusion: With oracle access to potentially unfair Bayes classifiers, the paper constructs a randomized classifier that is both accuracy-optimal and fair.This construction shows the lower bound is attainable under the stated oracle assumption.
- Discussion and conclusion: For more than two protected-attribute groups, the lower bound lacks an analytic form but is efficiently computable by a polynomial-time linear program called the TV-Barycenter problem.The result connects algorithmic-fairness tradeoffs with barycenter problems under total-variation distance.
- Discussion and conclusion: If group-wise Bayes optimal classifiers are close, learning fair representations leads to accuracy parity, meaning that group error rates are close.The paper reports empirical results on a real-world dataset that confirm its theoretical findings.