Finite-Dimensional Fairness Cannot Certify Distributional Equality
The setup. Kleinberg et al. 2017 (KMR), Chouldechova 2017, Pleiss 2017 showed three distributional fairness criteria collapse when base rates differ across groups. The open question was whether a set of linear criteria would suffice.
Alex Smola@smolixFinite-dimensional fairness is impossible: no finite checklist of linear mean-fairness criteria can certify that two groups are distributionally identical. You Gotta Catch 'Em All, alas the Pokémon theorem says that you can't.
First paper with my son Daniel Matsui Smola. The quantitative version gives a Kolmogorov m-width decay rate, and the minimax-optimal budget allocation is the top-m Mercer eigenspace of the pooled covariance.
Paper: https://arxiv.org/abs/2605.09221 Blog: https://alex.smola.org/posts/35-pokemon-theorem/
Alex Smola@smolixThe argument is one line of RKHS geometry. For any finite list {v_1, …, v_m} of test directions, the MMD witness δ/‖δ‖ lives in the orthogonal complement of the audit subspace. Perfectly visible, completely unaudited, and thus 'unfair'.
The argument is one line of RKHS geometry. For any finite list {v_1, …, v_m} of test directions, the MMD witness δ/‖δ‖ lives in the orthogonal complement of the audit subspace. Perfectly visible, completely unaudited, and thus 'unfair'.
Alex Smola@smolixThe setup. Kleinberg et al. 2017 (KMR), Chouldechova 2017, Pleiss 2017 showed three distributional fairness criteria collapse when base rates differ across groups. The open question was whether a set of linear criteria would suffice.