Stochastic Optimization of Global Fairness Constraints

This direction is split into other directions: stochastic fairness optimization. Its last version stays readable and citable here.

Version 1 of 120 papers35 conceptsfrozen 2026-10-04

Machine learning models are typically trained using Stochastic Gradient Descent (SGD), which updates parameters based on small, random "mini-batches" of data. While this works perfectly for standard loss functions like cross-entropy—where the total loss is simply the average of individual losses—it fails for fairness.

Fairness metrics, such as Demographic Parity or Equalized Odds, are global properties. They are defined by ratios or distributions across an entire population. When you calculate a fairness metric on a tiny mini-batch, the estimate is not just noisy; it is often mathematically biased. This "batch-size bottleneck" has historically forced researchers to choose between using massive, memory-intensive batches or sacrificing fairness for the sake of scalability.

Recent research has bridged this gap by developing stochastic optimization frameworks that allow global fairness constraints to be enforced using standard, small-batch training.

The Problem of Biased Gradients

The core challenge is that many fairness objectives are non-linear functions of the data. For example, if a fairness metric involves a ratio of selection rates between two groups, the average of ratios across several mini-batches does not equal the ratio of the averages across the whole dataset.

As noted by Sina Baharlouei, Shivam Patel, and Meisam Razaviyayn in their work on $f$-FERM, standard fairness-constrained methods exhibit severe instability when batch sizes are small. This instability arises because the "local" gradient calculated from a mini-batch points in a different direction than the "global" gradient of the actual fairness constraint.

Variational Reformulations and Min-Max Games

To solve this, researchers transform global constraints into a form that SGD can handle. One common approach is variational reformulation using the Legendre-Fenchel transformation.

In $f$-FERM, the authors use dual representations of fairness metrics to turn the problem into a min-max game (similar to a GAN). By introducing "dual variables" that track the fairness violation, the model can estimate unbiased gradients even from tiny mini-batches. Similarly, A. S. Poornash and Andrew Lowy demonstrate in SteFFLe that formulating fairness as a min-max problem with divergence regularizers allows for dynamic penalization of bias during decentralized training.

Correcting Bias with U-Statistics

Another path to scalability involves changing how we calculate the gradients themselves. In Metrizing Fairness, Yves Rychener, Bahar Taskesen, and Daniel Kuhn 0001 introduce unbiased gradient estimators derived from U-statistics.

By adding a specific bias-correction term to the mini-batch calculation, they ensure that the expected value of the mini-batch gradient exactly matches the global gradient. This allows fair models to be trained with the same high-speed SGD used for standard models, preventing the systematic errors that usually plague small-batch fairness optimization.

Maintaining Global State via Buffers and Tracking

When data is decentralized or the model is extremely sparse, even unbiased estimators need help. Several researchers have proposed mechanisms to "remember" the global distribution across iterations:

  1. Replay Buffers: In Balancing Act, Meraj Hashemizadeh and Golnoosh Farnadi use a replay buffer of recent evaluation results to stabilize fairness signals for sparse models. This reduces the variance of the gradient, ensuring that pruning a model doesn't accidentally introduce massive demographic bias.
  2. Moving Averages: For complex ranking tasks, Boyang Zhang and Tianbao Yang developed KSO-RED, which uses stochastic moving average estimators. This allows the system to track "exposure equality" across a massive dataset without needing to sort the entire list of items in every step.
  3. Function Tracking: In Federated Learning, where data never leaves the user's device, Yves Rychener and Daniel Kuhn proposed a function-tracking scheme. Clients share a tiny number of scalar predictions (as few as 50) to help the central server track the global fairness gradient without compromising privacy.

Scaling Fairness to Big Data

The shift from full-batch to stochastic fairness optimization is what makes "Fair AI" practical for production. As Mohammad Mahdi Kamani and Mehrdad Mahdavi argue in their work on Efficient Fair PCA, transitioning to mini-batch processing is the only way to scale fairness-aware techniques to environments where datasets exceed memory capacity.

By treating fairness not as a static post-processing step, but as a dynamic objective that can be tracked and optimized through standard backpropagation—as demonstrated by T. Hänel and Stefan Gumhold in visual attribute prediction—the field has moved toward a future where equity is a first-class citizen in large-scale machine learning pipelines.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_stochastic_optimization_of_global_fairne_a98e83b7,
  title = {Stochastic Optimization of Global Fairness Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-optimization-of-global-fairness-constraints/rdr_a98e83b73d86419589bba130921e8f8e},
  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_optimization_of_global_fairne_a98e83b7_v1,
  title = {Stochastic Optimization of Global Fairness Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-optimization-of-global-fairness-constraints/rdr_a98e83b73d86419589bba130921e8f8e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}