Fair Supervised Learning Through Constraints on Smooth Nonconvex Unfairness-Measure Surrogates

Technical Summary: Fair Supervised Learning Through Constraints on Smooth Nonconvex Unfairness-Measure Surrogates

Problem Statement
Supervised machine learning models, while effective in domains such as finance, criminal justice, hiring, and healthcare, often inherit or introduce biases that lead to discriminatory outcomes. These biases manifest as unfairness in predictions across different demographic groups. Existing strategies to mitigate unfairness generally fall into pre-processing, in-processing, or post-processing categories. This paper focuses on in-processing strategies, specifically the incorporation of unfairness measures into the optimization problems used for model training.

Current approaches face significant computational and theoretical challenges:

1. Non-smoothness and Nonconvexity: Direct formulation of unfairness measures (e.g., Demographic Parity, Disparate Impact) involves discontinuous Heaviside step functions, leading to nonconvex and nonsmooth optimization problems that are difficult to solve.
2. Limitations of Convex Surrogates: To address computational difficulties, researchers often employ convex surrogates (e.g., covariance-based approximations). However, these do not guarantee that the original unfairness measure remains within acceptable limits; a small surrogate value does not necessarily imply a small actual unfairness measure.
3. Limitations of Regularization: The widespread use of regularization terms (soft constraints) to enforce fairness requires expensive hyperparameter tuning. Furthermore, increasing regularization strength to reduce unfairness can severely degrade prediction accuracy, and the relationship between the regularization parameter and the resulting unfairness is often non-monotonic and difficult to control.
4. Handling Multiple Measures: Strategies attempting to balance multiple, potentially conflicting unfairness measures via regularization often result in intractable training problems and further tuning costs.

Methodology
The authors propose a new in-processing strategy that combines smooth nonconvex surrogates with hard constraints to enforce fairness.

1. Smooth Nonconvex Surrogates:
   Instead of using convex approximations or discontinuous step functions, the authors introduce smooth, bounded, nonconvex surrogates to approximate the Heaviside function. Two specific approximations are utilized:

   • The sigmoid function.
   • A smoothed-step function derived from optimization literature smoothing techniques (specifically, a piecewise-affine approximation smoothed via a square-root term).

   Crucially, these surrogates are bounded within $[0, 1]$ and are scaled (via a parameter $\alpha$) to ensure they closely approximate the step function. The authors prove (via Theorem 2.1, derived from prior work) that if the surrogate value is small, the actual empirical unfairness measure is also small, provided the surrogate values are sufficiently close to 0 or 1. This tight approximation is not guaranteed by unbounded linear or convex surrogates.

2. Hard Constraints:
   Rather than adding unfairness measures as regularization terms in the objective function, the authors formulate the training problem as a constrained optimization problem:
   $$\min_w \sum_{i \in [N]} \ell(N(x_i, s_i, w), y_i) + \frac{1}{\lambda}r(w) \quad \text{subject to} \quad l \leq c(w) \leq u$$
   Here, $c(w)$ represents the vector-valued surrogate for one or more unfairness measures (e.g., Disparate Impact, Equal Impact). The bounds $l$ and $u$ enforce specific tolerances for unfairness directly.

   • Tractability: The authors leverage recent stochastic Newton/Sequential Quadratic Programming (SQP) techniques to solve these nonconvex constrained problems efficiently.
   • Stochastic Gradients: Theorem 3.1 demonstrates that unbiased stochastic gradient estimates can be obtained for the constraint functions if mini-batches maintain a balanced number of samples from each sensitive group.

Key Contributions

1. Tight Surrogate Approximation: The paper introduces smooth, nonconvex, bounded surrogates that provide a theoretical guarantee: if the surrogate constraint is satisfied, the actual unfairness measure is bounded. This contrasts with convex surrogates where a small surrogate value does not guarantee low unfairness.
2. Hard Constraints vs. Regularization: The authors propose using hard constraints instead of regularization. This eliminates the need for expensive tuning of regularization parameters and avoids the non-monotonic behavior often seen in regularization-based approaches. It allows for the explicit enforcement of specific unfairness tolerances.
3. Scalability to Multiple Measures: The framework naturally accommodates multiple, potentially conflicting unfairness measures simultaneously within a single optimization problem, without the computational explosion associated with tuning multiple regularization weights.

Experimental Results
The authors evaluated their method on three benchmark datasets: Dutch (income prediction, sensitive attribute: gender), Law School (bar passage, sensitive attribute: race), and ACSIncome (income prediction, sensitive attribute: gender).

• Surrogate Tightness: Experiments showed that unscaled surrogates led to gaps between desired and actual fairness levels. However, when surrogates were scaled (e.g., $\alpha=50$), the realized fairness levels tightly matched the imposed constraints for both smoothed-step and sigmoid functions. In contrast, covariance-based surrogates made it difficult to map a specific constraint value to a desired fairness level.
• Constraint vs. Regularization: Comparing the proposed "constraint-only" approach against a "regularization-only" approach revealed that the constraint method achieved monotonic improvement in fairness as thresholds tightened, whereas the regularization method exhibited unpredictable, non-monotonic behavior. The constraint approach maintained high prediction accuracy even as fairness constraints became active, whereas the regularization approach often suffered significant accuracy drops when attempting to enforce strict fairness.
• Multiple Measures: The framework successfully enforced simultaneous constraints on Disparate Impact and Equal Impact. While adding multiple constraints reduced accuracy slightly more than single constraints, the method consistently satisfied both criteria, demonstrating robustness in handling complex fairness requirements.

Significance and Claims
The paper claims that its approach offers a tractable training paradigm for fair supervised learning. By solving a single constrained optimization problem, practitioners can obtain models that meet prescribed limits on unfairness without the computational burden of tuning regularization parameters. The authors emphasize that while solving constrained nonconvex problems is more expensive per iteration than unconstrained ones, the overall computational cost is reduced by eliminating the need for extensive hyperparameter search. The method is presented as a robust solution for real-world applications where strict fairness guarantees are required alongside high predictive accuracy.