PaperlayerView exact revision on arXiv

Source-linked AI summary

Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees

L. Elisa Celis, Lingxiao Huang, Vijay Keswani, Nisheeth K. Vishnoi

arXiv:1806.06055v3cs.LGcs.AIcs.CYcs.DSstat.ML

TL;DR

Existing fair-classification methods often target individual metrics and may lack guarantees when the resulting constraints are non-convex. The paper develops a meta-algorithm that reduces broad fairness-constrained classification problems to convex or linear subproblems, supporting multiple non-disjoint sensitive attributes. Experiments show practical fairness–accuracy tradeoffs and predictive-parity handling, while further evaluation across datasets and losses remains needed.

  • Problem

    Existing methods provide metric-specific fair classifiers, but important metrics remain unsupported and many methods lack theoretical guarantees for non-convex optimization problems.

  • Method

    The paper develops a convex-constraint meta-algorithm and reduces classification problems with more general fairness constraints to a family of linear constrained optimization problems.

  • Results

    The framework handles many fairness definitions, multiple non-disjoint sensitive attributes, and predictive parity with provable guarantees while achieving a reasonable fairness–accuracy tradeoff empirically.

  • Takeaways & Limitations

    The framework unifies prior fair-classification approaches and provides a practical route to approximately optimal classifiers across a broad class of fairness metrics.

  • Takeaways & Limitations

    The authors identify a need to evaluate the algorithm on more datasets and extend it to other loss functions and classifier classes.

Abstract

from arXiv · show

Developing classification algorithms that are fair with respect to sensitive attributes of the data has become an important problem due to the growing deployment of classification algorithms in various social contexts. Several recent works have focused on fairness with respect to a specific metric, modeled the corresponding fair classification problem as a constrained optimization problem, and developed tailored algorithms to solve them. Despite this, there still remain important metrics for which we do not have fair classifiers and many of the aforementioned algorithms do not come with theoretical guarantees; perhaps because the resulting optimization problem is non-convex. The main contribution of this paper is a new meta-algorithm for classification that takes as input a large class of fairness constraints, with respect to multiple non-disjoint sensitive attributes, and which comes with provable guarantees. This is achieved by first developing a meta-algorithm for a large family of classification problems with convex constraints, and then showing that classification problems with general types of fairness constraints can be reduced to those in this family. We present empirical results that show that our algorithm can achieve near-perfect fairness with respect to various fairness metrics, and that the loss in accuracy due to the imposed fairness constraints is often small. Overall, this work unifies several prior works on fair classification, presents a practical algorithm with theoretical guarantees, and can handle fairness metrics that were previously not possible.

1 Introduction

Fair classification is needed because deployed classifiers may discriminate across sensitive groups, while existing metric-specific methods often lack guarantees. This paper introduces a general, provably guaranteed framework that handles broader fairness constraints, including predictive parity.

  • Motivation: Classifiers increasingly affect criminal justice, policing, lending, hiring, health care, and education, raising concerns about bias against sensitive groups.Such bias may also violate anti-discrimination laws or create social imbalance.
  • Problem: Existing fair-classification methods formulate metric-specific constrained optimization problems, but many lack provable guarantees because the problems can be non-convex.Prior examples target statistical parity and equalized odds.
  • Contribution: The paper presents a meta-classification algorithm supporting many fairness constraints, multiple non-disjoint sensitive attributes, and theoretical guarantees.It develops a convex-constraint meta-algorithm and reduces more general fairness problems to that family.
  • Empirical evaluation: Experiments on Adult, German credit, and COMPAS show a reasonable fairness–accuracy tradeoff and support handling predictive parity.The framework is intended to cover fairness metrics beyond statistical parity and equalized odds.
  • Contribution: The framework unifies and extends prior fair-classification methods rather than designing a separate algorithm for each fairness definition.Its framework provides approximately optimal classifiers under a broad class of fairness definitions.

2 Background and Notation

The paper models classification with sensitive-group performance functions and fairness constraints, including linear-fractional metrics such as predictive parity. Because the resulting constraints can be non-convex, it introduces linear constrained problems as a computational subroutine.

  • Classification model: Data samples contain features, multiple sensitive attributes, and a binary label; the main text focuses on one sensitive attribute partitioning samples into groups.The framework also distinguishes classifiers that use the sensitive attribute from those that do not.
  • Group performance: Group performance measures conditional probabilities for each sensitive group, and fairness requires the group values to be approximately equal.Examples include statistical rate, accuracy rate, and false discovery rate.
  • Examples: Accuracy can be expressed as a linear combination of conditional probabilities, while false discovery rate is represented through conditional probabilities involving positive predictions.These representations expose the structure used to generalize group-performance functions.
  • Function class: Linear-fractional group-performance functions are quotients of linear combinations of classifier-dependent conditional probabilities; linear functions are a special case.The paper states that all metrics in Table 1 are linear-fractional and many are linear.
  • Fairness program: The fair-classification program minimizes prediction loss while imposing τ-rule constraints over one or more fractional group-performance functions.τ = 1 gives perfect fairness, whereas τ < 1 expresses relaxed fairness.
  • Optimization: The resulting ρ-Fair constraints are generally non-convex, motivating a linear fairness-constraint subproblem and a reduction from ρ-Fair to Group-Fair.Group-Fair is more flexible because it can treat different groups differently.
  • Relation to prior work: Prior linear-constraint frameworks do not directly support linear-fractional constraints such as predictive parity because their conditioning events may depend on the classifier.This dependence distinguishes the paper’s target constraints from conditional-moment formulations supported by earlier work.

3 Theoretical Results

The paper develops a provably approximately optimal meta-algorithm by reducing general fair classification problems to convex or linear constrained subproblems. It also quantifies accuracy and fairness losses when the data distribution is estimated from samples.

  • Reduction to Group-Fair: A β-approximate Group-Fair solver yields a classifier whose prediction error is at most β times that of the optimal relaxed ρ-Fair classifier.The reduction applies the solver at most ⌈τ/ε⌉ times and selects the lowest-error feasible output.
  • Multiple constraints: The framework extends to multiple fairness requirements by applying the Group-Fair algorithm around ε^-m times, where m is the number of requirements.The paper states that this extension handles a constant number of fairness requirements.
  • Solving Group-Fair: Group-Fair admits an optimal Lagrangian classifier, with its parameters computable in polynomial time through a convex program.The resulting procedure uses the Lagrangian principle to convert fairness constraints into an unconstrained optimization problem.
  • Constraint generality: Linearizing the fairness constraints makes Group-Fair applicable to predictive parity, which prior approaches could not handle because the corresponding ratio constraint may be non-convex.The paper rewrites the relevant inequalities as linear constraints of the form a⊤f + b ≤0.
  • Sample-based guarantees: The algorithm estimates the data distribution from N samples and solves a family of Group-Fair programs using that estimate.The paper gives Gaussian Naive Bayes as one example for estimating the distribution.
  • Sample-based guarantees: With an estimated distribution, the output error is bounded by the optimal fair classifier's error plus 2 · dTV(bℑ, ℑ), while additional fairness error is represented by κ.When the estimated and true distributions coincide, both dTV(bℑ, ℑ) and κ are zero, yielding the idealized guarantee.

4 Details of Section 3.2: Algorithm for Group-Fair

The paper characterizes optimal fair classifiers as instance-dependent threshold functions and computes their Lagrangian parameters through convex optimization, stochastic subgradients, and polynomial-time procedures.

  • Characterization: An optimal fair classifier has the form I[sλ⋆(x) > 0] for some Lagrangian parameter λ⋆.The characterization is obtained by applying the Lagrangian principle to the constrained problem.
  • Characterization: Randomized classifiers are introduced to express prediction error and group-performance terms as linear functions of f(X).The randomized classifier predicts 1 with probability f(x), extending deterministic classifiers for the analysis.
  • Computation: The optimal Lagrangian parameter λ⋆ can be computed in polynomial time as the solution of a convex program.The convexity follows from the nonnegative fairness-width terms ui−ℓi and the convexity of the relevant expectation.
  • Computation: For infinite X, the algorithm uses an unbiased stochastic subgradient estimate and updates λ by a step-size-scaled descent rule.Convergence is established when the stochastic subgradient bound G is finite; the analysis assumes certain probabilities are bounded away from zero and λ⋆ has bounded norm.
  • Implementation: Algorithm 2 requires only selected distributional probabilities rather than the full underlying distribution, with a sample oracle assumed for stochastic estimation.This supports estimating the required information when the full distribution is unknown.
  • Extensions: The framework extends to sensitive attributes used for prediction and to q ∈ Qlinf, including polynomial-time computation of the corresponding optimal parameters.For q ∈ Qlinf, the optimal classifier is characterized using parameters ν⋆ and ζ⋆.

5 Empirical Results

Experiments on Adult, German, and COMPAS evaluate fairness–accuracy tradeoffs across the proposed algorithms and literature baselines. The proposed method can satisfy fairness constraints and optimize multiple metrics, but performance depends on the empirical-distribution fit.

  • Experimental Setup: The experiments use Adult, German, and COMPAS datasets with gender or race as the sensitive attribute.Adult and German use gender; COMPAS is restricted to black and white race groups.
  • Experimental Setup: The evaluation averages five random 70% training and 30% testing splits, using ε = 0.01 and a Gaussian Naive Bayes fit for the estimated distribution.Algorithm 1-FDR is evaluated across τ values from 0.1 through 1.0.
  • Adult Results: On Adult, Algo 1-SR reaches higher γsr than the other methods, while its accuracy decreases with γsr but remains above 75%.The authors attribute its lower accuracy at comparable fairness partly to the simplistic empirical-distribution model.
  • Adult Results: On Adult, Algo 1-FDR and FPR-COV achieve both high accuracy and high γfdr, while other methods are worse on fairness and/or accuracy.The authors relate the strong γfdr performance to an unconstrained optimal classifier with γfdr = 0.84.
  • Multiple Metrics: Algo 1 can optimize different fairness metrics through its parameters, and Algo 1-SR+FDR achieves γsr > 0.7 and γfdr > 0.7 simultaneously.The remaining methods cannot achieve both thresholds, with γsr < 0.45 or γfdr < 0.55; the combined constraint reduces accuracy.
  • German Results: On German, Algo 1-FDR satisfies the input fairness constraint almost every time and reaches γfdr around 0.99, versus around 0.85 for other algorithms.Algo 1-SR also satisfies nearly all input τsr constraints, except when τsr is almost 1, where γsr is close to 0.98.
  • Interpretation: The plotted tradeoffs can appear non-monotone because they average results across five training–test splits, although each partition is monotone.Table 2 reports mean and standard deviation for accuracy and fairness metrics, alongside an unconstrained classifier.
  • COMPAS Results: On COMPAS, Algo 1-FDR reaches maximum γfdr around 0.80, while SHIFT reaches as high as 0.98.The authors attribute the lower output fairness to the multivariate Gaussian empirical distribution being a poor fit for the data.

6 Conclusion and Discussion

The framework handles many fairness definitions, including predictive parity, with provable guarantees. Experiments show fairness–accuracy tradeoffs, while future work targets broader evaluation and model settings.

  • The framework handles many existing fairness definitions and is presented as the first to ensure predictive parity with provable guarantees.
  • Future work includes evaluating additional datasets and extending the framework to other loss functions and classifier types.
  • Algo 1-SR achieves higher SR fairness than other methods, but its accuracy decreases as γsr increases.
  • Algo 1-FDR achieves better FDR fairness while remaining indistinguishable from other methods in accuracy.
  • The paper considers fairness metrics ρq and δq, while AUC and correlation are identified as other possible metrics.

A Proof of Lemma 4.6

The proof rewrites the relevant quantity as a sum of vectors and uses boundedness to complete the argument.

  • The proof begins by rewriting ˜g(λ) as the sum of two vectors, including a random vector h ∈ R^p.
  • The argument uses the fact that one resulting quantity is always bounded.
  • The proof concludes after applying the preceding identities and bounds.

B Existing Group Performance Functions are Linear-Fractional

The paper shows that many group performance functions are linear or linear-fractional, enabling a unified treatment of fairness constraints.

  • Statistical, conditional statistical, true positive, false positive, true negative, false negative, and accuracy rates are linear group performance functions.
  • False positive and true negative rates are linear after rewriting complementary conditional probabilities.
  • Accuracy is expressed as a weighted combination of class-conditional prediction probabilities within each group.
  • The remaining group performance functions are not linear but remain linear-fractional.
  • False discovery, false omission, positive predictive, and negative predictive rates are linear-fractional group performance functions.

C Algorithms for ρ-Fair with Multiple Sensitive Attributes and Multiple Group Benefit Functions

The appendix extends the framework to multiple sensitive attributes and multiple group performance functions. For a constant number of attributes, reductions and algorithms yield approximately optimal fair classifiers in polynomial time.

  • Problem formulation: The multi-attribute setting permits multiple non-disjoint sensitive attributes and multiple fairness metrics or group performance functions.
  • Problem formulation: A classifier satisfies the multi-attribute τ-rule when each fairness coordinate meets its corresponding threshold.
  • Reduction and algorithm: For constant m, Multi-ρq-Fair reduces to Multi-Group-Fair by solving a family of linear constrained optimization problems.
  • Guarantees: The resulting classifier satisfies, for every attribute, a lower bound on the minimum group performance relative to the target threshold.
  • Implementation: The output classifier is an instance-dependent threshold function with additional Lagrangian parameters, and the multi-attribute quantification matches the single-function theorem.
  • Guarantees: For constant m, a polynomial-time algorithm computes an approximately optimal fair classifier for Multi-ρq-Fair and Multi-δq-Fair.

D Another Algorithm for ρ-Fair with Linear Group Performance Functions

For linear group performance functions, ρ-Fair becomes a linear program that can be solved efficiently through Lagrangian optimization, including multiple group constraints. Meta2 offers a sample-based alternative with different computational and modeling tradeoffs.

  • ρ-Fair is a linear program when all group performance functions are linear, generalizing fairness problems such as statistical parity and true positive parity.
  • An efficient polynomial-time algorithm exists for ρ-Fair when the number of group performance functions is constant and each is linear.
  • The fairness ratio can be rewritten as p(p−1) linear constraints, yielding a linear-program formulation with one Lagrangian parameter λij per constraint.
  • An optimal fair classifier has threshold form I[sλ⋆(x) > 0], and the optimal Lagrangian parameters λ⋆ can be computed.
  • With only samples available, Meta2 estimates the distribution before optimization and achieves a fairness guarantee without the additional error parameter ε.
  • Algorithm 1 handles linear-fractional functions and uses fewer Lagrangian parameters, whereas Meta2 solves one convex optimization problem but may require (p−1)p parameters.

E Details of Remark 3.5 for Fairness Metric δq

The δq fairness problem is reduced to a family of Group-Fair problems, producing an approximately optimal classifier through repeated calls to a Group-Fair solver. A sample-based version estimates the distribution and incurs explicit estimation and approximation errors.

  • δq fairness captures existing constrained optimization problems as special cases through a fairness metric based on group-performance differences.
  • δ-Fair is reduced to Group-Fair, enabling an efficient approximately optimal classifier when an appropriate Group-Fair algorithm is available.
  • The reduction applies a β-approximate Group-Fair algorithm at most ⌈(1 + τ)/ε⌉ times and selects the candidate with minimum prediction error.
  • The resulting classifier satisfies δq(f) ≥ τ − ε while achieving error within the reduction’s β factor of the optimal δ-Fair classifier.
  • Meta-δq estimates the underlying distribution from N samples and then solves a family of Group-Fair programs using the estimate.
  • The sample-based guarantee includes an additional error term 2 · dTV(bℑ, ℑ) when transferring results from the estimated distribution to the true distribution.

F Price of Fairness Constraints

The paper defines the price of fairness as the increase in prediction error caused by imposing fairness constraints and analyzes when that increase is small. Tighter constraints cannot improve the optimal fair classifier’s performance.

  • The price of fairness measures the increase in prediction error resulting from fairness constraints.
  • The price of fairness is non-decreasing when lower bounds ℓi increase or upper bounds ui decrease, because tighter constraints cannot improve performance.
  • The theorem characterizes the price of fairness for a single linear group performance function under the optimal fair classifier defined by sλ⋆.
  • When λ⋆ = 0, the fairness price is zero, so imposing the constraints does not increase prediction error.
  • The fairness price is small when η(X) − 0.5 and η′(X) have the same sign with high probability, linking the cost to alignment with the sensitive-attribute-related variable.

G Other Experiments

Experiments compare accuracy against output fairness for Algo 1-SR and Algo 1-FDR across German and COMPAS datasets. The reported fairness–accuracy tradeoffs depend on the dataset and fairness metric.

  • For German, Algo 1-SR achieves better SR fairness while remaining indistinguishable in accuracy from comparison methods.
  • For German, Algo 1-FDR achieves better FDR fairness while remaining indistinguishable in accuracy from comparison methods.
  • For COMPAS, Algo 1-SR achieves better SR fairness than any other method, albeit with a loss in accuracy.
  • The experiments also vary τsr and τfdr to examine accuracy and fairness responses on both German and COMPAS datasets.
Loading 1806.06055v3…