Research map / Learning theory and algorithms / Fairness

Efficient Fairness-Performance Pareto Front Computation

NeurIPS 2025 · Learning theory and algorithms › Fairness · approach: Fairness-constrained classification · 1 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.

Proposes MIFPO, a model-independent discrete concave-minimization formulation (solved with DCCP) that computes the optimal fairness-performance Pareto front for total-variation statistical parity via structural results on fair representations, without training fair representation models.

Problem

Computing the optimal fairness-performance Pareto front of fair representations (and fair classifiers) under total-variation fairness, which currently requires training complex non-convex fair representation models whose results may be far from the true front.

Approach

Factorization lemma maps features to Bayes posteriors in a small simplex, an invertibility theorem restricts to representations where each point has at most two parents (one per group), and a uniform approximation lemma discretizes the problem into MIFPO, a concave minimization with linear constraints that works for any concave performance measure.

Key results

• MIFPO's Pareto front is equal to or above the baseline fair representation methods (CVIB, FCRL, FNF, sIPM, Fare) at almost all operating points on Health, ACSIncome-CA and ACSIncome-US.
• Experiments use k=5 points per pair and a discretization into L bins; all experiments run in under a day on a standard desktop.
• Reported std across runs of the MIFPO method is <= 1e-5.

Measured effects reported in the paper

Limitations

• Restricted to binary sensitive attribute and binary target in the main development; multi-label and multi-valued attributes require larger discretizations.
• Solved with DCCP (CCP local method), so global optimality is not guaranteed in theory, though not observed in experiments.
• Fairness measured only by total variation / statistical parity.

Experimental setup

Datasets: Health ACSIncome-CA ACSIncome-US

Benchmarks: Health ACSIncome-CA ACSIncome-US

Metrics: accuracy statistical parity distance

Baselines: CVIB FCRL FNF sIPM Fare

Builds on: DCCP XGBoost isotonic regression calibration

Closest papers by meaning

• Rethinking Pareto Frontier: On the Optimal Trade-offs in Fair Classification (ICLR 2026 · similarity 0.91)
• Demystifying the Optimal Fair Classifier in Multi-Class Classification (ICML 2026 · similarity 0.90)
• Faster Fair Machine via Transferring Fairness Constraints to Virtual Samples (AAAI 2023 · similarity 0.88)
• Fair and Optimal Classification via Post-Processing (ICML 2023 · similarity 0.88)
• Kernel-based Equalized Odds: A Quantification of Accuracy-Fairness Trade-off in Fair Representation Learning (NeurIPS 2025 · similarity 0.88)
• Simple and Effective Specialized Representations for Fair Classifiers (NeurIPS 2025 · similarity 0.87)