Stochastic Optimization for Fair Machine Learning

22 concepts11 papers1 proposal

Standard deep learning relies on Stochastic Gradient Descent (SGD), where a model updates its weights based on small, random subsets of data called mini-batches. This works beautifully for standard empirical risk minimization because the average loss of a mini-batch is an unbiased estimator of the true global loss. However, as Padala et al. demonstrate in FNNC: Achieving Fairness through Neural Networks and Buyl et al. show in fairret: a Framework for Differentiable Fairness Regularization Terms, this fundamental assumption completely breaks down when we introduce fairness constraints.

Fairness metrics—such as demographic parity, equalized odds, or max-min group fairness—are fundamentally global population statistics. They often take the form of non-linear or fractional functions, such as the ratio of selection rates between two demographic groups. When you try to compute these metrics over a small mini-batch during training, you encounter two severe issues:

  1. Data Slicing Noise: To evaluate group fairness, you must slice the mini-batch by demographic attributes. As noted by D'Amour et al. in Fairness and robustness in anti-causal prediction, calculating statistics on these tiny, fragmented slices introduces extreme gradient noise and numerical instability, preventing deep learning models from effectively converging.
  2. Statistical Bias: Because fairness metrics are non-linear, the expectation of the mini-batch fairness loss does not equal the true fairness loss over the entire dataset.

The Hidden Parameter: Batch-Size Dependent Bias

To understand why mini-batch fairness estimation is inherently biased, consider Jensen's Inequality, which states that for a non-linear function $f$, the expected value of the function is not equal to the function of the expected value: $\mathbb{E}[f(X)] \neq f(\mathbb{E}[X])$.

Xu et al. demonstrate in Bridging Jensen Gap for Max-Min Group Fairness Optimization in Recommendation that batch size acts as a critical hidden parameter in fair optimization. When mini-batches are small, the discrepancy between the estimated batch fairness and the actual population fairness (the Jensen gap) widens significantly.

Consequently, a model might appear perfectly fair according to its mini-batch statistics during training, yet remain highly unfair when evaluated on the full dataset. As Lowy et al. observe in A Stochastic Optimization Framework for Fair Risk Minimization, traditional optimization methods force a brutal trade-off: to get accurate fairness gradients, practitioners must use massive batch sizes, which is computationally intractable for large-scale deep learning and rules out online learning.

Reformulating Fairness via Mathematical Duality

How can we optimize a global, non-linear constraint using small mini-batches without introducing bias? The core insight across this research direction is to reformulate the optimization problem using mathematical duality.

By applying techniques like the Legendre-Fenchel transformation, researchers convert complex, non-decomposable fairness constraints into an equivalent min-max optimization problem (a saddle-point problem). Yurochkin et al. utilize this dual transformation in SenSeI: Sensitive Set Invariance for Enforcing Individual Fairness to handle worst-case variations in sensitive attributes for individual fairness. For group fairness, Lowy et al. in FERMI: Fair Empirical Risk Minimization via Exponential Rényi Mutual Information and Baharlouei et al. in f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization show that introducing auxiliary dual variables allows the global, fractional objective to be decoupled.

Crucially, in this dual min-max formulation, the objective function becomes smooth and linear with respect to the data distribution. This mathematical transformation means that we can now derive stochastically unbiased gradient estimators from small mini-batches, or even single data points. The global population constraint is effectively tracked and enforced via the auxiliary variables, which update alongside the model parameters.

Stable Convergence at Scale

With unbiased gradients in hand, fairness-aware machine learning can finally leverage the full power of modern stochastic optimization. Instead of standard SGD, models are trained using a Stochastic Gradient Descent-Ascent (SGDA) procedure. The model parameters minimize the loss, while the auxiliary dual parameters maximize the penalty for fairness violations.

This framework proves remarkably robust and scalable across diverse domains:

By shifting from naive mini-batch approximation to mathematically rigorous dual reformulations, this paradigm bridges the gap between local stochastic updates and global societal constraints, making fair machine learning practical for massive, high-dimensional models.

Key Foundational Work

FNNC: Achieving Fairness through Neural Networks (2020) — contributed 4 concept elements to this direction.
FERMI: Fair Empirical Risk Minimization via Exponential Rényi Mutual Information (2021) — contributed 3 concept elements to this direction.
SenSeI: Sensitive Set Invariance for Enforcing Individual Fairness (2021) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_stochastic_fairness_optimization_5278cfbf,
  title = {stochastic fairness optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-fairness-optimization/rdr_5278cfbf03ad42189a1e036b32cd87b4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_stochastic_fairness_optimization_5278cfbf_v1,
  title = {stochastic fairness optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-fairness-optimization/rdr_5278cfbf03ad42189a1e036b32cd87b4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake