Scalable Fair Learning via Cramér-von Mises Regularization

A standard way to enforce group fairness in machine learning models is to add a fairness regularizer to the training loss. Existing dependence-based regularizers, however, are often computationally expensive, with per-batch costs that are typically quadratic or higher in the batch size $B$. We propose a novel group-fairness regularizer based on the Cramér-von-Mises (CvM) sensitivity index, which penalizes statistical dependence between model predictions and a sensitive attribute during training. Our method combines a rank-based CvM estimator with differentiable soft ranking, yielding a bounded training penalty with $\Oc(B \log B)$ per-batch complexity. This is the first sub-quadratic in-processing fairness method that targets genuine joint-distribution dependence. We further establish theoretical connections between the CvM regularizer and standard fairness metrics such as demographic parity and equality of opportunity. Experiments on tabular and image datasets show competitive fairness-utility trade-offs while substantially lowering training overhead compared to existing dependence-based regularizers.