An Empirical Study of Rich Subgroup Fairness for Machine Learning

Michael Kearns; Seth Neel; Aaron Roth; Zhiwei Steven Wu

Source-linked AI summary

An Empirical Study of Rich Subgroup Fairness for Machine Learning

Michael Kearns, Seth Neel, Aaron Roth, Zhiwei Steven Wu

arXiv:1808.08166v1Aug 24, 2018cs.LGstat.ML

TL;DR

The paper asks whether rich subgroup fairness is empirically necessary and practical beyond marginal fairness constraints. It evaluates the Kearns et al. algorithm with heuristic oracles on four real datasets and finds rapid convergence, favorable fairness–accuracy trade-offs, and substantial subgroup unfairness under marginal fairness alone.

Problem
The paper investigates whether fairness gerrymandering occurs on real data and whether rich subgroup fairness is too costly or unnecessary compared with marginal fairness.
Method
The paper experimentally evaluates Kearns et al.’s SUBGROUP algorithm with fast heuristic learning oracles on four real datasets, comparing it with Agarwal et al.’s MARGINAL algorithm.
Results
The algorithm typically converges, supports appealing fairness–accuracy compromises, and reveals substantial subgroup unfairness in models optimized only for marginal fairness.
Takeaways & Limitations
Rich subgroup fairness is empirically effective and can be satisfied at reasonable computational and accuracy costs, making it a viable practical fairness notion.
Takeaways & Limitations
The heuristic Auditor has no theoretical guarantees and may miss larger subgroup disparities, making detected unfairness only a lower bound on true unfairness.

Abstract

from arXiv · show

Kearns et al. [2018] recently proposed a notion of rich subgroup fairness intended to bridge the gap between statistical and individual notions of fairness. Rich subgroup fairness picks a statistical fairness constraint (say, equalizing false positive rates across protected groups), but then asks that this constraint hold over an exponentially or infinitely large collection of subgroups defined by a class of functions with bounded VC dimension. They give an algorithm guaranteed to learn subject to this constraint, under the condition that it has access to oracles for perfectly learning absent a fairness constraint. In this paper, we undertake an extensive empirical evaluation of the algorithm of Kearns et al. On four real datasets for which fairness is a concern, we investigate the basic convergence of the algorithm when instantiated with fast heuristics in place of learning oracles, measure the tradeoffs between fairness and accuracy, and compare this approach with the recent algorithm of Agarwal et al. [2018], which implements weaker and more traditional marginal fairness constraints defined by individual protected attributes. We find that in general, the Kearns et al. algorithm converges quickly, large gains in fairness can be obtained with mild costs to accuracy, and that optimizing accuracy subject only to marginal fairness leads to classifiers with substantial subgroup unfairness. We also provide a number of analyses and visualizations of the dynamics and behavior of the Kearns et al. algorithm. Overall we find this algorithm to be effective on real data, and rich subgroup fairness to be a viable notion in practice.

1 Introduction

The paper evaluates whether rich subgroup fairness addresses fairness gerrymandering in practice, using heuristic implementations of the Kearns et al. algorithm across four real datasets. It finds that the algorithm generally converges, offers favorable fairness–accuracy compromises, and exposes subgroup unfairness left by marginal fairness.

Motivation: Standard statistical fairness constraints equalize metrics across a small number of protected groups but provide limited individual-level guarantees.Common metrics include positive classification, false positive, false negative, and positive predictive rates.
Motivation: Fairness gerrymandering can cause standard approaches to violate subgroup fairness even when false positive rates are equalized across marginal protected attributes.The paper describes this failure as arising naturally without malicious intent.
Approach: Rich subgroup fairness extends statistical constraints from a few coarse groups to a combinatorially or infinitely large collection of subgroups defined by functions of protected attributes.The paper highlights conjunctions or intersections of protected attributes as one example.
Empirical evaluation: Across four real datasets, the heuristic Kearns et al. algorithm typically converges and provides a controllable trade-off between fairness and accuracy.The study also visualizes optimization trajectories and subgroup-discrimination heatmaps over time.
Empirical evaluation: Each dataset exhibits appealing compromises between error and subgroup fairness, suggesting rich subgroup fairness can be achieved without a severe accuracy loss.The paper compares these outcomes with models trained under marginal fairness constraints.
Comparison and conclusion: Auditing marginal-fairness models reveals substantial subgroup unfairness, supporting explicit enforcement of subgroup rather than only marginal fairness.The paper concludes that rich subgroup fairness is effective on real data and viable in practice.

2 Definitions

The paper defines subgroup fairness as a statistical constraint applied across groups represented by protected-attribute indicators. Its SUBGROUP algorithm alternates learner and auditor best responses in a zero-sum game, using cost-sensitive classification and heuristic implementations in experiments.

Data and classifiers: The data model separates protected attributes x from unprotected attributes x′, jointly forming X, with labeled points drawn independently from an unknown distribution P.A binary classifier D may induce randomized predictions D(X).
False positive fairness: For false positive fairness, the constraint compares each subgroup’s false positive rate with the classifier’s overall false positive rate within tolerance γ.FP(D) is the overall rate, while FP(D,g) is the rate among group g and negative-label individuals.
Subgroup fairness: Subgroup fairness requires the chosen statistical constraint to hold across combinatorially many groups definable by protected attributes, rather than only coarse groups.Groups are represented by indicator functions g in a family G, where g(x)=1 denotes membership.
Auditing: A subgroup g witnessing violation of γ-subgroup fairness is a γ-unfair certificate, and an auditor either declares fairness or produces such a certificate.Auditing uses sampled points and the classifier’s outcomes.
Experimental implementation: The experiments use linear threshold functions for H and G, with linear regression heuristics used for both learning and auditing.The regression heuristic predicts the costs of labels 0 and 1 and chooses the label with lower predicted cost.
SUBGROUP algorithm: SUBGROUP formulates error minimization under subgroup-fairness constraints as a two-player zero-sum game between a Learner choosing hypotheses H and an Auditor choosing subgroups G.The Learner balances error and previously found violations, while the Auditor searches for the most violated subgroup.
SUBGROUP algorithm: Both players’ best-response problems reduce to cost-sensitive classification, and the algorithm simulates fictitious play through alternating learner and auditor rounds.Efficient execution assumes cost-sensitive classification oracles for H and G.

3 Empirical Evaluation

Across four datasets, the SUBGROUP algorithm generally converges or remains useful for searching accuracy–fairness tradeoffs, with rich subgroup fairness often achievable at modest accuracy cost. Compared with MARGINAL, it usually provides substantially better subgroup fairness, although convergence and dataset-specific tradeoffs vary.

Empirical convergence: The algorithm typically converges on Communities and Crime and Law School, but less cleanly on Adult and Student.With imperfect Learner and Auditor heuristics, convergence guarantees are heuristic; Adult still yields useful accuracy–fairness pairs despite nonconvergence.
Accuracy–fairness tradeoff: The SUBGROUP algorithm produces appealing Pareto frontiers, including regions where subgroup unfairness drops substantially with negligible error increases.The frontier summarizes the accuracy–subgroup-fairness tradeoff, while the preferred operating point depends on domain experts, stakeholders, and application stakes.
Comparison with marginal fairness: MARGINAL performs well on marginal fairness but is much worse on subgroup fairness for three datasets, so marginal fairness generally does not imply subgroup fairness.Matching the marginal and subgroup plots shows a systematic relationship except on Student, but MARGINAL reduces subgroup unfairness less than SUBGROUP.
Overall findings: Overall, subgroup fairness is strong but achievable on these datasets, and SUBGROUP appears effective for investigating it.The actual accuracy range varies substantially, from nearly 10% on Communities and Crime to less than 2% on Student.
Dataset-specific results: Communities and Crime reduces γ-unfairness from 0.026 to less than 0.005 while increasing error from 0.12 to 0.16.The curve later flattens, making additional unfairness reductions increasingly costly in accuracy.
Dataset-specific results: Law School shows an approximately linear SUBGROUP frontier, while MARGINAL lies close to it and appears to yield subgroup fairness for free.Adult instead exhibits both steep inexpensive and flat costly regions, alongside poorer convergence.
Dataset-specific results: On Student, SUBGROUP reduces γ-unfairness to 0 with a 2% error increase, whereas MARGINAL reaches only 0.002 with an over 3% increase.Student is also the only dataset where reducing marginal fairness has no relationship to subgroup fairness.

4 Conclusions

The paper finds rich subgroup fairness empirically effective on four fairness-sensitive datasets, while identifying several directions for further experimental work. These include richer learner classes, a no-regret implementation, and test-set generalization studies.

The study establishes the empirical efficacy of rich subgroup fairness and the SUBGROUP algorithm on four fairness-sensitive datasets.
Richer learner model classes H could produce more appealing fairness–accuracy Pareto curves, while keeping the auditor class G relatively simple.The authors want G to retain an intuitive interpretation of the subgroups.
A no-regret implementation of Kearns et al. may offer superior convergence and other properties because of its stronger theoretical guarantees.
Test-set Pareto-curve experiments could assess subgroup-fairness generalization beyond the training data.Standard VC theory provides worst-case bounds, but the authors expect potentially better empirical generalization.

A Details of the SUBGROUP algorithm

The SUBGROUP method formulates fair empirical risk minimization as a learner–auditor zero-sum game and uses cost-sensitive classification oracles for both hypothesis and subgroup classes. The investigated FairFictPlay variant has simpler per-step dynamics but weaker convergence guarantees than the randomized oracle-efficient algorithm.

The Fair ERM objective minimizes classification error over a distribution of hypotheses subject to subgroup false-positive-rate fairness constraints.The formulation assumes access to cost-sensitive classification oracles for both H and G.
Kearns et al. prove an oracle-efficient algorithm that approximately achieves optimal error and bounded fairness violations with high probability.Its guarantees require accuracy parameters ν, δ and access to CSC(H) and CSC(G).
The paper instead studies FairFictPlay because the randomized theorem algorithm is less amenable to empirical investigation.FairFictPlay has simple per-step dynamics but convergence guarantees only after an exponential rather than polynomial number of steps.
Each round lets the learner best-respond using CSC(H), while the auditor best-responds using CSC(G) against the empirical distribution of previously generated classifiers.The final output is the empirical distribution over classifiers accumulated during play.
The classes G(S) and H(S) are the labelings on the sample induced by subgroup functions G and hypotheses H.
For fixed dual variables, the learner’s cost vector LC(λ) assigns the costs used to find a best-response classifier through cost-sensitive classification.