A Near-Optimal Algorithm for Debiasing Trained Machine Learning Models

Ibrahim M. Alabdulmohsin, Mario Lucic

Introduction

Machine learning models often inherit or amplify societal biases present in their training data, leading to unfair outcomes in critical domains such as credit lending or criminal justice. While "in-processing" methods—which incorporate fairness constraints during training—can be effective, they are often prohibitively expensive for modern deep neural networks. Researchers from Google Research have introduced the Randomized Threshold Optimizer (RTO), a scalable post-processing algorithm that debiases already-trained models. RTO is mathematically proven to be "near-optimal," demonstrating that large-scale models can be debiased effectively without significant loss in accuracy.

The Randomized Threshold Optimizer (RTO)

The core innovation of RTO is treating debiasing as a regularized optimization problem. Unlike traditional methods that use a fixed "hard" threshold for classification, RTO introduces randomization near the decision boundary to achieve optimal fairness-accuracy trade-offs.

The RTO decision rule (a) uses a soft threshold to decide classifications near the boundary, while (b) shows the rapid convergence of the optimization process.

Key technical features include:

  • Randomization at the Threshold: To achieve the best possible accuracy for a given fairness level (Bayes risk consistency), the model outputs a probability—effectively "flipping a weighted coin"—for instances near the decision boundary.
  • Lagrange Duality: By using Lagrange multipliers, the authors transform fairness constraints into a dual optimization problem. This allows for fast, scalable solutions using projected Stochastic Gradient Descent (SGD).
  • Statistical Parity: The method primarily targets Statistical Parity, ensuring that average predicted outcomes are consistent across different sensitive groups.

Experimental Evaluation

The algorithm was evaluated across diverse datasets, including classic tabular data and modern computer vision benchmarks:

  • Adult Income & DCCC: Predicting income levels and credit defaults.
  • CelebA & COCO: Large-scale image datasets used to measure sex-based bias in attribute prediction and object detection.
  • Scaling Benchmarks: Models pre-trained on ImageNet-21k and JFT-300M were used to test how debiasing scales with model size.

Key Results

RTO consistently outperforms existing post-processing methods like the Reject Option Classifier (ROC) in the accuracy-vs-fairness tradeoff. It successfully reduces bias (statistical parity difference) to near-zero levels across various classifiers.

RTO achieves significant bias reduction across multiple datasets and model architectures, often reaching levels as low as 0.01.

Beyond its performance on standard benchmarks, the research revealed two critical insights:

  1. Scaling is a Friend to Fairness: Larger, overparameterized models trained on massive datasets are actually easier to debias via post-processing than smaller models, as they retain more accuracy after the transformation.
  2. Closing the Gap: RTO performs on par with more computationally intensive in-processing methods, challenging the notion that retraining is necessary for fairness.

Limitations and Future Work

While RTO is highly effective for Statistical Parity, its application to other metrics like Equalized Odds requires further theoretical extension. Additionally, the method requires access to sensitive attributes during the calibration phase, which may be restricted in certain legal or privacy-sensitive contexts. Finally, RTO assumes the base model provides continuous scores; it cannot be directly applied to models that only output hard labels.

Summary updated

Abstract

We present a scalable post-processing algorithm for debiasing trained models, including deep neural networks (DNNs), which we prove to be near-optimal by bounding its excess Bayes risk. We empirically validate its advantages on standard benchmark datasets across both classical algorithms as well as modern DNN architectures and demonstrate that it outperforms previous post-processing methods while performing on par with in-processing. In addition, we show that the proposed algorithm is particularly effective for models trained at scale where post-processing is a natural and practical choice.
BibTeX
@inproceedings{alabdulmohsin2021near,
  author = {Ibrahim M. Alabdulmohsin and Mario Lucic},
  title = {{A Near-Optimal Algorithm for Debiasing Trained Machine Learning Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=H5TBqNFPKSJ},
}
Figure