Scalable Fair Learning via Cramér-von Mises Regularization
A Cramér-von Mises fairness regularizer with O(B log B) complexity penalizes prediction-sensitive attribute dependence during training, achieving competitive fairness-utility trade-offs with lower overhead.
Published 2026Sydney Poster Session 1 · Tue, Dec 8, 10:00 AM–1:00 PM local time · Hall 1-4OpenReview ↗
Only vote on papers you've read. Sign in with GitHub to vote.
A scalable O(B log B) CvM fairness regularizer delivers rare sub-quadratic in-processing dependence penalties with strong fairness-utility results, though it never defines "genuine joint-distribution dependence," omits code and latency benchmarks, and leaves its theoretical parity links…
Abstract
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.