Practical Approaches for Fair Learning with Multitype and Multivariate Sensitive Attributes

Tennison Liu, Alex Chan, Boris van Breugel, Mihaela van der Schaar

TL;DR

Fair machine learning typically assumes a single, binary protected attribute (like race or sex) and a binary outcome, leaving multi-attribute and continuous real-world settings behind. This paper introduces FairCOCCO, a framework utilizing cross-covariance operators in Reproducing Kernel Hilbert Spaces (RKHS) to quantify and enforce fairness across multiple sensitive attributes of arbitrary types (continuous, categorical, or binary). It provides both an interpretable, normalized metric (FairCOCCO Score) and a differentiable regularizer that enforces joint fairness without sacrificing predictive utility.

What Problem Does This Paper Address?

Most fairness research evaluates algorithms on toy-like assumptions: a single protected attribute $A \in \{0, 1\}$ and a binary target $Y \in \{0, 1\}$. Real-world decision-making is rarely that simple:

  1. Multivariate attributes: Legal and ethical frameworks protect multiple traits simultaneously (e.g., race, gender, age). Penalizing unfairness separately per attribute causes "fairness gerrymandering," where an algorithm seems fair for each trait in isolation but severely discriminates against subgroup intersections (e.g., older women).
  2. Multitype variables: Attributes (like age) and outcomes (like credit limits or crime rates) are often continuous. Discretizing them into bins causes threshold artifacts, destroys order information, and creates sample sparsity.
  3. Weak dependence metrics: Prior relaxations only penalize linear correlations (first/second moments), allowing non-linear discriminatory biases to slip through undetected.

Methods

The authors build on the conditional cross-covariance operator (COCCO) in RKHS to capture arbitrary, higher-order dependencies between predictions $\hat{Y}$, true labels $Y$, and sensitive attributes $A$:

  • FairCOCCO Metric: The dependency between $\hat{Y}$ and $A$ given $Y$ is measured via the Hilbert-Schmidt (HS) norm of the normalized cross-covariance operator: $$\hat{I} = \|V_{\hat{Y}\ddot{A}|Y}\|^2_{\text{HS}}$$ Using the Cauchy-Schwarz inequality, the authors normalize this metric to the range $[0, 1]$, where $0$ represents statistical conditional independence ($\hat{Y} \perp\!\!\perp A \mid Y$, satisfying Equalized Odds) and $1$ represents maximal dependence.

  • FairCOCCO Learning: The metric is differentiable, enabling an unconstrained Lagrangian objective: $$\min_{\theta} \frac{1}{N} \sum_{i=1}^N \mathcal{L}(f_\theta(x_i), y_i) + \lambda I_F(\mathcal{D}, f_\theta)$$

  • Computational Scaling: Kernel matrix inversion naively scales as $\mathcal{O}(N^3)$. To make training practical, the authors approximate Gram matrices using a low-rank pivoted Cholesky decomposition ($\mathcal{O}(r^2 N)$ complexity) and compute regularizers over mini-batches.

Datasets

The authors evaluated FairCOCCO across 11 datasets spanning tabular, image, and temporal healthcare domains:

  • Binary Tabular Benchmarks: COMPAS, Adult, German Credit, and Drug Consumption.
  • Multivariate & Continuous Tabular Benchmarks: Communities and Crime (C&C, continuous regression with 3–4 ethnic proportion attributes), Student Performance (continuous grades with continuous age and binary gender), KDD-Census, Default Credit Card, and Law School.
  • Computer Vision: CelebA (face attribute classification for attractive, smile, and wavy hair using a ResNet-18, conditioned on gender).
  • Clinical Time Series: MIMIC-III ICU database (evaluating offline imitation learning via behavioral cloning for sepsis treatment intervention, conditioned on gender).

Key Insights and Ideas

  • Joint protection implies individual protection, but not vice-versa: Because $\hat{Y} \perp\!\!\perp (A_1, \dots, A_d) \mid Y \implies \hat{Y} \perp\!\!\perp A_i \mid Y$, optimizing for joint independence automatically protects individual attributes. In contrast, existing methods that optimize individual attributes independently fail to guarantee joint fairness and trigger internal trade-offs.
  • General framework compatibility: FairCOCCO easily adapts to all common independence-based fairness definitions simply by swapping conditioning variables: Demographic Parity ($\hat{Y} \perp\!\!\perp A$), Equalized Odds ($\hat{Y} \perp\!\!\perp A \mid Y$), and Calibration ($Y \perp\!\!\perp A \mid \hat{Y}$).
  • Hypothesis testing for transparency: Because the FairCOCCO statistic rigorously converges to zero under the null hypothesis of independence, it can be paired with permutation testing to output concrete $p$-values quantifying fairness guarantees.

Key Results

  • Tabular Benchmarks: In binary settings, FairCOCCO matched or exceeded state-of-the-art accuracy while consistently driving the Difference in Equal Opportunity (DEO) close to zero (e.g., dropping COMPAS DEO to $0.00 \pm 0.01$ at $0.89$ accuracy; Adult DEO dropped to $0.04$).
  • Multivariate Continuous Tasks: On Communities & Crime (C&C), FairCOCCO achieved lower MSE ($0.63$) and a joint COCCO score of $0.11$, decisively outperforming competitors FACL ($0.66$ MSE, $0.15$ COCCO) and FARMI ($0.65$ MSE, $0.20$ COCCO). It preserved minimal DEO across all protected subgroups simultaneously.
  • Beyond Tabular: On CelebA (attractive classification), FairCOCCO reduced DEO from $0.43$ (unregularized) to $0.03$ with negligible accuracy reduction ($0.82 \to 0.80$). On MIMIC-III sepsis treatment policy learning, it achieved a DEO of $0.00 \pm 0.01$ and cut unfairness (COCCO) from $0.13$ to $0.04$ while maintaining $0.81$ accuracy.

Limitations and Future Work

  • Tree-based models: FairCOCCO's regularizer is gradient-based, meaning it cannot be directly applied to popular non-differentiable tabular architectures like gradient-boosted decision trees (XGBoost/LightGBM).
  • Computational overhead: Despite mini-batching and low-rank Cholesky approximations, kernel methods remain heavier than basic moment matching; further acceleration methods (e.g., random Fourier features) are highlighted for future investigation.
  • Not a certificate of fairness: The authors caution that statistical independence metrics mitigate bias in predictions, but cannot resolve systemic, procedural, or data collection biases present in upstream pipelines.

Summary updated

Abstract

It is important to guarantee that machine learning algorithms deployed in the real world do not result in unfairness or unintended social consequences. Fair ML has largely focused on the protection of single attributes in the simpler setting where both attributes and target outcomes are binary. However, the practical application in many a real-world problem entails the simultaneous protection of multiple sensitive attributes, which are often not simply binary, but continuous or categorical. To address this more challenging task, we introduce FairCOCCO, a fairness measure built on cross-covariance operators on reproducing kernel Hilbert Spaces. This leads to two practical tools: first, the FairCOCCO Score, a normalized metric that can quantify fairness in settings with single or multiple sensitive attributes of arbitrary type; and second, a subsequent regularization term that can be incorporated into arbitrary learning objectives to obtain fair predictors. These contributions address crucial gaps in the algorithmic fairness literature, and we empirically demonstrate consistent improvements against state-of-the-art techniques in balancing predictive power and fairness on real-world datasets.
BibTeX
@inproceedings{liu2023practical,
  author = {Tennison Liu and Alex Chan and Boris van Breugel and Mihaela van der Schaar},
  title = {{Practical Approaches for Fair Learning with Multitype and Multivariate Sensitive Attributes}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=xWutyHiLtwP},
}

Loading related content...

Figure