Too Relaxed to Be Fair

Michael Lohaus, Michaël Perrot, Ulrike von Luxburg

This paper challenges a common practice in fair machine learning: the use of "relaxed" constraints. While these relaxations make optimization easier, the authors demonstrate that they often fail to deliver actual fairness. They propose a new framework, SearchFair, which uses a principled convex approach to find classifiers that are provably fair.

TL;DR

Many fair machine learning algorithms use "relaxed" versions of fairness constraints to make optimization mathematically tractable, but these relaxations are often too loose to guarantee real-world fairness. This paper introduces SearchFair, a framework that leverages the continuous relationship between accuracy and fairness to find provably fair classifiers using a simple binary search over a trade-off parameter.

The Problem with Relaxed Fairness

In fair classification, the goal is to build models that don't discriminate against specific groups (e.g., based on race or gender). Mathematically, this is usually framed as a constrained optimization problem: "Maximize accuracy subject to a fairness constraint."

However, standard fairness metrics—like Demographic Parity (ensuring the positive prediction rate is the same for all groups)—are "discrete" and non-convex, making them a nightmare to optimize directly. To get around this, researchers use "relaxations" (smooth approximations).

Comparison of decision boundaries showing how relaxed constraints can fail to achieve true fairness.

The authors identify a major gap: these relaxations are often too relaxed. A model can perfectly satisfy the relaxed constraint while remaining significantly unfair according to the true metric. They show that for complex models, these relaxations often have almost no influence on the final outcome, leading to a false sense of security regarding a model's bias.

The SearchFair Method

The authors propose a shift in strategy. Instead of trying to solve a single, difficult constrained problem, they solve a sequence of easier, unconstrained problems.

  1. Convex Trade-off: They formulate an objective function that balances accuracy and a signed convex approximation of the fairness constraint, weighted by a parameter $\lambda$.
  2. The Continuity Theorem: The core theoretical contribution is proving that the true fairness of the resulting classifier is a continuous function of $\lambda$.
  3. SearchFair Algorithm: Because the relationship is continuous, if $\lambda=0$ favors group A and $\lambda=1$ favors group B, there must be a value in between where the model is perfectly fair. The algorithm uses a simple binary search to find this optimal $\lambda_0$.
  4. Similarity-Based Classifiers: To ensure that a solution exists that is both fair and accurate, they utilize a framework of similarity-based classifiers, providing theoretical bounds on the existence of such separators.

Datasets Evaluated

The researchers evaluated their approach on six standard fairness benchmarks:

  • Adult: Predicting income levels.
  • Dutch: Predicting occupation levels.
  • CelebA: Predicting facial attributes (e.g., "attractive" vs. "not attractive" with gender as the sensitive attribute).
  • COMPAS: Predicting recidivism (risk of re-offending).
  • Communities and Crime: Predicting crime rates in neighborhoods.
  • German Credit: Predicting credit risk.

Key Insights and Ideas

Contour plots of true fairness (DDP) versus various relaxations, illustrating how some relaxations are blind to changes in the intercept.
  • Relaxations are "Blind" to Intercepts: The authors show that linear relaxations (common in the literature) are often oblivious to the model's intercept parameter. You can shift a decision boundary to be more or less fair, and the relaxation won't even notice.
  • Complexity vs. Fairness: For high-capacity models (like those using RBF kernels), linear relaxations often fail completely. The model is flexible enough to "cheat" the relaxation by changing the labels of just a few points, satisfying the math without fixing the underlying bias.
  • The Power of Signed Constraints: By using a signed version of the fairness penalty (rather than an absolute value), the authors create a "knob" ($\lambda$) that allows them to dial the bias from one group to the other, ensuring they can find the "neutral" middle ground.

Key Results

  • Reliable Fairness: SearchFair consistently achieved near-zero fairness scores (DDP and DEO) across all datasets, whereas previous "relaxed" methods often failed to improve fairness when using complex kernels.
  • Competitive with Non-Convex Methods: SearchFair performed as well as or better than state-of-the-art non-convex approaches but with the benefit of a more stable, convex optimization foundation.
  • Accuracy Trade-off: The results confirm that achieving perfect fairness sometimes requires a slight drop in accuracy, particularly when the underlying dataset is heavily biased. In some cases, the fairest model is close to a "constant classifier" (predicting the same for everyone), highlighting the inherent difficulty of the task.

Limitations and Future Work

  • Computational Overhead: Because SearchFair uses a binary search, it requires training the model multiple times (typically 10 iterations). While manageable for many tasks, this could be expensive for massive deep learning models.
  • Hyperparameter Sensitivity: While $\lambda$ is found automatically, other hyperparameters (like the regularization strength $\beta$ or kernel widths) still need to be tuned via cross-validation.
  • Beyond Binary: The current framework focuses on binary sensitive attributes (e.g., Group A vs. Group B). Extending this to multiple groups or continuous sensitive attributes remains a direction for future research.

Summary updated

Abstract

We address the problem of classification under fairness constraints. Given a notion of fairness, the goal is to learn a classifier that is not discriminatory against a group of individuals. In the ...
BibTeX
@inproceedings{lohaus2020too,
  author = {Michael Lohaus and Michaël Perrot and Ulrike von Luxburg},
  title = {{Too Relaxed to Be Fair}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=RfryHKJe_aq},
}
Figure