Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness

Abstract

The most prevalent notions of fairness in machine learning are statistical definitions: they fix a small collection of pre-defined groups, and then ask for parity of some statistic of the classifier across these groups. Constraints of this form are susceptible to intentional or inadvertent "fairness gerrymandering", in which a classifier appears to be fair on each individual group, but badly violates the fairness constraint on one or more structured subgroups defined over the protected attributes. We propose instead to demand statistical notions of fairness across exponentially (or infinitely) many subgroups, defined by a structured class of functions over the protected attributes. This interpolates between statistical definitions of fairness and recently proposed individual notions of fairness, but raises several computational challenges. It is no longer clear how to audit a fixed classifier to see if it satisfies such a strong definition of fairness. We prove that the computational problem of auditing subgroup fairness for both equality of false positive rates and statistical parity is equivalent to the problem of weak agnostic learning, which means it is computationally hard in the worst case, even for simple structured subclasses. We then derive two algorithms that provably converge to the best fair classifier, given access to oracles which can solve the agnostic learning problem. The algorithms are based on a formulation of subgroup fairness as a two-player zero-sum game between a Learner and an Auditor. Our first algorithm provably converges in a polynomial number of steps. Our second algorithm enjoys only provably asymptotic convergence, but has the merit of simplicity and faster per-step computation. We implement the simpler algorithm using linear regression as a heuristic oracle, and show that we can effectively both audit and learn fair classifiers on real datasets.

Added new experimental results and a slightly modified fairness definition

References in corpus (1)

• On the (im)possibility of fairness

Cited by in corpus (112)

• Prediction-Based Decisions and Fairness: A Catalogue of Choices, Assumptions, and Definitions
• Fairness in Machine Learning: A Survey
• 50 Years of Test (Un)fairness: Lessons for Machine Learning
• WILDS: A Benchmark of in-the-Wild Distribution Shifts
• Towards Out-Of-Distribution Generalization: A Survey
• A Clarification of the Nuances in the Fairness Metrics Landscape
• A Unified Approach to Quantifying Algorithmic Unfairness: Measuring Individual & Group Unfairness via Inequality Indices
• Learning Adversarially Fair and Transferable Representations
• An Empirical Characterization of Fair Machine Learning For Clinical Risk Prediction
• Contemporary Symbolic Regression Methods and their Relative Performance
• Auditing of AI: Legal, Ethical and Technical Approaches
• Identifying and Correcting Label Bias in Machine Learning
• The Butterfly Effect in Artificial Intelligence Systems: Implications for AI Bias and Fairness
• A Reductions Approach to Fair Classification
• Compositional Fairness Constraints for Graph Embeddings
• Exploring How Machine Learning Practitioners (Try To) Use Fairness Toolkits
• Towards Intersectionality in Machine Learning: Including More Identities, Handling Underrepresentation, and Performing Evaluation
• Empirical Risk Minimization under Fairness Constraints
• The US Algorithmic Accountability Act of 2022 vs. The EU Artificial Intelligence Act: What can they learn from each other?
• Online Learning with an Unknown Fairness Metric
• Differential Privacy Has Disparate Impact on Model Accuracy
• Aequitas: A Bias and Fairness Audit Toolkit
• Value Cards: An Educational Toolkit for Teaching Social Impacts of Machine Learning through Deliberation
• FlipTest: Fairness Testing via Optimal Transport
• Machine learning fairness notions: Bridging the gap with real-world applications
• Calibration for the (Computationally-Identifiable) Masses
• Fairness without Demographics through Adversarially Reweighted Learning
• Awareness in Practice: Tensions in Access to Sensitive Attribute Data for Antidiscrimination
• A survey on datasets for fairness-aware machine learning
• Probably Approximately Metric-Fair Learning
• Inherent Limitations of AI Fairness
• A Survey on Intersectional Fairness in Machine Learning: Notions, Mitigation, and Challenges
• Improving Fairness via Federated Learning
• Group Fairness: Independence Revisited
• Learning Certified Individually Fair Representations
• Average Individual Fairness: Algorithms, Generalization and Experiments
• Putting Fairness Principles into Practice: Challenges, Metrics, and Improvements
• Multiaccuracy: Black-Box Post-Processing for Fairness in Classification
• Algorithmic decision making methods for fair credit scoring
• Constrained Learning with Non-Convex Losses
• Toward Operationalizing Pipeline-aware ML Fairness: A Research Agenda for Developing Practical Guidelines and Tools
• Ensuring Fairness Beyond the Training Data
• Differentially Private Fair Learning
• Equalized odds postprocessing under imperfect group information
• Auditing and Achieving Intersectional Fairness in Classification Problems
• Adversarial training approach for local data debiasing
• Subverting machines, fluctuating identities: Re-learning human categorization
• What are the biases in my word embedding?
• SenSeI: Sensitive Set Invariance for Enforcing Individual Fairness
• Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints
• FairVis: Visual Analytics for Discovering Intersectional Bias in Machine Learning
• Rényi Fair Inference
• A Notion of Individual Fairness for Clustering
• Group Fairness in Prediction-Based Decision Making: From Moral Assessment to Implementation
• Fairness Hacking: The Malicious Practice of Shrouding Unfairness in Algorithms
• Environment Inference for Invariant Learning
• Modeling Techniques for Machine Learning Fairness: A Survey
• Two-Player Games for Efficient Non-Convex Constrained Optimization
• Regulatory Instruments for Fair Personalized Pricing
• Deontological Ethics By Monotonicity Shape Constraints
• Characterizing Intersectional Group Fairness with Worst-Case Comparisons
• Chasing Your Long Tails: Differentially Private Prediction in Health Care Settings
• Sample Complexity of Uniform Convergence for Multicalibration
• Removing Disparate Impact of Differentially Private Stochastic Gradient Descent on Model Accuracy
• To Split or Not to Split: The Impact of Disparate Treatment in Classification
• Vertical Allocation-based Fair Exposure Amortizing in Ranking
• Analysis of Trade-offs in Fair Principal Component Analysis Based on Multi-objective Optimization
• Learning Fair Rule Lists
• Metric-Free Individual Fairness in Online Learning
• Toward a better trade-off between performance and fairness with kernel-based distribution matching
• Improving Fairness of AI Systems with Lossless De-biasing
• Maximum Weighted Loss Discrepancy
• Technical Challenges for Training Fair Neural Networks
• A Sequentially Fair Mechanism for Multiple Sensitive Attributes
• Gerrymandering Individual Fairness
• Improving Fairness in Criminal Justice Algorithmic Risk Assessments Using Conformal Prediction Sets
• Group Fairness in Bandit Arm Selection
• Keeping Designers in the Loop: Communicating Inherent Algorithmic Trade-offs Across Multiple Objectives
• Preference-Informed Fairness
• Analyzing Fairness of Computer Vision and Natural Language Processing Models
• Statistical Discrimination in Ratings-Guided Markets
• Empirical Welfare Maximization with Constraints
• InfoFair: Information-Theoretic Intersectional Fairness
• From Soft Classifiers to Hard Decisions: How fair can we be?
• Fair Classification and Social Welfare
• Online Multivalid Learning: Means, Moments, and Prediction Intervals
• Intersectionality and Testimonial Injustice in Medical Records
• Pairwise Fairness for Ranking and Regression
• Multi-Differential Fairness Auditor for Black Box Classifiers
• Optimizing Generalized Rate Metrics through Game Equilibrium
• Metrics and methods for a systematic comparison of fairness-aware machine learning algorithms
• Balancing Competing Objectives with Noisy Data: Score-Based Classifiers for Welfare-Aware Machine Learning
• On the Impact of Data Quality on Image Classification Fairness
• Locating disparities in machine learning
• Probably Approximately Correct Constrained Learning
• Equal Confusion Fairness: Measuring Group-Based Disparities in Automated Decision Systems
• (Un)certainty of (Un)fairness: Preference-Based Selection of Certainly Fair Decision-Makers
• One-vs.-One Mitigation of Intersectional Bias: A General Method to Extend Fairness-Aware Binary Classification
• Fair for All: Best-effort Fairness Guarantees for Classification
• Everything is Relative: Understanding Fairness with Optimal Transport
• "And the Winner Is...": Dynamic Lotteries for Multi-group Fairness-Aware Recommendation
• Fairness Sample Complexity and the Case for Human Intervention
• On the Fairness of Randomized Trials for Recommendation with Heterogeneous Demographics and Beyond
• Outlining Traceability: A Principle for Operationalizing Accountability in Computing Systems
• Individually Fair Gradient Boosting
• Theory In, Theory Out: The uses of social theory in machine learning for social science
• On the Identification of Fair Auditors to Evaluate Recommender Systems based on a Novel Non-Comparative Fairness Notion
• Group-based Fair Learning Leads to Counter-intuitive Predictions
• An exploration of algorithmic discrimination in data and classification
• Non-Comparative Fairness for Human-Auditing and Its Relation to Traditional Fairness Notions
• Local Justice and the Algorithmic Allocation of Societal Resources
• Access to Population-Level Signaling as a Source of Inequality