Bridging Adversarial and Information-Theoretic Fairness via Robustness

This work investigates the tension between information-theoretic and adversarial approaches to fairness in neural network classifiers. Specifically, we examine the Equalized Odds (EO) objective, which requires the classifier output $Z$ to be independent of sensitive attributes $U$ given the true label $Y$. While Mutual Information (MI) provides an absolute measure of independence, adversarial (discriminator-based) approaches offer a computationally bounded alternative. We first bridge these paradigms by proving the existence of an ``optimal'' discriminator whose complexity is both necessary and sufficient to achieve a Difference in Equalized Odds (DEO) of zero. However, we demonstrate that this adversarial fairness is highly fragile under distributional shifts. In contrast, we show that the MI-based approach is ``over-robust''; we prove that if $I(Z;U|Y)=0$ on a source distribution, zero DEO is preserved for any target distribution sharing the same support. While this provides a powerful invariance guarantee, it addresses shifts far more radical than those typically encountered in practice. Finally, via experiments on benchmark fairness datasets, we show that the practical optimal discriminator complexity is often higher than theoretically predicted, gravitating toward MI-based solutions. Our results imply that treating discriminator complexity as a tunable hyperparameter can significantly optimize the fairness-accuracy curve, capturing the necessary robustness without the practical overhead of MI-based extremes.