Research map / Learning theory and algorithms / Fairness
Achievable Fairness on Your Data With Utility Guarantees
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.
Efficiently estimates the dataset-specific accuracy-fairness trade-off curve by training one YOTO model, and builds statistically valid confidence intervals (with a sensitivity analysis for suboptimality) to audit fairness methods.
Problem
Fairness-accuracy trade-off curves are dataset-dependent and expensive to approximate (requiring many retrained models), and empirical curves ignore finite-sample error, so suboptimality claims can be false.
Approach
Adapt You-Only-Train-Once (FiLM-conditioned on the regularization weight lambda) to fairness so one model yields the whole trade-off curve, then construct finite-sample confidence intervals on the optimal trade-off using a held-out calibration set, with a sensitivity analysis (extra separately trained models) for the unknown gap term in lower bounds.
Key results
- YOTO achieves about 40-fold computational savings (105 min for one model vs. ~40 separately trained models) while its trade-offs align with SOTA baselines on the four datasets.
- Using Bernstein CIs, 0.0 of YOTO trade-offs lie outside the permissible region, and the baselines show varying sub-optimal proportions (e.g., adversary 0.45, KDE-fair 0.03).
- The sensitivity analysis with 2 extra models shifts lower CIs for only 2 of 12 trade-off curves (DP and EO on Adult).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use YOTO instead of separately trained models across the fairness-regularization grid | Fairness trade-off estimation · All datasets and fairness metrics | Training cost: approximately 40-fold | Helped |
| Use YOTO trade-off estimation instead of separately trained models | Fairness trade-off estimation · All datasets and fairness metrics | Permissible proportion: 0.98 $\pm$ 0.01 -> 1.0 $\pm$ 0.0 | Helped |
| Use 2 separately trained models for sensitivity analysis | YOTO confidence intervals · Adult DP and EO; 12 trade-off curves overall | Lower confidence interval shift: 2 out of the 12 trade-off curves | Mixed |
Surprising findings
- Empirical trade-off curves of the same model evaluated on different test splits can differ enough to falsely suggest that one method is suboptimal, showing finite-sample error matters.
- Frontier bounds from information-theoretic work are not achieved by any SOTA method considered on Adult.
Limitations
- Requires a separate calibration dataset disjoint from training, which is problematic when data is limited.
- The lower CI depends on an unknown gap term Delta(h), approximated via sensitivity analysis with no general upper bound under weak conditions.
- The YOTO model may be suboptimal, making lower CIs too tight; the theoretical guarantee needs large model capacity assumption.
Experimental setup
Datasets: Adult COMPAS CelebA Jigsaw
Benchmarks: Adult COMPAS CelebA Jigsaw
Metrics: demographic parity violation equalized odds violation equalized opportunity violation accuracy coverage of confidence intervals proportion of baseline trade-offs in unlikely/permissible/su training time
Baselines: adversary logsig reductions linear KDE-fair RTO
Builds on: You-Only-Train-Once (YOTO) FiLM Hoeffding's inequality Bernstein's inequality
Closest papers by meaning
- Rethinking Pareto Frontier: On the Optimal Trade-offs in Fair Classification (ICLR 2026 · similarity 0.92)
- Fairness without Harm: An Influence-Guided Active Sampling Approach (NeurIPS 2024 · similarity 0.88)
- Kernel-based Equalized Odds: A Quantification of Accuracy-Fairness Trade-off in Fair Representation Learning (NeurIPS 2025 · similarity 0.88)
- FairTrade: Achieving Pareto-Optimal Trade-Offs between Balanced Accuracy and Fairness in Federated Learning (AAAI 2024 · similarity 0.88)
- The Fragility of Fairness: Causal Sensitivity Analysis for Fair Machine Learning (NeurIPS 2024 · similarity 0.88)
- Geometry of Relaxed Fair Regression: A Unified Framework for Aware and Unaware Settings (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.