Optimal Fair Learning Robust to Adversarial Distribution Shift

Previous work in fair machine learning has characterised the Fair Bayes Optimal Classifier (BOC) on a given distribution for both deterministic and randomized classifiers. We study the robustness of the Fair BOC to adversarial noise in the data distribution. Kearns & Li (1988) implies that the accuracy of the deterministic BOC without any fairness constraints is robust (Lipschitz) to malicious noise in the data distribution. We demonstrate that their robustness guarantee breaks down when we add fairness constraints. Hence, we consider the randomized Fair BOC, and our central result is that its accuracy is robust to malicious noise in the data distribution. Our robustness result applies to various fairness constraints---Demographic Parity, Equal Opportunity, Predictive Equality. Beyond robustness, we demonstrate that randomization leads to better accuracy and efficiency. We show that the randomized Fair BOC is nearly-deterministic, and gives randomized predictions on at most one data point, hence availing numerous benefits of randomness, while using very little of it.

If an ML model has good fairness/accuracy metrics when trained in Hospital-A, it may not when tested in Hospital-B. Similarly, a model trained (subject to fairness constraints) in Hospital-A might have very different accuracy if trained in Hospital-B. The phenomenon of distribution shift is common in practice, where the training distribution differs from the testing distribution. We study how fair ML models behave under adversarial/arbitrary distribution shifts.We focus on the Bayes Optimal Classifier (BOC), i.e., the most accurate classifier among all possible classifiers on a given distribution. We consider the Fair-BOC, for both deterministic and randomised classifiers. For various group-fairness notions, we show that the randomised Fair-BOC is robust, i.e., given two similar distributions, the Fair-BOC on each distribution has similar accuracy. In contrast, this robustness guarantee breaks down for deterministic classifiers. Furthermore, we show the randomised Fair-BOC has better accuracy and efficiency than its deterministic counterpart. Our results illustrate various advantages of using randomised classifiers over deterministic ones. However, one must be cautious while introducing randomness in critical decisions. Fortunately, we show that the randomised Fair-BOC is nearly deterministic, being randomised on at most one point in the domain, and deterministic on the rest.