An Efficient Geometric Characterization of Robust Fair Learning

Previous work has shown that the optimal classifier from a hypothesis class subject to exact fairness constraints may not be *robust*; that is, its accuracy can change drastically under small shifts to the underlying data distribution. We ask the following questions: Given a hypothesis class $\mathcal{H}$, is the accuracy of the optimal fair classifier from $\mathcal{H}$ robust to malicious distribution shifts? And is this property efficiently testable? We consider $\mathcal{H}$ that can be represented by a convex polytope — the natural setting for randomized ensembles of deterministic classifiers, including those produced by boosting. We provide a complete geometric characterization of when $\mathcal{H}$ is robust, and an efficient linear programming test to audit the robustness of a given $\mathcal{H}$. Surprisingly, we demonstrate that if we relax exact fairness constraints and only require approximate fairness, every $\mathcal{H}$ is robust. Our results hold for a broad class of linear fairness criteria (e.g., demographic parity, equal opportunity, predictive equality) and linear loss functions (e.g., 0/1 loss, weighted loss).