Modern machine learning relies almost entirely on gradient descent. To train a model, we define a smooth loss function, calculate its derivatives, and iteratively nudge the model's weights down the slope toward a better solution.
However, when we try to enforce ethical or operational constraints—such as ensuring a model does not discriminate against specific demographic groups—we run into a mathematical wall. Standard fairness metrics like demographic parity, equalized odds, and disparate mistreatment are fundamentally discrete. They rely on counting outcomes: how many people were hired, how many loans were incorrectly denied, or how many faces were misidentified.
Because these metrics are built on top of step functions and hard thresholds, their gradients are either zero everywhere or completely undefined. If a model slightly adjusts its internal weights, the discrete count of false positives typically remains exactly the same—yielding a gradient of zero—until it crosses a threshold and abruptly jumps. This lack of differentiability makes it impossible for standard optimization algorithms to directly navigate the trade-offs between accuracy and fairness.
To overcome this, a major direction of research focuses on transforming these rigid, non-differentiable fairness constraints into smooth, mathematically tractable objectives.
Smoothing the Step with Differentiable Surrogates
The most direct way to bypass the gradient wall is to replace discrete indicator functions with smooth approximations, known as surrogates.
Consider a classifier that approves or denies loan applications based on a score. The actual decision relies on a hard threshold: if the score is above $0.5$, approve; otherwise, deny. To equalize the false positive rates across different groups, we would traditionally count the step-function changes.
Instead of optimizing this step function, we can relax the boundary. By passing the scores through a smooth sigmoid function, we map the hard binary decisions to continuous probabilities. A small change in the model's weights now produces a small, predictable change in the continuous surrogate fairness metric, generating a reliable gradient that the training loop can follow.
Discrete Step Function (No Gradient):
Score ───[ > 0.5 ]───► 0 or 1 (Derivative is 0 or undefined)
Smooth Surrogate Relaxation:
Score ───[ Sigmoid ]───► Continuous Probability [0, 1] (Smooth Gradients)
Early foundational work by Muhammad Bilal Zafar et al. in Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment pioneered this approach by utilizing "covariance proxies." Instead of directly forcing error rates to be equal, they constrained the covariance between the continuous sensitive attributes and the signed distance from the classifier's decision boundary.
However, substituting discrete metrics with smooth surrogates introduces a new challenge: the surrogate-fairness gap. As Wei Yao et al. demonstrate in Understanding Fairness Surrogate Functions in Algorithmic Fairness, minimizing a smooth surrogate loss does not guarantee that the actual, discrete classification error will be fair. Outliers or "large margin points" can disproportionately skew the surrogate function, leading to a model that appears fair during differentiable training but remains unfair when evaluated on final, hard decisions. To mitigate this, Harry Bendekgey et al. developed adaptive data re-weighting strategies in Scalable and Stable Surrogates for Flexible Classifiers with Fairness Constraints, preventing deep neural networks from collapsing or degenerating when subjected to these proxy constraints.
Distributional Alignment via Density Estimation and Optimal Transport
Rather than trying to smooth individual decisions, a second strategy shifts the perspective from individual samples to entire populations. If the distribution of model predictions looks identical across different demographic groups, the model is inherently fair, regardless of where the final decision threshold is drawn.
The challenge is that raw prediction histograms are inherently discrete and non-differentiable. Researchers solve this by using Kernel Density Estimation (KDE) to smooth out the data points into continuous probability density functions.
Jaewoong Cho et al. leveraged this intuition in A Fair Classifier Using Kernel Density Estimation. By placing a smooth Gaussian kernel over each model prediction, they transformed discrete group counts into differentiable density functions. This allowed them to directly minimize the mathematical divergence between group distributions using standard gradient descent. Jaewoong Cho later extended this concept to recommendation systems in Equal Experience in Recommender Systems, ensuring equitable item exposure across diverse user groups despite underlying data bias.
Discrete Counts (Non-Differentiable):
Group A: █ █ █ █
Group B: █ █ █ █
KDE Smoothed Distributions (Differentiable):
Group A: ╭─╮_╭──╮___╭─╮
Group B: __╭─╮___╭───╮
▲ Minimize the geometric area between curves
Alternatively, we can use Optimal Transport to measure and minimize the distance between these distributions. The Wasserstein distance calculates the minimum "geometric work" required to transform the prediction distribution of one demographic group into another.
Because the Wasserstein distance between continuous representations can be differentiated with respect to model parameters, it serves as an elegant geometric regularizer. Aldo Pacchiano et al. demonstrated this in Wasserstein Fair Classification, mapping prediction distributions to a shared group barycenter to achieve threshold-independent fairness. Similarly, Laurent Risser et al. utilized Wasserstein-2 regularization in Tackling Algorithmic Bias in Neural-Network Classifiers using Wasserstein-2 Regularization to force neural networks to yield equitable prediction profiles across continuous sensitive attributes like age or income.
Game Theoretic Reformulations of Max-Min Fairness
A particularly difficult subset of fairness optimization involves Max-Min Fairness (MMF). Instead of equalizing averages, MMF aims to protect the most vulnerable or worst-off group by maximizing the utility of the lowest-performing demographic.
Mathematically, the minimum operator introduces sharp, non-differentiable "kinks" into the optimization landscape. When the identity of the worst-performing group suddenly switches during training, the gradient experiences an abrupt discontinuity, causing standard optimization loops to stall or oscillate wildly.
The Max-Min Kink:
Performance ───► \ / ◄── The "minimum" operator creates a sharp,
\ / non-differentiable vertex where the
\ / worst-performing group switches.
\/
To resolve this, researchers reformulate the problem as a two-player zero-sum game. Instead of directly optimizing a non-differentiable min function, they introduce an adversarial player (a "referee"). The adversary's job is to assign weights to the different demographic groups, placing the highest weight on whichever group is currently experiencing the worst performance. The machine learning model then updates its parameters to maximize its performance under this adversarial weighting scheme.
By smoothing this interaction—often using entropy regularization to prevent the adversary from making abrupt, discrete weight shifts—the optimization landscape becomes perfectly differentiable.
Giseung Park et al. successfully applied this dual convex optimization framework to multi-objective reinforcement learning in The Max-Min Formulation of Multi-Objective Reinforcement Learning: From Theory to a Model-Free Algorithm, ensuring that no single objective is neglected during training. Building on this, Woohyeon Byeon et al. introduced a game-theoretic architecture in Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach that guarantees stable "last-iterate" convergence, drastically reducing the memory and computational overhead typically required by non-smooth reinforcement learning workarounds.
Decoupled and Derivative-Free Optimization
What happens when we cannot alter the loss function, or when the underlying model architecture itself is strictly non-differentiable? For example, tree-based ensembles (like Gradient Boosting Machines) and pruned, sparse neural networks rely on discrete routing decisions and binary masks that cannot propagate gradients.
In these scenarios, researchers turn to decoupled optimization strategies. Instead of trying to calculate a single unified gradient for both accuracy and fairness, the training process is split into two distinct, alternating steps:
- The Weight Update Step: The model updates its parameters using standard, differentiable loss gradients to maximize raw predictive accuracy.
- The Constraint Adjustment Step: A separate, high-level optimization routine evaluates the model's actual, discrete fairness performance on validation data. It then updates a set of penalty multipliers (Lagrangian multipliers) or adjusts instance-level sampling weights.
This separation allows the system to respect strict, non-differentiable performance bounds without requiring the core model layers to calculate fairness gradients directly.
The authors of Balancing Act: Constraining Disparate Impact in Sparse Models successfully deployed this decoupled approach to enforce fairness in pruned deep learning models, using discrete accuracy measurements to update fairness penalties while keeping weight updates fully differentiable. For tree-based models, André F Cruz et al. designed FairGBM: Gradient Boosting with Fairness Constraints, which pairs a proxy-Lagrangian formulation with smooth cross-entropy surrogates to seamlessly integrate fairness constraints into the discrete training steps of gradient-boosted trees.
When gradients are completely unavailable, derivative-free search algorithms provide a powerful alternative. As Shotaro Akaho et al. demonstrate in Model-based and actual independence for fairness-aware classification, when deterministic decision rules like argmax completely obliterate gradient information, derivative-free optimization can successfully navigate the non-smooth objective space to guarantee true independence in final classification outcomes.
Finally, instead of modifying the model during training, some techniques bypass optimization entirely by computing post-hoc adjustments. Pierre Dognin developed the Fair Infinitesimal Jackknife: Mitigating the Influence of Biased Training Data Points Without Refitting, which uses influence functions and Hessian approximations to estimate how removing specific training points would alter a model's fairness. This allows practitioners to "virtually" debias pre-trained architectures without the massive computational cost of refitting non-differentiable models from scratch.
Key Foundational Work
Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment (2017) — contributed 1 concept elements to this direction.
Linear Transceiver Design for a MIMO Interfering Broadcast Channel Achieving Max-Min Fairness (2012) — contributed 1 concept elements to this direction.