Abstract
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.
Introduction: The Problem of Fairness Gerrymandering
Traditional machine learning fairness research often focuses on "marginal" fairness—ensuring that error rates are balanced across a few broad protected categories, such as Race or Gender. However, this approach is susceptible to fairness gerrymandering, a phenomenon where a model appears fair on broad groups but remains significantly biased against specific intersectional subgroups (e.g., older women of a specific ethnicity).
As the number of protected attributes (age, income, location, etc.) increases, the number of possible subgroups grows exponentially. This complexity makes it computationally difficult to protect all subgroups using traditional statistical definitions.
Methodology: The SUBGROUP Algorithm
To address this, the authors evaluate the SUBGROUP algorithm, which frames fairness as a two-player zero-sum game:
- The Learner: Attempts to find a model that minimizes prediction error while adhering to fairness constraints.
- The Auditor: Acts as a "fairness bounty hunter," searching the exponentially large space of subgroups to identify the group most unfairly treated by the Learner’s current model.
The algorithm proceeds through rounds of fictitious play. In each round, the Auditor provides a "certificate of unfairness" for a specific subgroup, prompting the Learner to update the model. While theoretical guarantees originally required perfect mathematical oracles, this study investigates whether the algorithm remains effective when these are replaced with fast linear heuristics.
Experimental Setup
The study utilizes four real-world datasets where fairness is a critical concern:
- Communities and Crime: Predicting violent crime rates in U.S. communities.
- Law School: Predicting bar exam success.
- Student: Predicting academic performance.
- Adult: Predicting income levels.
Categorical variables were one-hot encoded, and labels were preprocessed to ensure balance.
Results and Discussion
The empirical results confirm that subgroup fairness is not achieved "for free" by optimizing for marginal fairness. Comparison with the "Marginal" algorithm (Agarwal et al., 2018) showed that while broad groups might appear fair, intersectional subgroups often remained unprotected.
Convergence and Tradeoffs
A key finding is the algorithm's practical convergence. Despite the theoretical requirement for perfect optimization, the use of simple linear heuristics led to stable convergence within a few thousand iterations on most datasets.
The authors also identified a "Pareto frontier" between error and unfairness. In many cases, a "steep drop" in unfairness was achievable with only a marginal increase in error. For example, in the Communities and Crime dataset, subgroup unfairness was reduced by over 80% with only a 4% increase in the error rate.
Conclusion
This empirical study validates "rich subgroup fairness" as a viable and effective framework for real-world machine learning. The SUBGROUP algorithm, even when implemented with heuristics, successfully protects thousands of intersectional subgroups with manageable costs to predictive accuracy. Future work will explore richer model classes and the generalization of these fairness guarantees to unseen test data.
Summary updated