An Empirical Study of Rich Subgroup Fairness for Machine Learning
Empirical validation of Kearns et al.'s rich subgroup fairness algorithm on four real datasets, demonstrating quick convergence and favorable fairness-accuracy tradeoffs.
Key Findings
Methodology
Using Kearns et al.'s [2018] rich subgroup fairness framework, the study employs a game-theoretic formulation with cost-sensitive classification (CSC) to optimize classifiers under subgroup fairness constraints. The algorithm models the problem as a two-player zero-sum game, where the learner chooses hypotheses from H and the auditor identifies the most unfair subgroups from G. Heuristic approximations replace theoretical oracles for practical efficiency. Experiments on four datasets—Law School, Communities and Crime, Adult, and Student—assess convergence, fairness-accuracy tradeoffs, and compare with Agarwal et al.'s [2018] marginal fairness approach.
Key Results
- Across datasets, the algorithm converges rapidly within thousands of iterations, achieving substantial fairness improvements with minimal accuracy loss. For example, on Law School, fairness violations decrease significantly within a few thousand rounds, with errors increasing by only a few percentage points. On the Adult dataset, convergence is slower, requiring up to 180,000 iterations, but fairness gains remain notable. The Pareto frontiers reveal non-linear tradeoffs, with regions where fairness improves sharply at low accuracy costs.
- Rich subgroup fairness consistently outperforms marginal fairness in reducing subgroup bias, especially in datasets with complex protected attribute intersections. The marginal fairness algorithm often fails to control subgroup bias, highlighting the importance of the richer definition. In some cases, marginal fairness models even underperform compared to unconstrained classifiers in subgroup fairness metrics.
- Visualizations of the optimization trajectory show that the algorithm effectively balances error and fairness, with the fairness violation decreasing monotonically in most cases. The empirical results validate the theoretical guarantees, demonstrating that the approach is practical and scalable for real-world fairness challenges.
Significance
This work advances the field by translating the theoretical rich subgroup fairness framework into practical algorithms capable of handling complex, real-world data. It addresses the critical gap between coarse statistical fairness and fine-grained subgroup fairness, which is essential for deploying fair AI systems in sensitive domains like criminal justice, finance, and employment. The empirical success on diverse datasets underscores the feasibility of implementing such fairness constraints without prohibitive costs, paving the way for more equitable machine learning applications.
Technical Contribution
The study introduces a game-theoretic optimization approach that leverages cost-sensitive classification to efficiently approximate solutions under rich subgroup fairness constraints. It extends prior work by empirically validating the convergence and effectiveness of heuristic-based algorithms in realistic settings. The combination of theoretical insights and practical heuristics offers a new paradigm for scalable, fine-grained fairness optimization, bridging the gap between theory and application. The approach also provides a framework for auditing subgroup fairness violations, enabling targeted interventions.
Novelty
This is the first comprehensive empirical validation of Kearns et al.'s rich subgroup fairness framework on real datasets, demonstrating its practicality beyond theoretical guarantees. Unlike traditional marginal fairness methods, this approach explicitly enforces fairness across exponentially many subgroups, capturing complex intersectional biases. The innovative use of a game-theoretic formulation combined with heuristic CSC solvers distinguishes it from prior work, offering a scalable solution to a previously intractable problem.
Limitations
- The reliance on heuristic approximations for learning and auditing may lead to suboptimal convergence or fairness violations in some cases. Large datasets with high-dimensional features pose computational challenges.
- The definition of rich subgroups based on VC dimension can lead to exponential growth in subgroup count, complicating interpretability and model complexity.
- Current experiments are limited to in-sample evaluations; generalization to unseen data remains to be rigorously tested. Future work should address robustness and scalability in broader settings.
Future Work
Future research will focus on developing more efficient algorithms with provable convergence guarantees, extending the framework to non-linear models and deep learning architectures. Automating subgroup definition and improving interpretability are key directions. Additionally, integrating online learning and dynamic environments will enhance real-world applicability. Exploring broader fairness notions, such as calibration and metric fairness, within this rich subgroup paradigm also presents promising avenues.
AI Executive Summary
Fairness in machine learning remains a pressing challenge, especially when addressing intersectional biases across diverse subgroups. Traditional statistical fairness metrics often overlook nuanced biases, risking unfair treatment of minority groups. To bridge this gap, Kearns et al. [2018] introduced the concept of rich subgroup fairness, which seeks to enforce fairness constraints over an exponentially large collection of subgroups defined by functions with bounded VC dimension. This approach aims to ensure that fairness is not just a coarse average but holds at a granular level, capturing complex intersectional biases.
Building on this theoretical foundation, the current study empirically evaluates the practical viability of the rich subgroup fairness algorithm. Using a game-theoretic formulation, the method models the problem as a two-player zero-sum game, where the learner aims to minimize classification error while satisfying subgroup fairness constraints, and the auditor identifies the most unfair subgroups. The algorithm employs cost-sensitive classification (CSC) heuristics to approximate solutions efficiently, replacing ideal oracles with fast heuristics for real-world applicability.
Experiments on four diverse datasets—Law School, Communities and Crime, Adult, and Student—demonstrate that the algorithm converges quickly in most cases, often within thousands of iterations. The results reveal that substantial fairness improvements can be achieved with only modest increases in error, validating the approach's effectiveness. Visualizations of the optimization process show consistent balancing of fairness and accuracy, with Pareto frontiers illustrating the non-linear tradeoffs involved.
Comparative analysis with Agarwal et al.'s marginal fairness algorithm highlights that rich subgroup fairness provides significantly better control over subgroup biases. Marginal fairness models often fail to prevent biases in intersectional subgroups, underscoring the importance of the richer definition. These findings suggest that implementing rich subgroup fairness in practice is both feasible and beneficial, especially in sensitive applications like criminal justice and finance.
The study concludes that rich subgroup fairness is a promising paradigm for equitable AI. While current methods face computational and interpretability challenges, ongoing research aims to improve scalability, automate subgroup definitions, and extend to complex models. Overall, this work marks a significant step toward deploying fairer machine learning systems that recognize and address the multifaceted nature of bias in society.
Deep Dive
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.