Technical Summary: Counterfactually Fair Regression via Optimal Transport

Problem Statement

The paper addresses the challenge of learning a counterfactually fair regressor in high-stakes domains (e.g., student admissions) where predictions must be invariant to interventions on sensitive attributes (e.g., gender, race). Unlike standard fairness notions like Demographic Parity (DP), which only require marginal distributional equality across groups, Counterfactual Fairness (CF) demands that predictions remain unchanged if the sensitive attribute were altered, holding the individual's latent "ability" constant.

A significant barrier to deploying CF is the requirement for complete Structural Causal Models (SCMs), which are rarely available in practice. The authors adopt a "causal uncertainty" perspective (specifically the Level-2 setting of Kusner et al.), where the full causal graph is unknown, but a measurable proxy for the latent ability variable $V$ (denoted as $\psi(X, S)$) is accessible. The goal is to construct a post-processing estimator that recalibrates a pre-trained "black-box" predictor without retraining, providing rigorous finite-sample statistical guarantees.

Methodology

1. Theoretical Reduction: CF to Conditional DP

The core theoretical insight is that under the causal uncertainty setting with re-sampled noise, Counterfactual Fairness is equivalent to Demographic Parity conditional on the latent variable $V$.

• Definition: A predictor is CF if, for any fixed latent ability $v$, the distribution of predictions is identical across all sensitive groups $s$.
• Implication: This reduces the complex counterfactual problem to a conditional optimal transport problem. The authors show that the optimal fair predictor minimizes the risk subject to the constraint that the conditional prediction distributions $\mu_{f|v,s}$ coincide for all $s$.

2. Closed-Form Solution via Optimal Transport

Using the theory of Optimal Transport (OT), the authors derive a closed-form expression for the optimal fair regressor $f^*_0$.

• Barycentric Quantile Map: The optimal predictor maps the original prediction $f^*(x, s)$ to a Wasserstein-2 barycenter of the group-conditional distributions.
• Formula:
  $$f^*_0(x, s) = \left( \sum_{s'=1}^K w_{s'} F^{-1}_{f^*|v, s'} \right) \circ F_{f^*|v, s}(f^*(x, s))$$
  where $v = \psi(x, s)$, $w_s$ are group weights, and $F^{-1}$ denotes the quantile function. This operation effectively aligns the prediction distributions of different groups within the same latent ability level.

3. Discretized Post-Processing Estimator

Since $V$ is continuous, the authors propose a practical discretized post-processing algorithm:

• Discretization: The latent space $V$ is partitioned into $L$ intervals.
• Local Estimation: Within each interval, the conditional cumulative distribution functions (CDFs) and quantile functions are estimated from data.
• Plug-in Estimator: The closed-form barycentric map is applied locally within each interval using empirical estimates.
• Sample Splitting: To ensure statistical independence between the estimation of CDFs and the application of the transport map, the data is split (folding).

4. Relaxed Counterfactual Fairness

Recognizing that exact fairness may be unattainable or undesirable, the paper extends the framework to relaxed CF.

• Trade-off: The authors define a relaxed problem where the unfairness is bounded by a budget $\alpha U(f^*)$.
• Convex Combination: The optimal relaxed predictor is shown to be a convex combination of the original black-box predictor and the optimal fair predictor:
  $$f^*_\alpha = \sqrt{\alpha} f^* + (1-\sqrt{\alpha}) f^*_0$$
• Tuning: An explicit rule is provided to select $\alpha$ to meet a prescribed unfairness budget while accounting for estimation error.

Key Contributions

1. CF Reduction: The paper establishes that under causal uncertainty and awareness, Counterfactual Fairness is equivalent to Demographic Parity conditional on the latent ability $V$. This connects CF to existing DP methodologies.
2. Closed-Form Optimal Regressor: It derives the exact form of the optimal fair predictor using a barycentric quantile construction, providing a constructive solution rather than an abstract existence proof.
3. Finite-Sample Guarantees: The authors propose a model-agnostic post-processing method and prove high-probability finite-sample guarantees.
   • Both the unfairness and the excess risk decay at a rate of $\tilde{O}(n^{-1/3})$.
   • They establish a matching lower bound, proving that this rate is fundamental to the problem of estimating fair regressors under these conditions, not merely an artifact of the discretization.
4. Relaxed Fairness with Tuning: The work extends to relaxed CF, providing explicit tuning rules to navigate the risk-unfairness trade-off.

Results

Synthetic Data

• Validation of Theory: Experiments confirm that unfairness decreases as the discretization level $L$ increases, stabilizing near the theoretically optimal $L^*$.
• Trade-off: The method dominates baselines on the CF frontier. While strict causal methods (Fair K) achieve perfect fairness by discarding observable features (leading to high error), and global DP methods (WFR) achieve low error but fail CF, the proposed method achieves near-perfect CF with significantly lower error than Fair K.

Real-World Data (Law School Dataset)

• Performance: Applied to the LSAC dataset (predicting first-year grades), the method bridges the gap between accuracy and fairness.
  • Compared to Fair K (causal baseline), the proposed method maintains similar accuracy (RMSE $\approx$ 1.054 vs 1.086) while reducing conditional unfairness by an order of magnitude.
  • Compared to WFR (global DP baseline), it achieves significantly lower conditional unfairness (0.009 vs 0.088) with comparable accuracy.
• Robustness to Proxy Estimation: The paper evaluates the impact of estimating the latent proxy $V$ using Structural Causal Models (SCM) versus Variational Autoencoders (VAE). It highlights that "proxy leakage" (where $V$ retains information about $S$) degrades fairness, but the method remains robust when using a "Fair VAE" that explicitly disentangles $V$ from $S$.

Significance and Claims

The paper claims to provide the first model-agnostic post-processing framework for counterfactual fairness that offers rigorous finite-sample statistical guarantees without requiring retraining or access to the full causal graph.

• Theoretical Depth: By proving that the $n^{-1/3}$ convergence rate is a fundamental lower bound (via Assouad's Lemma), the authors argue that the slow convergence is the intrinsic "price of fairness" in non-parametric settings, rather than a limitation of their specific algorithm.
• Practical Utility: The approach is designed for scenarios where models are proprietary or third-party, or where training data is unavailable, making it highly applicable to real-world deployment.
• Nuanced Fairness: The work moves beyond the debate of whether global DP is sufficient for CF by showing that conditional DP (on the latent variable) is the correct structural reduction, offering a new perspective on the relationship between these fairness notions.

The authors conclude that their method successfully balances the trade-off between predictive utility and counterfactual fairness, offering a calibrated approach to meet specific fairness budgets while maintaining statistical validity.