Research map / Learning theory and algorithms / Fairness

Utility-Fairness Trade-Offs and How to Find Them

CVPR 2024 · Learning theory and algorithms › Fairness · approach: Fair allocation and selection · 8 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces Data-Space and Label-Space utility-fairness trade-offs and U-FaTE, a closed-form-solver method to numerically estimate them from data, then uses them to evaluate FRL methods and over 1000 pre-trained representations.

Problem

Optimal utility-fairness trade-offs for classification with demographic fairness constraints are not precisely characterized, and prior work lacks a way to numerically quantify them from data for independence and separation fairness definitions.

Approach

Defines two trade-offs (DST, data-dependent; LST, oracle over label distribution) that partition the utility-fairness plane into possible, possible-with-extra-data, and impossible regions, and estimates them with U-FaTE, which alternates a neural feature extractor with a closed-form HSIC-based fair encoder solver.

Key results

• On FairFace, U-FaTE-DST reaches 96.17% accuracy at 0.263% EOD, while the best FRL baseline (ARL) reaches 93.39% at 1.34% EOD.
• Over 100 zero-shot OpenCLIP models are far from the estimated DST on CelebA, with models trained on CommonPool being fairer but less accurate.
• Several supervised models (OpenAI WIT, LAION, ImageNet22K/21K/12K) surpass the DST on FairFace, entering the possible-with-extra-data region.

Measured effects reported in the paper

Surprising findings

• Some supervised pre-trained representations on FairFace surpass the estimated DST, implying that extra training data can exceed the data-limited trade-off.
• EOD and EOOD trade-offs are nearly flat at 100% accuracy on CelebA for LST, so these fairness metrics do not force accuracy sacrifice, unlike DPV.

Limitations

• U-FaTE provides no convergence or optimality guarantees, so estimated DST and LST are likely suboptimal.
• Trade-off estimates use all available samples without a held-out split, so they may reflect training-set fit.

Experimental setup

Datasets: CelebA FairFace FolkTables

Benchmarks: CelebA FairFace FolkTables

Metrics: accuracy equalized opportunity difference equality of odds difference demographic parity violation distance to DST/LST

Baselines: ARL FairHSIC OptNet-ARL MaxEnt-ARL K-TOpt LEACE

Builds on: K-TOpt adversarial representation learning FairHSIC Hilbert-Schmidt independence criterion

Closest papers by meaning

• Inherent Tradeoffs in Learning Fair Representations (NeurIPS 2019 · similarity 0.90)
• Understanding Fairness and Prediction Error through Subspace Decomposition and Influence Analysis (NeurIPS 2025 · similarity 0.88)
• Demographic parity in regression and classification within the unawareness framework (NeurIPS 2026 · similarity 0.88)
• Accuracy vs. Accuracy: Computational Tradeoffs Between Classification Rates and Utility (NeurIPS 2026 · similarity 0.87)
• Achievable Fairness on Your Data With Utility Guarantees (NeurIPS 2024 · similarity 0.87)
• Fairness-Accuracy Trade-Offs: A Causal Perspective (AAAI 2025 · similarity 0.86)