Efficient Fairness-Performance Pareto Front Computation

Conference: NeurIPS 2025 arXiv: 2409.17643 Code: bp6725/FairPareto Area: AI Safety Keywords: fairness, Pareto front, fair representation, concave optimization, MIFPO

TL;DR

This paper proposes MIFPO, a method that efficiently computes the fairness-performance Pareto front without training complex fair representation models, by theoretically reducing the problem to a compact discrete concave optimization problem.

Background & Motivation

Fair representation learning is a central problem in fair machine learning. Given data features \(X\), sensitive attribute \(A\), and target variable \(Y\), the goal is to learn a representation \(Z\) that preserves predictive power for \(Y\) while satisfying fairness constraints with respect to \(A\). Stronger fairness constraints generally lead to lower classification performance, giving rise to the fairness-performance trade-off.

Existing methods primarily rely on complex neural network architectures (e.g., GANs, VAEs, Optimal Transport variants) and learn fair representations through non-convex optimization over high-dimensional parameter spaces. These approaches suffer from several drawbacks:

1. They are prone to local optima and sensitive to hyperparameters (architecture, learning rate, initialization).
2. It is difficult to determine whether the resulting fairness-performance curve approximates the true Pareto front.
3. Retraining the entire model is required whenever the fairness threshold \(\gamma\) changes.

This motivates the question: can the optimal Pareto front be computed directly, without relying on complex representation learning models?

Core Problem

Given a fairness measure (this paper uses Total Variation distance) and a concave performance measure \(h\), for each fairness threshold \(\gamma \in [0,1]\), compute the Pareto front curve defined by the optimal performance \(E(\gamma) = \min_Z \mathbb{E}_{z \sim Z} h(\mathbb{P}(Y|Z=z))\) over all representations \(Z\) satisfying \(D_{TV}(Z) \leq \gamma\).

The key challenge is that the representation space \(\mathcal{Z}\) can be arbitrarily large and the feature space \(\mathcal{X}\) is typically high-dimensional, making exhaustive search over all possible representations computationally infeasible.

Method

Step 1: Factorization Lemma

The core insight is that for computing the Pareto front, only the conditional distributions \(\mathbb{P}(Y|X=x, A=a)\) in the data are relevant. The high-dimensional feature space \(\mathcal{X}\) can therefore be mapped to the low-dimensional probability simplex \(\Delta_\mathcal{Y}\) via the Bayes-optimal classifier \(f^*(x,a) = \mathbb{P}(Y=\cdot|X=x,A=a)\).

For binary classification (\(Y \in \{0,1\}\)), \(\Delta_\mathcal{Y}\) reduces to the interval \([0,1]\), which can be readily discretized into \(L\) bins.

Step 2: Invertibility Theorem

Definition: A representation \(Z\) is invertible if and only if, for each \(z \in \mathcal{Z}\) and each \(a \in \{0,1\}\), at most one \(x\) satisfies \(\mathbb{P}(Z=z|X=x,A=a) > 0\).

Theorem 3.1: For any representation \(Z\), there exists an invertible representation \(Z'\) whose performance is no worse than \(Z\) and whose fairness is no worse than \(Z\). It therefore suffices to search for optimal solutions within the class of invertible representations.

Invertibility implies that each representation point \(z\) has at most two "parent" data points (at most one per sensitive attribute value), which greatly restricts the effective size of the representation space.

Step 3: MIFPO Discrete Optimization

Based on the above theoretical results, the paper formulates the Model Independent Fairness-Performance Optimization (MIFPO) problem:

• Representation space: \(\mathcal{Z} = S_0 \times S_1 \times [k]\), where \(S_0, S_1\) are the discretized feature sets (each with \(L\) bins) for the two sensitive groups, and \(k\) is an approximation parameter (set to \(k=5\) in experiments).
• Variables: Transition probabilities \(r_{u,v,j}^a\), representing the probabilistic mapping from data points to representation points.
• Objective: Minimize the concave performance function in Equation (14).
• Constraints: Probability normalization constraints (linear) and TV fairness constraints \(\leq \gamma\) (linear).

This is a concave minimization problem under linear constraints, which can be efficiently solved using the DCCP (Disciplined Convex-Concave Programming) framework.

Full Algorithm Pipeline

1. Train calibrated classifiers \(c_0, c_1\) on each sensitive group separately (using XGBoost + Isotonic Regression).
2. Discretize \(\Delta_\mathcal{Y}\) into \(L\) bins and estimate parameters \(\alpha, \beta, \rho\).
3. Construct and solve the MIFPO instance for a given \(\gamma\).
4. Sweep over different values of \(\gamma\) to obtain the complete Pareto front.

Equivalence to Fair Classification

Lemma 3.1 establishes that, under binary classification, accuracy, and statistical parity, the Pareto front of fair representation learning is equivalent to that of fair classification. Consequently, MIFPO can serve as an evaluation benchmark for both fair representation and fair classification methods.

Key Experimental Results

The method is evaluated on three standard fairness benchmark datasets: Health, ACSIncome-CA, and ACSIncome-US.

Baseline	Type	Relation to MIFPO
CVIB	Fair representation	MIFPO consistently matches or outperforms
FCRL	Fair representation	MIFPO consistently matches or outperforms
FNF	Fair representation	MIFPO consistently matches or outperforms
sIPM	Fair representation	MIFPO consistently matches or outperforms
Fare	Fair representation	MIFPO consistently matches or outperforms

MIFPO achieves performance comparable to or better than all baselines at nearly every operating point, while tracing the complete Pareto front curve (rather than discrete points corresponding to specific hyperparameter configurations). In practice, MIFPO serves as a performance upper bound for the other methods.

Highlights & Insights

1. Theoretical elegance: Two structural theorems—the Factorization Lemma and the Invertibility Theorem—reduce a high-dimensional continuous optimization problem to a compact discrete one, with rigorous derivations throughout.
2. Model independence: No complex generative models (GANs/VAEs) are required; the method relies solely on calibrated classifiers and is straightforward to implement.
3. General performance measure: Any concave performance measure (e.g., log loss) is supported, unlike existing reduction-based methods that are restricted to accuracy.
4. Theoretical benchmark: Provides a theoretically grounded upper bound for evaluating other fair representation and classification methods.
5. Open-source implementation: A scikit-learn-compatible Python package is provided (PyPI: FairPareto), supporting both tabular and image data.

Limitations & Future Work

1. Binary sensitive attributes only: The current theory and algorithm are restricted to \(A \in \{0,1\}\). While the Invertibility Theorem can be extended to multi-valued \(A\), doing so increases the size of the MIFPO problem.
2. Primarily targets binary classification: Multi-label classification requires more complex discretization schemes (e.g., clustering).
3. Dependence on calibration quality: Parameter estimation in MIFPO relies on accurate estimation of \(\mathbb{P}(Y|X,A)\); poor calibration can degrade results.
4. Local optimality risk of DCCP solver: Although not observed in experiments, global optimality of concave minimization is not theoretically guaranteed (branch-and-bound can be used but is slower).
5. Problem size scales with \(L\) and \(k\): The number of variables is \(O(L^2 \cdot k)\), and more efficient solvers may be needed for large-scale instances.

Related Work & Insights

Method	Requires Training	Supports General Loss	Full Pareto Front	Multi-valued Sensitive Attr.
MIFPO (Ours)	Calibrated classifier only	Yes (any concave function)	Yes	No
Xian et al. 2023	No	No (accuracy only)	Yes	Yes
Wang et al. 2023	No	No (accuracy only)	Yes	Yes
CVIB/FCRL/FNF, etc.	End-to-end training required	Implementation-dependent	No (discrete points)	Implementation-dependent

The most closely related works are Xian et al. and Wang et al., which similarly depart from the Bayes-optimal classifier but diverge in subsequent steps. Existing methods exploit the special structure of accuracy (reducing classifiers to small confusion matrices or restricting distributions to simplex vertices), whereas the proposed method handles the more general case.

The paper offers several broader insights. The idea of reducing continuous fairness optimization to discrete concave programming is elegant, analogous to discretization techniques in information bottleneck methods. The role of MIFPO as a theoretical benchmark—computing the achievable optimum to upper-bound all fairness methods—represents a valuable methodological perspective. Additionally, the transition probabilities \(r_{u,v,j}^a\) are essentially transport plans, drawing a natural connection between fairness research and Optimal Transport theory.

Rating

• Novelty: ⭐⭐⭐⭐ — The Factorization and Invertibility theorems provide a fundamentally new structural understanding of the problem.
• Experimental Thoroughness: ⭐⭐⭐ — Three datasets and multiple baselines, but limited to the binary classification / binary sensitive attribute setting.
• Writing Quality: ⭐⭐⭐⭐ — Theoretical derivations are clear, notation is consistent, and the logical chain from theory to algorithm is concise.
• Value: ⭐⭐⭐⭐ — Provides a theoretical benchmark tool for fairness research, with an open-source implementation.

Related Papers

• [NeurIPS 2025] Cost Efficient Fairness Audit Under Partial Feedback
• [NeurIPS 2025] Incentivizing Time-Aware Fairness in Data Sharing
• [CVPR 2026] Computation and Communication Efficient Federated Unlearning via On-server Gradient Conflict Mitigation and Expression
• [NeurIPS 2025] FairContrast: Enhancing Fairness through Contrastive Learning and Customized Augmentation
• [NeurIPS 2025] Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity