Source-linked AI summary
A Reductions Approach to Fair Classification
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, Hanna Wallach
TL;DR
Fair classification must balance prediction accuracy with constraints tied to protected attributes. The paper reduces this problem to cost-sensitive classification using black-box learners, obtaining randomized classifiers with favorable fairness–accuracy performance while retaining broad applicability.
Problem
The paper studies binary classification subject to fairness constraints with respect to a predefined protected attribute such as race or sex.
Method
The approach reduces fair classification to a sequence of cost-sensitive classification problems while treating the underlying classifier as a black box.
Results
The reductions yield randomized classifiers with the lowest empirical error subject to the desired fairness constraints and compare favorably to prior baselines.
Takeaways & Limitations
The reductions support any classifier representation, encompass many fairness definitions, provide provable guarantees, and work well in practice.
Takeaways & Limitations
The approach requires training-time access to protected attributes, and guarantees can become vacuous when multiple fairness definitions are mutually contradictory.
Abstract
from arXiv · showhide
We present a systematic approach for achieving fairness in a binary classification setting. While we focus on two well-known quantitative definitions of fairness, our approach encompasses many other previously studied definitions as special cases. The key idea is to reduce fair classification to a sequence of cost-sensitive classification problems, whose solutions yield a randomized classifier with the lowest (empirical) error subject to the desired constraints. We introduce two reductions that work for any representation of the cost-sensitive classifier and compare favorably to prior baselines on a variety of data sets, while overcoming several of their disadvantages.
1. Introduction
The paper addresses binary classification under fairness constraints and proposes a general black-box reductions approach that supports broad fairness definitions while improving on prior methods’ limitations.
- Fair classification seeks accurate binary predictions subject to constraints involving a predefined protected attribute such as race or sex.
- Existing classifier-specific methods often rely on relaxed fairness constraints, strong distributional assumptions, or restricted model families.
- Existing black-box wrappers avoid restricting classifier families but can be tied to particular fairness definitions, fail to find the most accurate fair classifier, or require protected attributes at test time.
- The proposed approach treats the underlying classifier as a black box, supports fairness definitions expressible as linear inequalities on conditional moments, and reduces the task to sequential cost-sensitive classification.
- Solutions to the cost-sensitive problems yield a randomized classifier with the lowest empirical error subject to the desired fairness constraints.
- The experiments report that the reductions compare favorably with three baselines while overcoming some of their disadvantages, and the approach is presented as algorithmic with finite-sample guarantees rather than only asymptotic analysis.
2. Problem Formulation
The formulation learns accurate binary classifiers under fairness constraints represented by conditional moments and linear inequalities. It permits randomized classifiers and empirical optimization to trade accuracy against fairness using finite data.
- 2. Problem Formulation: Training examples are triples (X, A, Y), where X is a feature vector, A a protected attribute, and Y a binary label; classifiers in H do not explicitly depend on A.
- 2.2. Fair Classification: The objective is to learn an accurate classifier from a family such as linear threshold rules, decision trees, or neural networks while satisfying a fairness definition.
- 2.1. Fairness Definitions: Demographic parity requires prediction rates conditional on each protected-attribute value to equal the overall prediction rate.
- 2.1. Fairness Definitions: Equalized odds requires predictions to be conditionally independent of the protected attribute given the label, equivalently matching conditional prediction moments across groups.
- 2.1. Fairness Definitions: Both fairness definitions are represented as linear constraints on a vector of conditional moments, with matrices and vectors specifying the constraints.
- 2.1. Fairness Definitions: Many other fairness definitions fit the same representation, but calibration and predictive parity do not because their required events depend on the classifier.
- 2.2. Fair Classification: Randomized classifiers are distributions over H, and they can achieve accuracy–fairness tradeoffs unavailable to individual deterministic classifiers.
- 2.2. Fair Classification: Because the true distribution is unknown, the optimization replaces true error and moments with empirical versions and permits constraint tolerances based on sampling error.
3. Reductions Approach
The reductions approach casts fair classification as a constrained saddle-point problem whose best responses are cost-sensitive classification tasks. Its randomized classifier achieves near-optimal feasible error while approximately satisfying fairness constraints, with optimization and statistical errors explicitly bounded.
- Reduction to cost-sensitive classification: Fair classification is reduced to a sequence of cost-sensitive classification problems whose solutions produce a randomized classifier with lowest empirical error under the desired constraints.The reduction assumes access to a cost-sensitive classification algorithm and supports general error functions through example-specific costs.
- Saddle-point formulation: The constrained optimization is formulated as a saddle-point problem with Lagrange multipliers for fairness constraints and an ℓ1-norm bound on those multipliers.The algorithm treats the classifier distribution and multipliers as two players and seeks an approximate equilibrium.
- Optimization procedure: Exponentiated gradient updates the multiplier player while the classifier player repeatedly computes a best response through cost-sensitive classification.The best multiplier response is either zero or concentrated on the most violated constraint, while the classifier response can place all mass on one classifier.
- Optimization guarantees: The optimization bound decreases with iterations as sqrt(log(|K| + 1) / t) and grows slowly with the number of fairness constraints.The bound also depends on the maximum constraint violation ρ and the multiplier norm bound B.
- Optimization guarantees: Achieving suboptimality ν may require up to 4ρ^2B^2 log(|K| + 1) / ν^2 iterations.Larger B brings the constrained problem closer to the original formulation but can require more iterations.
- Statistical guarantees: With suitable parameter settings, the returned randomized classifier has the lowest feasible classification error up to eO(n^-α) while approximately satisfying the fairness constraints.The true-distribution error combines optimization error, which grows linearly with ν, and statistical error, which grows as n^-α.
4. Experimental Results
The experiments evaluate exponentiated-gradient reductions for demographic parity and equalized odds against several baselines across multiple data sets. The reductions generally match or outperform baselines while offering flexible accuracy–fairness tradeoffs, though grid search has scalability limits for non-binary protected attributes.
- Experimental setup: The reductions are evaluated for demographic parity and equalized odds using test classification error and fairness-constraint violation.The study examines exponentiated-gradient reductions and also evaluates grid search in Appendix D.
- Experimental setup: The evaluation uses logistic regression and gradient-boosted decision trees as base classifiers across four randomly split data sets.Each data set uses 75% training examples and 25% test examples.
- Experimental setup: The returned randomized classifiers track the training Pareto frontier across a wide range of accuracy–fairness tradeoffs.The experiments vary ε from 0.001 to 0.1 and run Algorithm 1 across all k.
- Results: Across data sets, classification-error variation is much smaller than constraint-violation variation, with the largest relative error increase occurring on the Dutch census data set.Almost all approaches substantially reduce or remove disparity without much impact on accuracy.
- Results: The reduction generally dominates or matches baselines, while relabeling is often not Pareto optimal and reweighting often retains substantial disparity.Post-processing can achieve statistically indistinguishable-zero disparity but sometimes has higher error than the reduction at comparable disparity.
- Limitations: Grid search sometimes misses the lowest training disparities and becomes prohibitively costly when the protected attribute has four values.For adult4, it would require three dimensions for demographic parity and six for equalized odds.
5. Conclusion
The paper concludes that its two reductions provide a broadly applicable and empirically effective route to fair binary classification. Their scope remains limited to one fairness definition at a time and requires training-time access to protected attributes.
- Conclusion: The paper presents two reductions that support any classifier representation, many fairness definitions, provable guarantees, and effective practical performance.The conclusion summarizes the reductions as applicable to binary classification.
- Conclusion: The reductions optimize the accuracy–fairness tradeoff for any single fairness definition when protected attributes are available during training.Fairness without training-time access and tradeoffs involving multiple fairness definitions remain open problems.
A. Error and Fairness for Randomized Classifiers
This section defines accuracy and fairness for deterministic and randomized classifiers through distributional error and conditional moments. Randomization extends the available accuracy–fairness tradeoffs.
- Definitions: A classifier’s accuracy is measured by its 0-1 error under the distribution over features, protected attributes, and labels.For randomized classifiers, the section extends the error definition to a distribution over classifiers.
- Definitions: Fairness constraints require the classifier’s conditional moments to satisfy linear inequalities of the form Mµ(h) ≤ c.For randomized classifiers, the moments are defined over the randomized prediction procedure.
B. Proof of Theorem 1
The proof analyzes the exponentiated-gradient reduction as a repeated game between classifier and constraint players. Regret bounds, best responses, and linearity establish the theorem’s saddle-point and convergence guarantees.
- Proof strategy: The proof applies standard Exponentiated Gradient analysis, which is equivalent here to Hedge.This supplies the regret bound used in the theorem.
- Technical construction: The auxiliary-coordinate construction preserves the regret analysis by embedding constraint vectors and maintaining the bound ∥r′_t∥∞ = ∥r_t∥∞ ≤ ρ.The associated vectors place remaining mass and a zero residual on the added coordinate.
- Convergence: The regret analysis bounds optimization error using the per-round constraint residuals and the exponentiated-gradient learning rate.The proof derives successive inequalities from regret, best-response optimality, and linearity in the players’ variables.
- Best responses: The classifier player’s best response minimizes the Lagrangian and can be obtained through a cost-sensitive classification reduction.Because the Lagrangian is linear in the classifier distribution, a best response can place all mass on one classifier.
- Convergence: Choosing the learning rate and requiring a sufficiently large number of iterations yields the theorem’s second guarantee.The stated iteration condition depends on ρ, B, |K|, and ν.
C. Proofs of Theorems 2 and 3
The proofs show that an approximate saddle point yields near-optimal empirical error and approximately satisfies empirical fairness constraints, which are then lifted to population guarantees through uniform concentration.
- Theorem 4: Theorem 4 analyzes any ν-approximate saddle point of the Lagrangian under empirical fairness constraints.Its proof relies on approximate complementary slackness and bounds for empirical error and constraint violation.
- Population guarantees: The proof obtains the population error comparison c err(bQ) ≤ c err(Q⋆) + 2ν before applying concentration bounds.Q⋆ minimizes population error subject to population fairness constraints.
- Empirical guarantees: The learned distribution has empirical error at most the error of any empirically feasible distribution plus 2ν.This is established by Lemma 2 through upper and lower bounds on the Lagrangian.
- Empirical guarantees: When empirical fairness constraints are feasible, the learned distribution approximately satisfies all of them.Lemma 3 supplies the corresponding empirical fairness-violation guarantee.
- Population guarantees: Uniform convergence transfers empirical error and fairness bounds to population quantities using Rademacher complexity and concentration of classifier moments.The analysis bounds generic moments, loss, conditional moments, and the resulting constraint deviations uniformly over the classifier class.
- Population guarantees: Conditional-moment concentration requires sufficient sample counts for each constraint event, with the proof using Chernoff bounds and a union bound.The final theorems combine these sample-count conditions with Theorem 4 and earlier results.
D. Additional Experimental Results
The appendix expands the experiments across training and test data, evaluating both reductions and interpolation extensions of reweighting and relabeling.
- Experimental scope: The appendix evaluates exponentiated-gradient and grid-search variants of the reductions on both training and test data.It also examines extensions of reweighting and relabeling beyond their originally prescribed tradeoffs.
- Training results: In training, Figure 2 plots classification error against DP and EO constraint violation and compares Pareto frontiers across methods.The exponentiated-gradient reduction dominates or matches other approaches because it solves for Pareto-frontier points in each classifier class.
- Test results: In testing, Figure 3 uses convex envelopes of training-frontier classifiers and finds exponentiated-gradient performance dominates or matches other methods up to statistical uncertainty.The figure reports confidence bands for classification error and confidence intervals for post-processing constraint violation.