Search for: All records

We consider the vulnerability of fairness-constrained learning to malicious noise in the training data. Konstantinov and Lampert (2021) initiated the study of this question and proved that any proper learner can exhibit high vulnerability when group sizes are imbalanced. Here, we present a more optimistic view, showing that if we allow randomized classifiers, then the landscape is much more nuanced. For example, for Demographic Parity we need only incur a Θ(α) loss in accuracy, where α is the malicious noise rate, matching the best possible even without fairness constraints. For Equal Opportunity, we show we can incur an O(sqrt(α)) loss, and give a matching Ω(sqrt(α)) lower bound. For Equalized Odds and Predictive Parity, however, and adversary can indeed force an Ω(1) loss. The key technical novelty of our work is how randomization can bypass simple 'tricks' an adversary can use to amplify its power. These results provide a more fine-grained view of the sensitivity of fairness-constrained learning to adversarial noise in training data. 

A fundamental problem in robust learning is asymmetry: a learner needs to correctly classify every one of exponentially-many perturbations that an adversary might make to a test example, but the attacker only needs to find one successful perturbation. Xiang et al. [2022] proposed an algorithm for patch attacks that reduces the effective number of perturbations from an exponential to a polynomial, and learns using an ERM oracle. However, their guarantee requires the natural examples to be robustly realizable. In this work we consider the non-robustly-realizable case. Our first contribution is to give a guarantee for this setting by utilizing an approach of Feige, Mansour, and Schapire [2015]. Next, we extend our results to a multi-group setting and introduce a novel agnostic multi-robust learning problem where the goal is to learn a predictor that achieves low robust loss on a (potentially) rich collection of subgroups.