An Empirical Study of Rich Subgroup Fairness for Machine Learning

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

TL;DR

This paper provides the first major empirical validation of "rich subgroup fairness," a framework designed to prevent "fairness gerrymandering"—where a model appears fair on broad groups (like race or gender) but remains biased against specific intersections (like older women of a specific ethnicity). The authors demonstrate that a game-theoretic algorithm can effectively protect thousands of subgroups in real-world datasets with only a marginal cost to predictive accuracy.

What Problem Does This Paper Address?

Most machine learning fairness research focuses on "marginal" fairness—ensuring that a model’s error rates are roughly equal across a few protected categories, such as Race or Gender. However, the authors highlight a phenomenon called fairness gerrymandering.

Imagine a classifier that is perfectly fair to "Men" and "Women" as broad groups, and fair to "Blue people" and "Green people." It sounds fair, right? But what if that same model is extremely biased against "Blue Women" and "Green Men"? By balancing the averages, the model "hides" its unfairness in the intersections. Traditional statistical definitions are too coarse to catch this. The challenge is that as you add more attributes (age, income, location), the number of possible subgroups explodes exponentially, making it computationally "hard" to protect all of them.

Methods

The authors evaluate the SUBGROUP algorithm, which treats fairness as a two-player zero-sum game:

  1. The Learner: Tries to find a model that minimizes prediction error while staying within fairness constraints.
  2. The Auditor: Acts as a "fairness bounty hunter." It searches through the exponentially large space of subgroups to find the one group that is being treated most unfairly by the Learner’s current model.

The algorithm proceeds in rounds (fictitious play). In each round, the Auditor finds a "certificate of unfairness" for a subgroup, and the Learner updates the model to be fairer to that specific group.

While the original theory required "perfect" mathematical oracles, this paper tests whether the algorithm still works when those oracles are replaced with fast heuristics (specifically, linear regression models). This is a crucial bridge from "math theory" to "engineering reality."

Datasets

The study uses four real-world datasets where fairness is a known concern:

  • Communities and Crime: Predicting high violent crime rates in U.S. communities.
  • Law School: Predicting whether a student will pass the bar exam.
  • Student: Predicting academic performance based on social and demographic factors.
  • Adult: Predicting whether an individual’s income exceeds $50k/year.

The authors preprocessed these to ensure balanced labels and used one-hot encoding for categorical variables.

Key Insights and Ideas

  • Fairness Gerrymandering is Real: The authors proved that if you only optimize for marginal fairness (e.g., just race or just gender), you often end up with models that are significantly unfair to subgroups. Subgroup fairness doesn't happen "for free."
  • Heuristics are "Good Enough": One of the most surprising findings is that even though the algorithm’s theoretical guarantees rely on perfect optimization, using simple linear heuristics actually leads to convergence in practice.
  • The "Steep Drop" Phenomenon: On several datasets, the authors found a "sweet spot" where they could drastically reduce subgroup unfairness with almost zero increase in the model's error rate. You don't always have to sacrifice much accuracy to be fair.
  • Visualizing the "Flattening": The paper uses "discrimination heatmaps" to show how the algorithm works. Initially, the "surface" of unfairness is jagged and peaky; as the algorithm runs, it "flattens" the surface until no single subgroup stands out as being mistreated.

Key Results

  • Pareto Frontiers: The authors mapped the tradeoff between error and unfairness. In the Communities and Crime dataset, they reduced the "unfairness score" from 0.026 to less than 0.005 while only increasing the error rate from 12% to 16%.
  • Comparison to Marginal Methods: They compared their approach to the state-of-the-art "Marginal" algorithm (Agarwal et al., 2018). While the Marginal algorithm succeeded in making the broad groups look fair, it left the subgroups unprotected in 3 out of 4 datasets. The SUBGROUP algorithm consistently outperformed it on intersectional fairness.
  • Convergence: Despite the complexity of the task, the algorithm typically converged within a few thousand iterations on most datasets.

Limitations and Future Work

  • Model Complexity: This study focused primarily on linear classifiers and linear subgroup definitions. The authors note that using richer model classes (like deep neural networks) for the Learner might yield even better results but could make the Auditor’s job much harder.
  • Generalization: The results reported are "in-sample" (on the training data). While VC-dimension theory suggests these results should generalize to new data, the authors suggest that empirical "test-set" Pareto curves are a necessary next step.
  • Randomization: The current deterministic version of the algorithm is easier to implement, but the authors are interested in testing a "no-regret" randomized version that might offer even stronger theoretical stability.

Summary updated

Abstract

Kearns, Neel, Roth, and Wu [ICML 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, Beygelzeimer, Dudik, Langford, and Wallach [ICML 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.
BibTeX
@inproceedings{kearns2019empirical,
  author = {Michael J. Kearns and Seth Neel and Aaron Roth and Zhiwei Steven Wu},
  title = {{An Empirical Study of Rich Subgroup Fairness for Machine Learning}},
  booktitle = {FAT},
  year = {2019},
  doi = {10.1145/3287560.3287592},
}

Loading related content...

Figure