Fairness-Aware PAC Learning from Corrupted Data

Nikola Konstantinov, Christoph H. Lampert

Abstract

In the field of fairness-aware machine learning, it is often assumed that training data, while potentially biased, is sampled honestly from an underlying distribution. However, real-world data is frequently subject to corruption, whether through historical bias, collection errors, or deliberate adversarial manipulation. This paper, originally published in JMLR 2022 by Nikola Konstantinov and Christoph H. Lampert, investigates the fundamental information-theoretic limits of learning fair models in the presence of a malicious adversary. By establishing tight lower and upper bounds, the authors demonstrate that even minor data corruption can impose significant fairness violations, particularly for underrepresented minority groups.

Introduction

As machine learning models are increasingly deployed in high-stakes domains such as hiring, lending, and criminal justice, ensuring their fairness has become a primary concern. Most existing fairness interventions focus on mitigating bias inherent in the data distribution itself. This research shifts the focus to a more adversarial setting: what happens when a small fraction of the training data is maliciously corrupted?

Using the framework of Probably Approximately Correct (PAC) learning, the authors explore the limits of two critical fairness metrics: Demographic Parity (independence of predictions from protected attributes) and Equal Opportunity (equality of true positive rates across groups). The central question is whether a learner can remain fair when an adversary can manipulate a fraction $\alpha$ of the training set.

The Malicious Adversary Model

The study adopts Valiant’s classic malicious adversary model. In this setup, the adversary possesses full knowledge of the true data distribution and the learning algorithm. They are permitted to replace a fraction $\alpha$ of the training samples with arbitrary, potentially misleading data points. This represents a "worst-case" scenario, providing a rigorous test for the robustness of fairness-aware algorithms.

To prove the impossibility of achieving perfect fairness under these conditions, the authors utilize the Method of Induced Distributions. They construct pairs of distributions that appear identical to a learner after adversarial poisoning but require fundamentally different classifiers to satisfy fairness constraints. This creates a scenario where any learning algorithm is guaranteed to fail on at least one of the distributions, establishing a fundamental lower bound on achievable fairness.

Fundamental Limits: The "Minority Tax"

The most significant theoretical contribution of the paper is the characterization of the relationship between data corruption, group size, and fairness. The authors prove that for any learner, the excess bias is at least $\Omega(\alpha / P_0)$, where $P_0$ represents the proportion of the minority group in the population.

This finding reveals a "Minority Tax" on robustness: the smaller the protected group, the more vulnerable the model is to forced unfairness. If a minority group constitutes only 1% of the data, an adversary needs very little leverage to significantly bias the model against them. Crucially, this bias cannot be eliminated by simply increasing the sample size; the $\alpha$ corruption leaves a permanent, irreducible impact on the model's fairness profile.

Stealthy Unfairness and Accuracy

A chilling insight from the mathematical analysis is the existence of "stealthy unfairness." The authors demonstrate that an adversary can often successfully destroy a model's fairness without significantly degrading its predictive accuracy. In a production environment, a model might pass all standard performance benchmarks and validation checks while secretly harboring discriminatory biases introduced during the training phase. This highlights the necessity of dedicated fairness auditing that goes beyond simple accuracy metrics.

Robust Algorithmic Approaches

While the paper establishes harsh lower bounds, it also proposes and analyzes two algorithmic strategies designed to be as robust as possible:

  1. Weighted Objective: This approach minimizes a combined loss function of the form Error + λ * Unfairness. By tuning the hyperparameter $\lambda$, the learner can navigate the trade-off between performance and bias.
  2. Component-wise Learner: This method seeks a hypothesis within the intersection of a "low-error" set and a "low-bias" set, ensuring that the chosen model satisfies both criteria simultaneously.

The authors show that these algorithms achieve an upper bound on bias of $O(\alpha / P_0)$. Because this matches the lower bound in terms of its dependence on $\alpha$ and $P_0$, these algorithms are considered order-optimal. They represent the theoretical limit of what can be achieved under adversarial conditions.

Conclusion and Future Directions

This research provides a rigorous foundation for understanding the limits of fair machine learning in adversarial environments. It proves that underrepresented groups bear the brunt of data corruption and that fairness is often more fragile than accuracy.

However, the study also points toward potential solutions. The authors suggest that the presence of a small "gold standard" dataset—a subset of data guaranteed to be clean and uncorrupted—could potentially bypass these impossibility results. Future work may also relax the "God-like" adversary assumption, exploring how models perform against random noise or specific, non-omniscient corruption patterns. For now, the paper serves as a vital reminder that in the quest for algorithmic fairness, data integrity is just as important as the algorithm itself.

Summary updated

Abstract

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.
BibTeX
@article{konstantinov2022fairness,
  author = {Nikola Konstantinov and Christoph H. Lampert},
  title = {{Fairness-Aware PAC Learning from Corrupted Data}},
  journal = {J. Mach. Learn. Res.},
  year = {2022},
  url = {https://openreview.net/forum?id=ES7lBzyXII},
}
Figure