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:
- 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.
- 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:
- Privacy and Utility: Lowy et al. extended this min-max framework in Stochastic Differentially Private and Fair Learning, proving that it prevents the utility collapse typically seen when combining privacy and fairness constraints at scale.
- Recommendation Systems: In large-scale recommender systems where full-dataset operations are impossible, Li et al. in FEIR: Quantifying and Reducing Envy and Inferiority for Fair Recommendation of Limited Resources combined mini-batching with user-item sampling to approximate global fairness metrics efficiently.
- Information Retrieval: For top-$K$ ranking, Zhang et al. in Learning to Rank with Top-K Fairness introduced stochastic moving average estimators for composite functions, allowing production-scale systems to enforce complex equity constraints with minimal computational overhead.
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.