Abstract:Fairness impossibility results often look like distinct scalar incompatibility statements. We show that several share one RKHS geometry: fairness criteria are linear constraints on conditional mean embeddings, and unequal base rates make the law of total expectation overdetermine those constraints.
This view yields four results. The Kleinberg--Mullainathan--Raghavan dichotomy needs only group-conditional unbiasedness, not full calibration. The \emph{Pokémon theorem} shows that a distinct group pair satisfying any finite collection of linear mean-fairness criteria leaves a residual violation witnessed by the MMD, decaying at the Kolmogorov $m$-width rate under spectral regularity. The same tools prove an impossibility for fair feature learning: parity and class-conditional separation in representation space force class collapse under unequal base rates. The approximate relaxations yield signal and error frontiers, allowing a trade-off between real-world estimators and fairness goals. Experiments on standard fairness benchmarks are consistent with our bounds.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| MSC classes: | 68T05 (Primary) 46E22, 47B32, 62H30, 41A46, 62G10 (Secondary) |
| ACM classes: | I.2.6; G.3; K.4.1 |
| Cite as: | arXiv:2605.09221 [cs.LG] |
| (or arXiv:2605.09221v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.09221 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Alexander Smola [view email]
[v1]
Sat, 9 May 2026 23:37:10 UTC (290 KB)