Exponentiated Gradient Reduction
Description
Exponentiated gradient reduction trains a classifier that satisfies a chosen fairness criterion, such as demographic parity (equal rates of favourable outcomes across groups) or equalised odds (equal error rates across groups), while keeping error as low as it can. It reduces the problem to a series of ordinary training runs on the same data, each with different example weights. Between runs, a multiplicative update, the exponentiated gradient step, increases the weight on fairness constraints that are currently violated, and a standard classifier is retrained on the reweighted data. The output is a randomised classifier, a weighted mix of the classifiers trained along the way, with one drawn at random for each prediction. The original paper proves that its error and its fairness violation come close to the best achievable, up to a tolerance the user sets and the statistical error from a finite training set.
Example Use Cases
Fairness
A recruitment team trains a shortlisting model under a demographic parity constraint so that selection rates are equal across gender groups, and sweeps the method's tolerance setting to see how much accuracy each step towards equality costs.
A justice agency building a recidivism risk model trains a logistic regression under a demographic parity constraint on race, then compares accuracy and fairness metrics against the unconstrained model on the same data before deciding whether to deploy it.
A lender trying equalised odds, true-positive-rate difference and demographic parity as constraints on its credit-scoring model picks the one that gives the best balance of accuracy and profit on its own data, since the best choice differs between datasets.
Limitations
- The guarantees assume the base learner can solve each weighted training problem close to exactly. Real learners only approximate this, so the stated bounds on error and fairness violation are approximate in practice. The learner must also accept per-example weights, which rules out some model types.
- The result is a randomised mix of classifiers, so the same input can receive different predictions on repeat requests. This is hard to defend where decisions must be repeatable, as in appeals or audits.
- Needs the protected attribute for every training example, although not at prediction time. It enforces one fairness criterion at a time, and the original paper leaves trading off several criteria as an open problem.
- Each round retrains the base model, and the number of rounds needed grows with the square of the inverse of the tolerance, so halving the tolerance roughly quadruples training cost. Large datasets or slow models make tight tolerances expensive.
- Constraint violation is controlled only up to sampling error, which is larger for small groups. In one credit-scoring comparison the best-performing constraint differed between datasets, so the right criterion has to be found by experiment on the data in hand.
Resources
Research Papers
A Reductions Approach to Fair Classification
We present a systematic approach for achieving fairness in a binary classification setting. While we focus on two well-known quantitative definitions of fairness, our approach encompasses many other previously studied definitions as special cases. The key idea is to reduce fair classification to a sequence of cost-sensitive classification problems, whose solutions yield a randomized classifier with the lowest (empirical) error subject to the desired constraints. We introduce two reductions that work for any representation of the cost-sensitive classifier and compare favorably to prior baselines on a variety of data sets, while overcoming several of their disadvantages.