# Fairness-Aware PAC Learning from Corrupted Data arXiv: https://arxiv.org/abs/2102.06004 ยท HTML: https://mlsanity.com/paper/2102.06004/ ## Key facts - Cited by 18 papers in the map (data through 14 Oct 2026). - Builds on 34 of its 54 references that are in the map. - First posted on arXiv 11 Feb 2021. ## Builds on (most cited first, 30 of 34) - [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016) - [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019) - [Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning](https://mlsanity.com/paper/1712.05526/) (2017) - [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018) - [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016) - [Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning](https://mlsanity.com/paper/1712.03141/) (2017) - [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018) - [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017) - [Fairness without Demographics through Adversarially Reweighted Learning](https://mlsanity.com/paper/2006.13114/) (2020) - [Using Trusted Data to Train Deep Networks on Labels Corrupted by Severe Noise](https://mlsanity.com/paper/1802.05300/) (2018) - [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016) - [Identifying and Correcting Label Bias in Machine Learning](https://mlsanity.com/paper/1901.04966/) (2019) - [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018) - [Tilted Empirical Risk Minimization](https://mlsanity.com/paper/2007.01162/) (2020) - [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016) - [Fairness risk measures](https://mlsanity.com/paper/1901.08665/) (2019) - [Assessing Algorithmic Fairness with Unobserved Protected Class Using Data Combination](https://mlsanity.com/paper/1906.00285/) (2019) - [Robust Optimization for Fairness with Noisy Protected Groups](https://mlsanity.com/paper/2002.09343/) (2020) - [Fair Classification with Group-Dependent Label Noise](https://mlsanity.com/paper/2011.00379/) (2020) - [Poisoning Attacks on Algorithmic Fairness](https://mlsanity.com/paper/2004.07401/) (2020) - [FR-Train: A Mutual Information-Based Approach to Fair and Robust Training](https://mlsanity.com/paper/2002.10234/) (2020) - [Recovering from Biased Data: Can Fairness Constraints Improve Accuracy?](https://mlsanity.com/paper/1912.01094/) (2019) - [Residual Unfairness in Fair Machine Learning from Prejudiced Data](https://mlsanity.com/paper/1806.02887/) (2018) - [Equalized odds postprocessing under imperfect group information](https://mlsanity.com/paper/1906.03284/) (2019) - [Exacerbating Algorithmic Bias through Fairness Attacks](https://mlsanity.com/paper/2012.08723/) (2020) - [Fair Learning with Private Demographic Data](https://mlsanity.com/paper/2002.11651/) (2020) - [A Distributionally Robust Approach to Fair Classification](https://mlsanity.com/paper/2007.09530/) (2020) - [Noise-tolerant fair classification](https://mlsanity.com/paper/1901.10837/) (2019) - [Fairness Evaluation in Presence of Biased Noisy Labels](https://mlsanity.com/paper/2003.13808/) (2020) - [On Adversarial Bias and the Robustness of Fair Machine Learning](https://mlsanity.com/paper/2006.08669/) (2020) ## Built on by (most cited first, 18 of 18) - [Towards Adversarial Evaluations for Inexact Machine Unlearning](https://mlsanity.com/paper/2201.06640/) (2022) - [Corrective Machine Unlearning](https://mlsanity.com/paper/2402.14015/) (2024) - [Monitoring Algorithmic Fairness](https://mlsanity.com/paper/2305.15979/) (2023) - [The Fragility of Fairness: Causal Sensitivity Analysis for Fair Machine Learning](https://mlsanity.com/paper/2410.09600/) (2024) - [Monitoring Algorithmic Fairness under Partial Observations](https://mlsanity.com/paper/2308.00341/) (2023) - [Quantifying and mitigating the impact of label errors on model disparity metrics](https://mlsanity.com/paper/2310.02533/) (2023) - [Breaking Fair Binary Classification with Optimal Flipping Attacks](https://mlsanity.com/paper/2204.05472/) (2022) - [Generalization In Multi-Objective Machine Learning](https://mlsanity.com/paper/2208.13499/) (2022) - [Mitigating Source Bias for Fairer Weak Supervision](https://mlsanity.com/paper/2303.17713/) (2023) - [A Survey on Preserving Fairness Guarantees in Changing Environments](https://mlsanity.com/paper/2211.07530/) (2022) - [A Cognac Shot To Forget Bad Memories: Corrective Unlearning for Graph Neural Networks](https://mlsanity.com/paper/2412.00789/) (2024) - [Navigating Towards Fairness with Data Selection](https://mlsanity.com/paper/2412.11072/) (2024) - [Measuring Equality in Machine Learning Security Defenses: A Case Study in Speech Recognition](https://mlsanity.com/paper/2302.08973/) (2023) - [Identifying Early Help Referrals For Local Authorities With Machine Learning And Bias Analysis](https://mlsanity.com/paper/2307.06871/) (2023) - [Utility of Multimodal Large Language Models in Analyzing Chest X-ray with Incomplete Contextual Information](https://mlsanity.com/paper/2410.07111/) (2024) - [A Critical Review of Predominant Bias in Neural Networks](https://mlsanity.com/paper/2502.11031/) (2025) - [Monitoring of Static Fairness](https://mlsanity.com/paper/2507.03048/) (2025) - [Algorithmic Fairness: A Runtime Perspective](https://mlsanity.com/paper/2507.20711/) (2025) ## Abstract (arXiv) Addressing fairness concerns about machine learning models is a crucial step towards their long-term adoption in real-world automated systems. While many approaches have been developed for training fair models from data, little is known about the robustness of these methods to data corruption. In this work we consider fairness-aware learning under worst-case data manipulations. We show that an adversary can in some situations force any learner to return an overly biased classifier, regardless of the sample size and with or without degrading accuracy, and that the strength of the excess bias increases for learning problems with underrepresented protected groups in the data. We also prove that our hardness results are tight up to constant factors. To this end, we study two natural learning algorithms that optimize for both accuracy and fairness and show that these algorithms enjoy guarantees that are order-optimal in terms of the corruption ratio and the protected groups frequencies in the large data limit.