On the Impossibility of Fairness-Aware Learning from Corrupted Data

Nikola Konstantinov, Christoph H. Lampert

Abstract

As machine learning (ML) models are increasingly deployed in high-stakes environments such as hiring, lending, and law enforcement, the demand for "fairness-aware" algorithms has grown. These algorithms are often designed under the assumption that they can filter out historical biases or noise to recover a fair model. This paper challenges that assumption by establishing fundamental information-theoretic limits on fairness-aware learning. Using the Malicious Adversary Model, we prove that if even a small fraction of training data is corrupted by a strategic adversary, it becomes mathematically impossible for any algorithm to guarantee fair outcomes. Our findings highlight a critical vulnerability: adversaries can force models to be discriminatory—often without impacting overall accuracy—with the most severe consequences falling on underrepresented minority groups.

Introduction

The prevailing paradigm in fair machine learning assumes that while training data may be imperfect, algorithmic interventions—whether applied during pre-processing, in-processing, or post-processing—can successfully mitigate bias. However, real-world data is frequently subject to corruption, ranging from systemic historical bias to intentional "poisoning" attacks.

This research investigates a pivotal question: Can we certify the fairness of a model when a portion of the training data has been manipulated by an adversary with full knowledge of the learning process? By exploring the boundaries of Probably Approximately Correct (PAC) learning for binary classification, this paper identifies the "breaking point" where fairness guarantees become impossible to maintain.

Theoretical Framework: The Malicious Adversary Model

To analyze the limits of fairness, the authors employ the Malicious Adversary Model (Valiant, 1985). In this rigorous theoretical setup:

  1. A "clean" dataset is sampled from a true underlying distribution.
  2. An adversary replaces a fraction ($\alpha$) of these points with arbitrary, strategically chosen data.
  3. The adversary possesses "god-like" knowledge, including the true distribution, the specific learning algorithm in use, and the remaining clean data.

The study focuses on two primary mathematical definitions of fairness:

  • Demographic Parity: Ensuring the model’s predictions are independent of protected attributes (e.g., race or gender).
  • Equal Opportunity: Ensuring the model maintains consistent true positive rates across different groups.

The Mechanics of Impossibility

The core of the impossibility proof lies in the "method of induced distributions." The authors demonstrate that an adversary can construct scenarios where two distinct data distributions—which would require entirely different classifiers to achieve fairness—appear identical to a learner after corruption. Because the learner cannot distinguish between these two underlying realities, it cannot consistently choose a classifier that satisfies fairness constraints for the true distribution.

This result is algorithm-agnostic. It does not merely critique specific existing tools; it proves that no possible algorithm can overcome this information-theoretic barrier once the data has been sufficiently poisoned.

Key Insights

The "Minority Tax"

A significant finding of this research is that the difficulty of achieving fairness is inversely proportional to the size of the minority group. The authors prove that the fairness deviation (the degree of unfairness) is bounded by $\Omega(\alpha / P_0)$, where $\alpha$ is the corruption rate and $P_0$ is the frequency of the minority group. Consequently, if a protected group is small, even a negligible amount of data corruption can lead to massive, unavoidable unfairness.

Stealthy Bias Injection

One of the most dangerous aspects of adversarial corruption is that it does not require a trade-off with accuracy. An adversary can inject "sneaky" bias where the model remains highly accurate on the corrupted dataset but becomes significantly discriminatory. This poses a major risk for developers who use accuracy as a primary proxy for model health, as significant bias may remain undetected by standard performance metrics.

The Pareto Front Barrier

Even in scenarios with infinite training data, the presence of corruption prevents a learner from reaching the optimal trade-off between accuracy and fairness, known as the Pareto front. The adversary can effectively force any learner to return a classifier that appears optimal in terms of accuracy but exhibits a level of unfairness that renders fairness constraints useless.

Conclusion and Future Directions

This research serves as a sobering reminder that fairness cannot be solved through algorithmic adjustments alone if the underlying data integrity is compromised. The results suggest that the "worst-case" scenario for fairness is highly sensitive to even minor data manipulations, particularly for underrepresented populations.

Moving forward, the authors suggest two primary strategies to combat these limitations:

  1. Prioritizing Data Integrity: Since fairness cannot be mathematically "fixed" after poisoning, resources must be shifted toward securing the data collection pipeline itself.
  2. Utilizing Trusted Subsets: The impossibility results can be broken if the learner has access to even a very small "certified clean" subset of data. Future research should focus on how to leverage these small, high-quality anchors to stabilize the fairness of models trained on larger, potentially corrupted datasets.

Summary updated

Abstract

Addressing fairness concerns about machine learning models is a crucial step towards their long-term adoption in real-world automated systems. Many approaches for training fair models from data have been developed and an implicit assumption about such algorithms is that they are able to recover a fair model, despite potential historical biases in the data. In this work we show a number of impossibility results that indicate that there is no learning algorithm that can recover a fair model when a proportion of the dataset is subject to arbitrary manipulations. Specifically, we prove that there are situations in which an adversary can force any learner to return a biased classifier, with or without degrading accuracy, and that the strength of this bias increases for learning problems with underrepresented protected groups in the data. Our results emphasize on the importance of studying further data corruption models of various strength and of establishing stricter data collection practices for fairness-aware learning.
BibTeX
@inproceedings{konstantinov2021impossibility,
  author = {Nikola Konstantinov and Christoph H. Lampert},
  title = {{On the Impossibility of Fairness-Aware Learning from Corrupted Data}},
  booktitle = {AFCR},
  year = {2021},
  url = {https://openreview.net/forum?id=LVLNVYAkQQL},
}
Figure