Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness

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

Source-linked AI summary

Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness

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

arXiv:1711.05144v5Nov 14, 2017cs.LGcs.DScs.GT

TL;DR

Fairness checks based on a few predefined groups can miss violations on structured subgroups, motivating fairness constraints over rich subgroup classes. The paper reduces auditing to weak agnostic learning and develops two zero-sum-game algorithms for fair classification, with one offering polynomial-step guarantees and the other simpler, faster iterations but only asymptotic guarantees.

Problem
Predefined-group fairness can miss violations on structured subgroups, while auditing fairness over combinatorially many groups creates a computational challenge.
Method
The paper models subgroup fairness with indicator classes and formulates fair learning as a two-player zero-sum game solved using FTPL or Fictitious Play with agnostic-learning oracles.
Results
Auditing is computationally equivalent to weak agnostic learning and hard in the worst case, while the two algorithms converge under their respective guarantees and Fictitious Play performs effectively on real data.
Takeaways & Limitations
Rich subgroup auditing can be approached with practical machine-learning heuristics, and fair classifiers can be learned through game-based procedures despite worst-case hardness.
Takeaways & Limitations
Fictitious Play has provable convergence only asymptotically, and the auditing best-response step in the first algorithm is computationally expensive.

Abstract

from arXiv · show

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.

1 Introduction

The paper extends statistical fairness from a few predefined groups to rich subgroup classes to prevent fairness gerrymandering, while addressing the resulting computational challenges through auditing reductions and game-based learning algorithms.

Motivation: Statistical fairness over a few predefined groups can miss severe violations on structured subgroups formed by combining protected attributes.The race-and-gender example appears fair on each attribute separately but unfair on their intersectional subgroups.
Motivation: The proposed framework demands statistical fairness across a combinatorially large or infinite collection of structured subgroups.This creates a middle ground between coarse group fairness and individual fairness.
Learning algorithms: The paper formulates fair learning as a two-player zero-sum game between a Learner choosing classifiers and an Auditor identifying fairness violations.It presents FTPL-based polynomial-step convergence and simpler Fictitious Play with asymptotic convergence and faster per-step computation.
Empirical evaluation: The Fictitious Play implementation effectively audits and learns fair classifiers on a real dataset where subgroup fairness is a concern.The experiments use a dataset with many real-valued protected attributes, creating many possible subgroups.
Auditing: Auditing subgroup fairness for statistical parity and equal opportunity is computationally equivalent to weak agnostic learning of the subgroup class.The equivalence is stated in a strong, distribution-specific sense.
Auditing: Agnostic learning is computationally hard in the worst case even for simple subgroup classes, so universally efficient auditing algorithms should not be expected.The paper cites boolean conjunctions and linear threshold functions as examples of simple classes with hard agnostic learning.

2 Model and Preliminaries

The paper defines subgroup fairness through indicator-function classes over protected attributes, formalizes auditing and agnostic learning, and supplies learning-theoretic and optimization preliminaries for its algorithms.

Model: Individuals are represented by protected attributes x, unprotected attributes x′, and a binary label y; auditing may expose x and y without exposing x′.The induced auditing distribution includes the classifier’s decision but hides unprotected attributes.
Protected subgroups: The subgroup class G contains indicator functions g over protected attributes, with g(x)=1 identifying membership in subgroup g.The framework uses these indicators to define protected groups.
Fairness constraints: Statistical parity requires subgroup acceptance rates to remain close to the overall acceptance rate, while false-positive fairness compares subgroup and overall false-positive rates.Both definitions use approximation parameters and exclude sufficiently small groups or complements for statistical estimation.
Auditing: An auditing algorithm either certifies fairness or returns a subgroup witnessing a fairness violation, with accuracy and runtime controlled by γ, γ′, and δ.An unfair subgroup is called an unfair certificate.
Learning preliminaries: Auditing subgroup fairness is closely related to weak agnostic learning, which is computationally equivalent to cost-sensitive classification.This connection supports both hardness results and oracle-based algorithm descriptions.
Optimization and guarantees: The paper introduces FTPL as a no-regret learner and uses uniform-convergence results to connect empirical optimization with population error and fairness.Separate convergence statements are given for statistical parity and false-positive subgroup fairness.

3 Equivalence of Auditing and Weak Agnostic Learning

The paper reduces subgroup-fairness auditing to weak agnostic learning, establishing both an equivalence and corresponding worst-case hardness results. The reduction also supports heuristic auditing and learning on practical, non-worst-case distributions.

Equivalence of Auditing and Weak Agnostic Learning: Auditing statistical parity and false positive fairness is computationally equivalent to weak agnostic learning under the stated distribution-specific relationships.The equivalence is formalized through reductions in both directions, with parameter-dependent guarantees.
Worst-Case Intractability of Auditing: Despite worst-case hardness, heuristic agnostic-learning algorithms can provide practical auditing procedures on specific distributions.The paper uses this implication to motivate effective learning algorithms and empirical evaluation beyond worst-case instances.
Equivalence of Auditing and Weak Agnostic Learning: The proof connects unfair subgroup certificates to functions that predict a classifier’s decisions from protected attributes with non-trivial accuracy.Either the predictor or its negation can serve as an unfairness certificate, using closure of the group class under negation.
Equivalence of Auditing and Weak Agnostic Learning: A single cost-sensitive classification or agnostic-learning oracle can solve the best-response problems underlying auditing and learning.The formulation treats the relevant distributions as targets for predicting classifier decisions from protected features.
False Positive Fairness: False positive fairness inherits the same equivalence because it is statistical parity fairness applied to the subset of examples with y = 0.The corresponding reductions relate auditing guarantees to weak agnostic learning under the conditional distribution P_D y=0.
Worst-Case Intractability of Auditing: Under standard complexity-theoretic assumptions, auditing is not polynomial-time solvable in the worst case for conjunctions, linear threshold functions, or bounded-degree polynomial threshold functions.The hardness applies to both statistical parity and false positive fairness for suitable distributions.

4 A Learning Algorithm Subject to Fairness Constraints G

The paper learns randomized classifiers that minimize error while satisfying subgroup fairness across a potentially large class of protected groups. It reduces this optimization to a zero-sum game and solves it using cost-sensitive classification oracles and no-regret dynamics.

Problem formulation: The goal is to find a distribution over classifiers that minimizes classification error subject to fairness constraints for every subgroup in G.The formulation remains feasible because constant classifiers satisfy all subgroup fairness constraints.
Guarantee: Given CSC(H) and CSC(G) oracles, a polynomial-time algorithm outputs a randomized classifier with error at most OPT+ν and bounded fairness violations with probability at least 1−δ.The result applies to the subgroup fairness constraints represented in the theorem’s formulation.
Finite reformulation: Even when H and G are infinite, Sauer’s Lemma reduces the problem to finitely many hypothesis and subgroup labelings on the sample.The resulting linear program has variables for induced hypothesis labelings and constraints for induced subgroup labelings.
Zero-sum game formulation: The Fair ERM problem is formulated as a zero-sum game whose Learner chooses classifiers and whose Auditor chooses subgroups and fairness-violation signs.The Learner minimizes prediction error plus a Lagrangian fairness penalty, while the Auditor emphasizes the most violated subgroup constraint.
Oracle access: Best responses for both players can be computed with cost-sensitive classification oracles over H and G.The Learner’s best response corresponds to classification, while the Auditor’s best response corresponds to auditing subgroup violations.
No-regret dynamics: Follow the Perturbed Leader for the Learner and best responses for the Auditor yield average strategies that converge to an approximate equilibrium.The equilibrium formulation supports oracle-based algorithms for learning fair classifiers.

5 Experimental Evaluation

The experiments evaluate FairFictPlay on the Communities and Crime dataset using Fictitious Play, examining convergence and error–unfairness trade-offs as γ varies. The algorithm shows practical convergence and produces models spanning useful accuracy–fairness trade-offs.

Algorithm: FairFictPlay implements Fictitious Play because it is simpler, deterministic, and faster per step than the randomized FTPL-based algorithm.Each round requires both players to compute a single best response to the opponent’s empirical history.
Dataset and setup: The evaluation uses the Communities and Crime dataset, containing 1,994 community records and 122 features, including many sensitive attributes.The study focuses on an 18-dimensional real-valued protected-attribute space derived from race statistics and related features.
Algorithm: The algorithm varies γ to control permitted unfairness, adding a subgroup penalty when Auditor-discovered disparity exceeds γ.Sweeping γ traces a menu of accuracy–fairness trade-offs.
Convergence: By 6,000 iterations most error curves flatten, and by 8,000 iterations most—but not all—appear approximately converged.Larger γ generally yields lower error after convergence, although some ordering violations occur, especially early in optimization.
Convergence: Most unfairness curves eventually settle near their corresponding γ values after substantial early oscillation.The Learner and Auditor alternate between reducing prediction error and enforcing subgroup fairness.
Trade-offs: The aggregate Pareto frontier ranges from error about 0.21 with no unfairness to error about 0.12 with unfairness 0.025.Intermediate points provide a relatively smooth menu of error–unfairness trade-offs.

A Chernoff-Hoeffding Bound

This appendix states a real-valued additive Chernoff–Hoeffding concentration bound for independent, identically distributed bounded random variables.

Theorem: Theorem A.1 assumes i.i.d. random variables with common expectation μ and values bounded between a and b.It provides a concentration statement for deviations controlled by α.

B Generalization Bounds

This appendix develops VC-dimension-based generalization machinery for products of hypothesis and subgroup classes. The argument bounds the combined class’s complexity and then applies uniform convergence.

Complexity bound: The proof relates the VC dimension of the combined class F_H,G to the VC dimensions of H and G.Its growth function is bounded by the product of the separate growth functions.
Complexity bound: Sauer–Shelah yields a combined complexity bound of approximately ˜O(VCDIM(H) + VCDIM(G)).This follows from counting labelings realized as conjunctions of labels from the two component classes.
Generalization: A standard VC-dimension uniform-convergence theorem then gives simultaneous control over the relevant functions with probability 1 − δ.The proof rewrites the fairness expression into terms involving subgroup and classifier probabilities.

C Missing Proofs in Section 4

The missing Section 4 proofs establish guarantees for approximate minmax solutions, best responses, no-regret dynamics, and sampling-based approximations. Together they support the theoretical analysis of the Learner–Auditor game.

Theorem 4.5: A ν-approximate minmax solution yields error at most OPT + 2ν and bounded maximum constraint violation.The proof derives these guarantees by comparing the approximate solution with an optimal feasible distribution.
Best responses: When a subgroup constraint is violated, an Auditor best response can place all dual weight C on a single subgroup coordinate.The dual optimization is linear over a scaled nonnegative ℓ1 ball, so an optimum occurs at a vertex.
No-regret analysis: The FTPL analysis bounds the Learner’s regret using the loss-coordinate magnitude and the dataset dimension n.The stated regret bound is 2n^1/4(1 + C) / √(nT).
Equilibrium guarantees: The proofs combine approximate best responses and regret bounds to establish the claimed equilibrium guarantees.The Auditor’s approximation error is incorporated into the regret analysis before the final conclusion.