Benchmarking Stochastic Approximation Algorithms for Fairness-Constrained Training of Deep Neural Networks

1. Problem Definition

The paper addresses the challenge of training Deep Neural Networks (DNNs) under fairness constraints. Specifically, it focuses on the Constrained Empirical Risk Minimization (ERM) problem, formulated as:

$$\min_{x \in \mathbb{R}^n} \mathbb{E}[f(x, \xi)] \quad \text{s.t.} \quad \mathbb{E}[c(x, \zeta)] \leq 0$$

Where:

• $f(x, \xi)$ represents the loss function (objective).
• $c(x, \zeta)$ represents the fairness constraints (e.g., bounding the difference in error rates between demographic subgroups).
• $\xi$ and $\zeta$ are random variables representing data samples.

Key Challenges:

• Non-convexity and Non-smoothness: The objective and constraint functions involve DNNs, making them non-convex and potentially non-smooth.
• Stochastic Constraints: Unlike standard constrained optimization, both the objective and the constraints are expectations that must be estimated via sampling (mini-batches).
• Inequality Constraints: The constraints are inequalities (e.g., $|Risk_A - Risk_B| \leq \delta$), which are harder to handle than equality constraints in stochastic settings.
• Lack of Benchmarks: There is no standard toolkit or benchmark for comparing stochastic approximation algorithms specifically for this type of fairness-constrained DNN training.

2. Methodology

A. Benchmark Construction

The authors created a new benchmark based on the US Census (Folktables) dataset, specifically the ACSIncome dataset.

• Task: Binary classification predicting if an individual's income exceeds $50,000.
• Protected Attributes:
  1. Binary: Race (White vs. Non-White).
  2. Multi-valued: Marital Status (5 categories).
• Fairness Definitions: The benchmark implements constraints based on loss differences across subgroups, covering three elementary fairness notions:
  • Independence: Statistical parity (Demographic Parity).
  • Separation: Equalized Odds (Equal True Positive/Negative Rates).
  • Sufficiency: Predictive Parity.

B. Algorithms Evaluated

The paper implements and compares four algorithms. Three are recent stochastic approximation methods proposed for constrained optimization, and one is a baseline regularized approach:

1. Stochastic Ghost (StGh): Combines a deterministic method (solving a subproblem to find a direction) with stochastic sampling. It uses a "ghost" penalty mechanism and geometric distribution sampling to handle feasibility.
2. Stochastic Smoothed and Linearized Augmented Lagrangian Method (SSL-ALM): Based on the Augmented Lagrangian (AL) framework. It uses a proximal AL function with a smoothing term and handles inequality constraints via slack variables. It is noted for not requiring large mini-batches.
3. Stochastic Switching Subgradient (SSw): A method that switches between updating based on the objective gradient (if constraints are satisfied) and the constraint subgradient (if violated). It uses subgradients to handle non-smoothness.
4. Baselines:
   • SGD: Standard unconstrained training.
   • SGD-Fairret: Unconstrained training with a differentiable fairness regularizer (penalty term) added to the loss.

C. Experimental Setup

• Hardware: Asus Zenbook (AMD Ryzen 7, 16GB RAM).
• Framework: Python/PyTorch.
• Hyperparameters: Extensive grid searches were performed on validation sets to tune learning rates, penalty multipliers, and step sizes for each algorithm.
• Metrics: Optimization performance (loss convergence, constraint violation) and Fairness performance (Independence, Separation, Sufficiency, Inaccuracy, and Wasserstein distance between group distributions).

3. Key Contributions

1. First Large-Scale Benchmark: The paper provides the first challenging benchmark for stochastic approximation algorithms in the context of fairness-constrained DNN training, utilizing real-world US Census data with up to 5.7 billion potential subgroup definitions.
2. Algorithmic Implementation & Comparison: It implements three recently proposed but previously untested algorithms (StGh, SSL-ALM, SSw) and compares them against a regularized baseline (Fairret) and standard SGD.
3. Theoretical Review: It reviews the theoretical landscape, highlighting that while many algorithms exist for stochastic optimization, few handle stochastic inequality constraints with non-smooth, non-convex objectives, and none currently offer convergence guarantees for this specific general setting.
4. Open Source Toolkit: The authors released a Python package to facilitate the benchmarking of new optimization methods for fairness.

4. Results

Optimization Performance

• Constraint Satisfaction:
  • ALM and SSL-ALM generally satisfied constraints on the training set effectively.
  • SSw satisfied constraints the best but failed to minimize the objective function (loss) as effectively as other methods.
  • StGh showed high variability in both loss and constraint values.
  • SGD (Unconstrained) minimized loss fastest but completely violated fairness constraints.
  • SGD-Fairret (Regularized) minimized loss slower than constrained methods and showed increasing constraint violations over time, consistent with the trade-off inherent in penalty methods.
• Generalization: On the test set, AL-based methods showed slight bias (constraint violation), reflecting the generalization behavior of fairness-constrained estimators.

Fairness Performance

• Trade-offs: All constrained methods improved fairness metrics (Independence, Separation, Sufficiency) compared to unconstrained SGD.
• Best Compromise: SSL-ALM and ALM provided the best trade-off, significantly improving fairness metrics while only moderately degrading accuracy compared to unconstrained SGD.
• SSw Performance: While SSw minimized constraint violation, its fairness metrics were comparable to unconstrained SGD, suggesting that with the chosen parameters, it prioritized the objective over the constraints.
• Regularization vs. Constraints: The constrained optimization approaches generally outperformed the penalty-based (Fairret) approach in maintaining a stable trade-off between accuracy and fairness.

5. Significance and Conclusion

• Practical Impact: The study demonstrates that Augmented Lagrangian-based methods (SSL-ALM) are currently the most robust practical choice for training fair DNNs under hard constraints, offering better control over the fairness-accuracy trade-off than penalty-based regularization.
• Theoretical Gap: The paper highlights a critical gap in the literature: there is currently no algorithm with theoretical convergence guarantees for the general setting of non-convex, non-smooth, stochastic inequality-constrained optimization.
• Future Directions: The work calls for further research into algorithms that can handle the specific challenges of fairness constraints (non-smoothness, stochasticity) with theoretical guarantees. It also emphasizes that fairness tools are not "silver bullets" and must be part of a broader interdisciplinary pipeline.

In summary, this paper establishes a rigorous standard for evaluating fairness algorithms, reveals the practical superiority of constraint-based methods over penalty-based methods in specific settings, and provides the necessary tools for the community to develop better optimization strategies for ethical AI.