Fair Regression: Quantitative Definitions and Reduction-based Algorithms

Alekh Agarwal; Miroslav Dudík; Zhiwei Steven Wu

Source-linked AI summary

Fair Regression: Quantitative Definitions and Reduction-based Algorithms

Alekh Agarwal, Miroslav Dudík, Zhiwei Steven Wu

arXiv:1905.12843v1May 30, 2019cs.LGstat.ML

TL;DR

The paper addresses fair prediction of real-valued targets, where existing classifier-based fairness tools do not directly cover continuous scores. It develops reductions from fair regression to standard learning oracles under statistical parity and bounded group loss, and empirically uncovers fairness–accuracy frontiers. The approach supports broader regression tasks and model classes while retaining theoretical fairness and performance guarantees.

Problem
Existing fairness research largely targets discrete classification decisions, leaving a gap for quantitatively fair real-valued regression across broader tasks and model classes.
Method
The paper develops separate reductions for statistical parity and bounded group loss using cost-sensitive classification, weighted least-squares, and weighted risk-minimization oracles.
Results
Experiments on standard datasets uncover fairness–accuracy frontiers for least-squares and logistic regression under statistical parity.
Takeaways & Limitations
The schemes provide a systematic way to enforce fairness across a broader class of learning problems using standard classification or regression algorithms.
Takeaways & Limitations
The main reduction can take time and create a dataset of size Ω(n^(1+β)), substantially larger than the original size n for typical β ≈ 1/2.

Abstract

from arXiv · show

In this paper, we study the prediction of a real-valued target, such as a risk score or recidivism rate, while guaranteeing a quantitative notion of fairness with respect to a protected attribute such as gender or race. We call this class of problems \emph{fair regression}. We propose general schemes for fair regression under two notions of fairness: (1) statistical parity, which asks that the prediction be statistically independent of the protected attribute, and (2) bounded group loss, which asks that the prediction error restricted to any protected group remain below some pre-determined level. While we only study these two notions of fairness, our schemes are applicable to arbitrary Lipschitz-continuous losses, and so they encompass least-squares regression, logistic regression, quantile regression, and many other tasks. Our schemes only require access to standard risk minimization algorithms (such as standard classification or least-squares regression) while providing theoretical guarantees on the optimality and fairness of the obtained solutions. In addition to analyzing theoretical properties of our schemes, we empirically demonstrate their ability to uncover fairness--accuracy frontiers on several standard datasets.

1. Introduction

The paper extends quantitative fairness from discrete classification decisions to real-valued regression predictions, developing reductions with theoretical guarantees and empirical fairness–accuracy frontiers.

Fair regression targets real-valued quantities while enforcing fairness with respect to protected attributes such as race or gender.
The paper studies statistical parity and bounded group loss as quantitative fairness definitions for regression.Statistical parity requires prediction independence from the protected attribute; bounded group loss limits error within each protected group.
The proposed schemes cover Lipschitz-continuous losses and tasks including least-squares, logistic, Poisson, and quantile regression.
For bounded group loss, fairness-constrained loss minimization reduces to weighted loss minimization using standard approaches.
For statistical parity, discretizing predictions reduces fair regression to cost-sensitive classification under suitable constraints.
Experiments on least-squares and logistic regression show fairness–accuracy frontiers across standard datasets, with comparisons against unconstrained baselines and prior methods.The study uses linear and tree-ensemble learners.
Substantial tradeoffs along a fairness–accuracy frontier require analysis because they may indicate data problems needing additional data, new features, or nonalgorithmic intervention.

2. Problem Formulation

The formulation defines fair regression for real-valued labels and predictions under Lipschitz losses, then formalizes statistical parity, bounded group loss, and randomized predictors.

2. Problem Formulation: Training examples are triples (X, A, Y), with a finite protected attribute A, potentially high-dimensional features X, and labels Y embedded in [0, 1].
2. Problem Formulation: Predictions and labels may be real-valued, and accuracy is measured by a loss ℓ that is 1-Lipschitz under the ℓ1 norm.The condition is |ℓ(y, u) − ℓ(y′, u′)| ≤ |y − y′| + |u − u′|.
2. Problem Formulation: Least-squares regression fits the framework when normalized GPA labels and predictions lie in [0, 1], making the square loss bounded and 1-Lipschitz.
2.1. Fairness Definitions: Statistical parity requires f(X) to be independent of protected attribute A, equivalently matching threshold probabilities across groups for every z.
2.1. Fairness Definitions: Bounded group loss requires E[ℓ(Y, f(X)) | A = a] ≤ ζ for every protected group.
2.2. Fair Regression: Fair regression minimizes expected loss subject to statistical parity or bounded group loss, and randomized predictors are introduced to improve fairness–accuracy tradeoffs.
2.2. Fair Regression: Under statistical parity, slack ε_a bounds each group’s allowed CDF departure from the overall prediction CDF, measured in the ℓ∞ norm.
2.2. Fair Regression: Randomized predictors sample f from a distribution Q before producing predictions, extending the constrained optimization over predictors.

3. Supervised Learning Oracles

The paper reduces fair regression to standard supervised-learning oracle problems that support example-specific costs or weights, enabling fairness constraints through familiar learners.

Fair regression is transformed into cost-sensitive classification, weighted least-squares regression, or weighted risk minimization without fairness constraints.
Risk minimization under ℓ returns a predictor minimizing weighted empirical risk over the chosen function class.
Weighted square-loss minimization provides a least-squares oracle even when the target accuracy loss is ℓ.
The cost-sensitive classification oracle optimizes classifiers over an augmented feature space with binary predictions.
In the binary reduction, the sign of each cost difference determines the target label, while its absolute value becomes the example weight.
For statistical parity, classifiers threshold regressors using augmented inputs (x, z) and predict 1{f(x) ≥ z}.
Optimization-based learners such as logistic regression, SVMs, and neural networks can be adapted to the thresholded-regressor representation.

4. Fair Regression under Statistical Parity

The statistical-parity reduction discretizes predictions, converts fair regression into constrained cost-sensitive classification, and solves the resulting problem through standard learning oracles. The method provides fairness and loss guarantees, while alternative implementations address the computational cost of discretization.

Reduction to Constrained Classification: Discretizing the prediction space converts fair regression under statistical parity into a constrained classification problem solved by repeated cost-sensitive-classification oracle calls.The reduction first approximates the loss on a finite grid, then represents grid-threshold predictions as classifiers.
Discretization: The discretized loss differs from the original loss by at most α, so sufficiently fine grids preserve the regression objective approximately.Lipschitz continuity supplies the approximation guarantee, with α = 1/N controlling granularity.
Reduction to Constrained Classification: The classification construction samples grid values uniformly, augments inputs with the sampled prediction threshold, and assigns costs encoding the discretized regression loss.The resulting classifier cost equals the discretized loss, and its constraints represent statistical-parity deviations.
Algorithm and Generalization Bounds: The algorithm solves a Lagrangian saddle-point problem with primal predictor distributions and dual fairness multipliers, using best-response and exponentiated-gradient updates.Empirical constraints use slightly enlarged slacks to compensate for finite-sample errors.
Algorithm and Generalization Bounds: Under the stated Rademacher-complexity assumption, the returned randomized predictor has theoretical guarantees on loss and statistical-parity constraint violations with probability at least 1−δ.The analysis uses parameters ν ∝ n^-β, B ∝ n^β, and N ∝ n^β, with logarithmic factors suppressed in the iteration bound.

5. Fair Regression with Bounded Group Loss

For bounded group loss, the paper reduces fair regression to unconstrained loss minimization using a matched loss and a weighted risk-minimization oracle. Algorithm 2 alternates dual updates and best responses, with guarantees of termination and either approximate feasibility or certified infeasibility.

Reduction: The approach reduces bounded-group-loss fair regression directly to regression without discretization because the objective and constraints use the same loss.The method follows a reduction framework while exploiting the matched loss function.
Algorithm: Algorithm 2 alternates exponentiated-gradient updates on group-specific dual variables with best responses for the predictor distribution.The best-response computation can be solved with one call to a weighted risk-minimization oracle.
Algorithm: The best-response minimization weights examples according to their protected-group membership and can be written using the number of samples in each group.This converts the constrained optimization step into weighted loss minimization.
Guarantees: Under Assumption 2, Algorithm 2 terminates in O(n^4ω ln |A|) iterations with probability at least 1−δ.The guarantee uses ν ∝ n^-ω and B ∝ n^ω, with the stated condition on C′.
Guarantees: With probability at least 1−δ, the algorithm returns an approximately valid solution or returns null when the bounded-group-loss problem is infeasible.Unlike the statistical-parity problem, bounded group loss may be infeasible, so the algorithm explicitly accommodates that case.

6. Experiments

The experiments evaluate fair regression on least-squares and logistic tasks across five dataset variants, tracing fairness–accuracy tradeoffs against unconstrained and prior fair-learning baselines. The reductions substantially reduce disparity with limited overall-loss impact, although fair classification is stronger for logistic regression on adult.

Experimental setup: The evaluation covers least-squares and logistic regression under statistical parity across adult, law school, and communities & crime datasets, including subsampled variants.The two larger datasets also receive random 2,000-point subsampled versions, producing five datasets total.
Evaluation: The experiments select predictors along training fairness–loss Pareto fronts and evaluate their relative test loss against worst statistical-parity violation.Relative loss subtracts the smallest baseline loss, and Figure 1 reports confidence bands and intervals.
Experimental setup: The study compares the proposed algorithm with unconstrained regression and two baselines from fair classification and fair regression.The baselines include substantive equality of opportunity for least-squares tasks and fair classification for logistic tasks.
Results: All reductions significantly reduce disparity without strongly affecting overall loss, although communities & crime exhibits a more substantial accuracy–fairness tradeoff.The paper presents that tradeoff as a possible starting point for diagnosing data quality across the racial subgroups.
Results: The proposed methods dominate SEO on least-squares tasks but are slightly worse than fair classification in logistic regression, with a statistically significant difference only on adult.Least-squares and logistic reductions generally achieve tradeoffs comparable to cost-sensitive reductions while running substantially faster.

A. Proof of Lemma 1

The proof rewrites the loss as a cost-sensitive classification loss through a telescoping construction, then identifies the resulting loss with the classifier induced by a predictor.

Reduction: The proof begins by rewriting ℓα as a cost-sensitive classification loss using a telescoping trick.This provides the reduction from the regression loss to a classification-style objective.
Reduction: For z in the discretized prediction set, the loss ℓα is interpreted as the cost-sensitive error of classifier h_f.The induced classifier links each predictor to the cost-sensitive formulation.
Proof: The argument concludes after establishing the stated loss correspondence.The supplied proof excerpt ends with completion of the lemma.

B. Iteration Complexity of Algorithm 1

Algorithm 1 inherits a multiplicative-weights iteration guarantee from the fair-classification reduction framework, while adapting the analysis to its constraint count and cost range.

Iteration complexity: Algorithm 1 terminates in at most 16B^2 log(2|A|N+1)/ν^2 iterations.The bound is stated for the fair-regression reduction with its total constraint structure.
Proof strategy: The analysis casts the empirical constraints into the prior framework with 2|A|N total constraints and maximal violation at most 2.This is the bridge used to apply the inherited theorem.
Proof strategy: Because the regression costs may lie in [−1,1] rather than [0,1], one lemma’s bound changes while the main theorem and another lemma remain unaffected.The modified right-hand side is reported as 2+2ν in the supplied proof passage.
Guarantees: The returned predictor distribution has cost at most the feasible comparator’s cost plus 2ν.This follows from the cited adapted lemma in the proof.

C. Proof of Theorem 2

The proof combines uniform-convergence bounds with discretization and saddle-point guarantees to show that Algorithm 1 returns an approximately feasible and approximately optimal solution for fair regression.

Uniform convergence: Rademacher complexity controls uniform deviations for Lipschitz loss transformations, with a tighter bound when the transformation is linear.The general bound uses 4R_n(G), while linear transformations use 2R_n(G).
Uniform convergence: The proof separately bounds deviations in the cost and fairness constraints, then combines both events with probability at least 1 − δ.The cost and constraint bounds each hold with failure probability at most δ/2 before applying the union bound.
Population guarantees: The empirical saddle-point solution is compared with every feasible empirical solution through iteration and approximation guarantees.The analysis then transfers these guarantees from the empirical problem to the population problem using uniform convergence.
Population guarantees: A feasible population solution is also feasible empirically under the chosen slack adjustment, enabling approximate population optimality and fairness.The argument then relates the discretized fair-regression problem back to the original formulation.

E. Proof of Theorem 3

The proof of Theorem 3 analyzes Algorithm 2 through approximate saddle points, uniform convergence, and separate cases for feasible and infeasible fairness constraints.

Iteration complexity: Iteration complexity follows from the bilinear Lagrangian structure and boundedness assumptions used in the saddle-point analysis.The proof reuses the relevant results for distributions over predictors despite their original formulation for binary classifiers.
Algorithm 2: Algorithm 2 solves fair regression with bounded group loss using a Lagrangian best-response procedure over predictors and nonnegative constraint weights.The algorithm uses exponentiated-gradient updates with learning rate η = ν/(2B).
Feasible case: When a feasible solution exists, the approximate saddle point has loss within 2ν of any feasible empirical comparator and the algorithm returns a non-null predictor.Uniform convergence converts these empirical statements into corresponding population guarantees.
Feasible case: The population-feasible solution remains empirically feasible under the selected concentration slack, completing the theorem in the feasible case.This establishes the required approximate loss and group-loss guarantees for the returned solution.
Infeasible case: When no feasible solution exists, the algorithm either returns a predictor satisfying the theorem vacuously or returns null.The distinction depends on whether the approximate saddle point meets the theorem’s infeasibility condition.

F. Details for Efficient Implementation of Algorithm 1

Algorithm 1 is implemented through efficient fairness-statistic computation and reductions of the oracle subproblem to standard regression or risk-minimization tasks.

Algorithm 1 operations: Algorithm 1 averages the λ-player’s and classifier responses to form a candidate saddle-point solution, then stops when its suboptimality reaches ν.The auxiliary-vector transformations and updates take O(|A|N) time apart from best-response calls.
Fairness-statistic computation: For each protected group, sorting predictions enables computation of conditional threshold expectations and fairness statistics.The total cost of computing d_cost(h_f) and γ̂(h_f) is O(n log n + |A|N).
Fairness-statistic computation: Previously computed statistics let subsequent Lagrangian evaluations run in O(|A|N), while the first evaluation costs O(n log n + |A|N).The same complexity applies to the λ-player’s best response once γ̂ is available.
Best responses: The λ-player places all weight on the most violated fairness constraint, or returns zero when no constraint is violated.This makes BEST_λ(Q) computable in O(|A|N).
Oracle reductions: The predictor best response reduces to weighted least-squares regression or weighted risk minimization under any loss convex in the prediction.For logistic loss, two weighted examples per training triple suffice, with the same reduction complexity as least squares.
Oracle reductions: The convex-loss reduction constructs two weighted examples whose loss derivatives cancel at the chosen prediction.For logistic loss, one can choose labels 0 and 1 with the second weight equal to U_i.

G. Additional Experimental Results

Additional experiments examine training-set Pareto frontiers, oracle runtime, and how oracle-call counts vary with fairness slackness.

Training-set evaluation: Training evaluations show that the proposed method generally dominates or closely matches baseline methods, while SEO is not Pareto optimal on law school.The comparison includes SEO and unconstrained regressors.
Training-set evaluation: Figure 2 plots training loss against DP constraint violation as fairness slackness varies, showing Pareto frontiers for returned predictors.The logistic experiments additionally compare fair-classification reduction frontiers.
Runtime comparison: Figure 3 relates the number of oracle calls to the specified fairness slackness value.The experiment reports oracle-call behavior across different slackness settings.
Runtime comparison: Table 1 compares runtime for three supervised-learning oracles across model classes on a 1,000-example subsampled law-school dataset.The experiment used a 2.7 GHz Intel processor and 16GB memory.