Technical Summary: Functional Bilevel Optimization for Predictive Fairness

Problem Statement

Standard machine learning models often exploit statistical signals tied to sensitive attributes (e.g., age, income, demographic scores), leading to unfair predictions. While fairness is often framed as enforcing full statistical independence between predictions and sensitive attributes, this approach is frequently too restrictive, particularly when sensitive attributes are continuous and high-dimensional. In such regimes, full independence constrains the entire prediction distribution, whereas the practical fairness concern is often limited to systematic shifts in average predictions across different values of the sensitive attribute.

Existing relaxations for continuous attributes rely on indirect dependence penalties (e.g., HSIC, mutual information), adversarial schemes, or linear-dependence constraints. These methods often fail to directly target the specific fairness-accuracy trade-off of controlling the conditional mean, or they are limited to low-dimensional or discrete attributes.

The authors propose addressing this gap by optimizing Mean Demographic Parity, formalized as minimizing the variance of the conditional-mean prediction given the sensitive attribute. This metric is termed DPVar:
$$\text{DPVar}(\omega) = \text{Var}_A \left( \mathbb{E}[f_\omega(X) \mid A] \right)$$
where $f_\omega$ is the predictor and $A$ is the sensitive attribute.

Methodology

The Functional Bilevel Formulation

Optimizing DPVar presents a unique challenge: the objective depends on the conditional mean function $h^\star_\omega(a) = \mathbb{E}[f_\omega(X) \mid A=a]$, which is unknown and must be estimated from data. The authors formulate this as a functional bilevel optimization problem:

1. Inner Problem: Estimate the conditional mean function $h^\star_\omega$ by minimizing the squared loss between the predictor's output and the function of the sensitive attribute:
   $$h^\star_\omega \in \arg\min_{h \in \mathcal{H}} \mathbb{E}[(f_\omega(X) - h(A))^2]$$
2. Outer Problem: Optimize the predictor parameters $\omega$ to minimize a trade-off between prediction accuracy and the DPVar penalty (which depends on the solution $h^\star_\omega$ of the inner problem):
   $$\min_\omega \mathbb{E}[(f_\omega(X) - Y)^2] + \alpha \text{Var}_A(h^\star_\omega(A))$$

Because the inner variable is a function rather than a finite-dimensional parameter vector, this is a functional bilevel problem.

Proposed Algorithms

The paper introduces two algorithms to solve this problem, both utilizing a data split into IN (for inner estimation) and OUT (for outer evaluation) to prevent optimistic bias.

1. FBO (Functional Bilevel Optimization):

   • Mechanism: This method exploits the specific structure of the squared-loss inner problem. The authors derive a closed-form adjoint for the sensitivity of the inner solution with respect to the outer parameters.
   • Advantage: This derivation yields an exact, Hessian-free hypergradient. It avoids the computational cost of inverting Hessians or computing inner Jacobians, requiring only one inner regression and two empirical means per outer step.
   • Limitation: It is specific to the squared-loss inner objective.

2. ITD (Iterative Differentiation):

   • Mechanism: This method uses a broader strategy of unrolling the inner optimization steps. The inner regressor is updated for $K$ gradient steps, and the outer objective is differentiated through this unrolled computation graph.
   • Advantage: It is generalizable to non-squared-loss inner objectives (e.g., Huber loss) and does not require a closed-form inverse of the inner Hessian.
   • Trade-off: It is approximate and computationally more expensive per outer step (scaling linearly with $K$) compared to FBO.

Key Contributions

1. DPVar Criterion: The adoption of DPVar as a fairness criterion specifically designed for continuous and high-dimensional sensitive attributes, moving beyond full independence to a conditional-mean view.
2. Functional Bilevel Framework: The formulation of DPVar optimization as a functional bilevel problem that integrates naturally with neural network predictors, a regime not covered by prior conditional-mean approaches.
3. Algorithmic Innovations:
   • Derivation of a closed-form adjoint for the squared-loss case, enabling the exact FBO algorithm.
   • Development of the ITD algorithm for broader applicability via iterative differentiation.
4. Semi-Synthetic Benchmark: The creation of a large-scale, standardized evaluation suite built from 60 real tabular regression datasets. This benchmark automatically constructs continuous sensitive attributes from features to provide controlled, nontrivial fairness-accuracy trade-off scenarios.

Experimental Results

The methods were evaluated on synthetic data and the new semi-synthetic tabular benchmark against strong baselines, including HSIC, adversarial debiasing, linear-dependence penalties, and Generalized Demographic Parity (GDP).

• Synthetic Data: In regimes where unfairness is driven by first-moment shifts, all methods perform similarly. However, as the prediction problem becomes more complex (introducing interactions between sensitive and non-sensitive features), FBO and ITD consistently achieve better fairness-accuracy trade-offs. They outperform methods relying on full distributional independence (HSIC, adversarial) or linear penalties, which are either too restrictive or miss nonlinear effects.
• Tabular Benchmark: Across 27 informative datasets, FBO and ITD achieve the lowest or near-lowest aggregate accuracy regret under DPVar constraints.
  • Under tight and mid-level fairness budgets, FBO and ITD win most often.
  • Under loose budgets, GDP becomes a stronger competitor.
  • Both proposed methods consistently match or outperform HSIC, adversarial, and linear-dependence baselines.

Significance and Claims

The paper claims that by targeting the conditional mean rather than the full distribution, DPVar offers a more appropriate and estimable fairness measure for continuous, high-dimensional attributes. The significance of the work lies in:

• Providing a direct optimization path for this specific fairness criterion, avoiding the indirectness of adversarial or kernel-based penalties.
• Demonstrating that functional bilevel optimization can be made practical and efficient (via FBO) for modern neural network predictors.
• Offering a standardized benchmark that moves beyond hand-picked datasets to systematically evaluate fairness methods on continuous attributes.

Scope and Limitations:
The authors explicitly note that DPVar is a mean-parity criterion. It controls systematic shifts in average predictions but does not guarantee equality of higher-order moments (variance, tails) or full distributional fairness. Consequently, it should not be interpreted as a certificate for overall fairness in applications requiring full distributional equality. Furthermore, the method relies on estimating a conditional mean function, which can be statistically challenging in high dimensions. The benchmark is semi-synthetic, designed for methodological evaluation rather than making specific legal or social fairness claims about the original datasets.