Empirical Risk Minimization under Fairness Constraints

Michele Donini; Luca Oneto; Shai Ben-David; John Shawe-Taylor; Massimiliano Pontil

Source-linked AI summary

Empirical Risk Minimization under Fairness Constraints

Michele Donini, Luca Oneto, Shai Ben-David, John Shawe-Taylor, Massimiliano Pontil

arXiv:1802.08626v3Feb 23, 2018stat.MLcs.LG

TL;DR

The paper asks how classifiers can limit the unfair influence of sensitive variables while learning from data. It introduces fairness-constrained empirical risk minimization with theoretical guarantees and kernel and linear implementations, and reports improved fairness with maintained classification accuracy and favorable benchmark performance.

Problem
The paper addresses how to ensure that sensitive information does not unfairly influence supervised classifier outcomes.
Method
The paper constrains conditional risk across sensitive groups within empirical risk minimization, deriving a convex surrogate and implementations for kernel methods and linear preprocessing.
Results
Experiments indicate improved fairness properties while maintaining classification accuracy and favorable performance against state-of-the-art methods across benchmark datasets.
Takeaways & Limitations
The framework provides a theoretically supported and practically implementable approach for learning classifiers under fairness constraints.
Takeaways & Limitations
The approach is presented as naturally generalizing to other fairness measures, such as equal odds, but those extensions are left for future work.

Abstract

from arXiv · show

We address the problem of algorithmic fairness: ensuring that sensitive variables do not unfairly influence the outcome of a classifier. We present an approach based on empirical risk minimization, which incorporates a fairness constraint into the learning problem. It encourages the conditional risk of the learned classifier to be approximately constant with respect to the sensitive variable. We derive both risk and fairness bounds that support the statistical consistency of our approach. We specify our approach to kernel methods and observe that the fairness requirement implies an orthogonality constraint which can be easily added to these methods. We further observe that for linear models the constraint translates into a simple data preprocessing step. Experiments indicate that the method is empirically effective and performs favorably against state-of-the-art approaches.

1 Introduction

The paper develops fairness-constrained supervised learning by combining empirical risk minimization with approximately constant conditional risk across sensitive groups. It provides theoretical consistency guarantees, kernel and linear implementations, and favorable empirical comparisons.

Motivation: The paper addresses how supervised learning algorithms can prevent sensitive information from unfairly influencing classifier outcomes.The motivation includes decisions such as loan offers based on credit history while excluding unfair use of race or sex.
Fairness framework: Its fairness notion constrains conditional risk for positively labeled samples to be approximately constant across groups, recovering Equal Opportunity when using misclassification loss and ϵ = 0.
Fair ERM: Fair ERM incorporates the fairness constraint into empirical risk minimization and is supported by risk and fairness bounds establishing statistical consistency.Because the direct constraint is non-convex, the paper also proposes a surrogate convex problem related to relaxed Equal Opportunity.
Contributions: The paper develops a convex kernel-based method and a linear preprocessing approach, with experiments indicating favorable performance against state-of-the-art alternatives.
Contributions: The framework covers existing fairness-training approaches and positions them within a general empirical-risk-minimization framework.The related-work discussion distinguishes classifier modification methods from approaches enforcing fairness during training, including non-convex methods.

2 Fair Empirical Risk Minimization

The paper formulates fairness as approximately equal conditional risk on positive samples across groups, then incorporates this constraint into empirical risk minimization. FERM is supported by consistency results and a convex relaxation that can approximate both risk and fairness objectives.

Scope: The approach is formulated for binary labels and two groups, with extensions to multiple groups and other fairness measures noted as future work.Equal odds would require constraining conditional risks for both label values rather than only positive-labeled samples.
Fairness definition: The framework defines ϵ-fairness by requiring the positive-class conditional risks of two groups to differ by at most ϵ.With hard loss and ϵ = 0, this recovers equal opportunity; with linear loss and ϵ = 0, it equates conditional model outputs across groups.
Fair ERM: Fair ERM minimizes empirical risk subject to a fairness constraint, with risk measured by a prescribed loss function.The population risk is generally unavailable, so the learning procedure uses empirical risk within a prescribed model class.
Consistency: Theorem 1 establishes that, with appropriate parameter selection and learnability assumptions, FERM is consistent for both the selected model’s risk and fairness.As sample size grows, the learned risk approaches a value no larger than the constrained solution’s risk, while the estimator tends to be ϵ-fair.
Convex relaxation: Because the original fairness-constrained problem is nonconvex and nonsmooth, the method replaces hard loss with a convex loss and uses linear loss in the fairness constraint.For hinge loss, empirical hard-loss risk is bounded by empirical convex-loss risk; under an additional condition, linear-loss fairness is close to equal opportunity.
Convex relaxation: The resulting convex FERM solution is supported as close in classification accuracy and fairness to the target hard-loss solution under the stated conditions.The linear approximation may be tightened with other nonlinear approximations, but the proposed approximation yields a convex problem and works well empirically.

3 Fair Learning with Kernels

The paper specializes Fair ERM to kernel methods, where fairness becomes an orthogonality constraint in feature space. For linear models, this constraint can instead be enforced through preprocessing that removes one feature direction.

Kernel formulation: The kernelized method uses a positive-definite kernel and feature mapping to represent models in an RKHS.Functions are parameterized through feature vectors induced by κ.
Fairness constraint: Fairness is imposed by requiring w to be orthogonal to the difference between positive-sample group barycenters when ϵ = 0.The difference vector is u = u_a − u_b, and λ controls model complexity.
Kernel solution: By the representer theorem, the solution is expressed as a linear combination of training feature vectors and predictions use the kernel function.The coefficient vector can be obtained using the Gram matrix.
Optimization: With a convex loss such as Hinge loss, the resulting constrained problem extends SVM and can be integrated into standard SVM solvers.The dual formulation for Hinge loss is provided in supplementary material.
Linear models: For a linear kernel with ϵ = 0, fairness is enforced by preprocessing the data into a representation with one fewer feature.The transformation solves the orthogonality constraint directly rather than adding a separate model constraint.

4 Experiments

Experiments evaluate the method on synthetic and real datasets using accuracy and DEO. The results indicate improved fairness with a moderate accuracy cost, and demonstrate applicability beyond SVMs, including Lasso.

Experimental design: The experiments use one synthetic and five real datasets to assess fairness, accuracy, theoretical properties, and applicability to other linear models.The real datasets are Arrhythmia, COMPAS, Adult, German, and Drug.
Experimental design: The evaluation uses ϵ = 0, reports classification accuracy and DEO, and selects hyperparameters through 10-fold cross-validation.For four datasets, the procedure is repeated 10 times with average test performance and standard deviation.
Synthetic experiment: The synthetic experiment shows that the proposed method achieves higher fairness while maintaining good classification accuracy compared with standard linear SVM.Figure 1 compares test error and DEO across values of C and examines positive-label score distributions by group.
Real-data experiments: On the real datasets, the method substantially decreases DEO with only a moderate loss in accuracy relative to competing methods.The comparison includes settings where the sensitive feature is inside or outside x.
Real-data experiments: When the sensitive feature is included in x, accuracy generally increases, while fairness tends to decrease for methods not designed specifically for fairness.For the proposed method, access to group membership can improve fairness during prediction.
Application to Lasso: The method also produces sparse and fair models when combined with standard Lasso after applying the linear preprocessing step.This experiment targets a high-dimensional, small-sample Arrhythmia setting.
Theoretical validation: The estimated discrepancy Δ̂ has order of magnitude 10^-2 across benchmark and toy datasets, supporting a good approximation of DEO.The paper uses this quantity to assess how closely linear-loss fairness tracks Equal Opportunity.

5 Conclusion and Future Work

The paper presents a generalized fairness notion for constrained ERM, supported by theoretical analysis and practical kernel-method implementation. Experiments suggest improved fairness while maintaining classification accuracy, while future work includes broader relaxations, task settings, and accuracy–fairness analysis.

The framework generalizes prior fairness notions and incorporates fairness constraints into empirical risk minimization for fair classifiers.
Theoretical analysis provides statistical justification, while algorithmic observations support efficient implementation with kernel methods.
Experimental results suggest improved fairness properties while maintaining classification accuracy.
Future work includes alternative fairness-constraint relaxations, applications to multiclass classification and regression, and analysis of how ϵ affects statistical performance.

A Proofs

The proofs establish excess-risk and fairness results by combining empirical-risk comparisons, uniform bounds, and a union-bound argument. A loss inequality also relates the hard and convex formulations.

The excess risk is decomposed into estimation errors and an empirical-risk comparison between the learned model and the reference model.
An empirical-risk inequality makes the middle term nonpositive, leaving two generalization deviations to be bounded.
The first theorem statement follows from Eq. (5), while the second combines Eqs. (16) and (17) with a union bound.
The proposition's first statement follows from the pointwise inequality ℓh(f(x), y) ≤ ℓc(f(x), y).

B Literature Review of Fairness Methods

The literature review organizes fairness methods into a taxonomy and compares their properties, learning behavior, theoretical guarantees, empirical comparisons, and code availability.

Fairness methods are classified into three families according to when or how they impose fairness.
Table 2 compares convexity, convergence, and consistency with respect to risk and fairness across methods.
The table also records method comparisons and whether code is available online.

C Datasets

The paper describes the datasets, their tasks and sensitive features, and summarizes method characteristics and Drug-dataset results. Figure 3 compares Naïve SVM, Hard method, and the proposed method across ϵ values.

The dataset section outlines each dataset's task, feature type, data source, statistics, and sensitive feature.
Datasets: Arrhythmia is converted to binary classification of normal cases versus the other 15 arrhythmia classes.
Datasets: COMPAS contains defendant features and two-year recidivism outcomes for evaluating a commercial risk-scoring algorithm.
Datasets: Adult predicts whether annual income exceeds $50,000 using 14 demographic features and provided training and test sets.
Datasets: German classifies people as good or bad credit risks from 20 numerical and categorical features, including personal information.
Datasets: Drug contains 1,885 respondents described by 12 quantified categorical attributes, including personality, education, age, gender, country, and ethnicity.
Results: Figure 3 compares Naïve SVM, Hard method, and the proposed method on Drug-dataset results across different ϵ values.

D Varying the Value of ϵ

The experiments examine how varying ϵ affects the trade-off between classification error and demographic equal opportunity (DEO). Increasing ϵ reduces error but increases unfairness in the nonlinear method on the Drug dataset.

Increasing ϵ from 0 to 0.3 produces smaller error but stronger unfairness, measured by higher DEO.The tested values are 0, 0.01, 0.1, 0.2, and 0.3.
The experiment compares the nonlinear method with Naïve SVM and the Hard method on the Drug dataset.The study follows the experimental setting from Section 4.

E Visualization of the results of Table 1

Figure 4 visualizes the Table 1 results for linear and nonlinear methods when the sensitive variable is excluded from x. It reports that the same conclusions as Table 1 and Figure 2 apply in this setting.

Figure 4 presents linear-method results on the left and nonlinear-method results on the right when s is not included in x.
The results support the same conclusions previously drawn from Table 1 and Figure 2.

F Approximation of the DEO

The paper compares its DEO approximation with the original DEO and classification error across hyperparameter settings, finding empirical similarity between the two fairness measures. The method also connects fairness constraints to projected kernel features and extends to multiple sensitive groups.

The approximation of DEO is empirically similar to the original DEO on the German validation set across values of C and γ.Figure 5 varies the regularization hyperparameter C and the RBF hyperparameter γ.
A correct DEO approximation is particularly important in regions where classification error is low.
Figure 4 compares normalized error and DEO for linear and nonlinear methods, with points closer to the origin representing better results.Different symbols and colors identify datasets and methods.
The dual SVM problem optimizes over α ∈ [0, C]^n and ρ ∈ R after eliminating auxiliary variables under nonnegative multiplier constraints.
When ϵ = 0, the fairness-constrained SVM can be expressed using an orthogonal projection and an equivalent kernel based on projected features.The projection removes the component of the feature map along the direction of u.
For k sensitive groups and linear loss, the fairness requirement becomes k − 1 orthogonality constraints balancing group-specific positive-label barycenters.