Introduction
Machine learning models often inherit or amplify biases present in historical training data, leading to unfair treatment of protected groups based on attributes like race or gender. Addressing these biases typically occurs at one of three stages: pre-processing (modifying the data), in-processing (modifying the algorithm), or post-processing (modifying the predictions).
Pre-processing is particularly advantageous as it is "downstream agnostic," allowing the use of any off-the-shelf classifier—such as Logistic Regression, SVMs, or Neural Networks—once the data is fixed. However, existing pre-processing techniques often lack theoretical guarantees for the exact level of fairness achieved or struggle to effectively balance the trade-off between fairness and accuracy. FairRR (Fair Randomized Response) bridges this gap by connecting the theory of Fair Bayes-Optimal Classifiers to the domain of data pre-processing.
Methodology
The core innovation of FairRR is the repurposing of Randomized Response (RR), a technique traditionally used in differential privacy to protect sensitive attributes by having respondents occasionally provide false information according to a specific probability. FairRR adapts this mechanism to achieve fairness by strategically "flipping" labels in the training set.
Optimal Label Flipping
Instead of injecting noise to hide information, FairRR uses a controlled noise mechanism to remove statistical bias between groups. It modifies the training labels ($Y$) to a new set of labels ($\tilde{Y}$) to eliminate demographic disparity. For instance, it might randomly flip positive labels to negative in a privileged group to match the base rates of an unprivileged group. The authors derive exact flipping probabilities by formulating group fairness as an optimal design problem that minimizes label noise while satisfying linear fairness constraints.
The Bisection Search
Since the optimal fairness threshold ($t^*_\delta$) is not known a priori, the algorithm employs a bisection search. It iteratively trains a proxy model to find the precise parameters required to achieve a target disparity level ($\delta$). This provides practitioners with a "fairness knob," allowing them to tune the model to specific legal or business requirements precisely.
Experimental Evaluation
The authors evaluated FairRR on three standard fairness benchmarks: Adult Census (income prediction), COMPAS (recidivism prediction), and Law School (admission prediction).
Pareto Frontier Dominance
In experiments comparing various classifiers, FairRR consistently outperformed competing methods such as Fair Sampling, FAWOS, and GAN-based approaches. As shown in the figure below, FairRR consistently occupies the "Pareto Frontier," meaning it provides the highest accuracy for any given level of fairness.
Key Results
FairRR demonstrates significant versatility and effectiveness across multiple fairness criteria, including Demographic Parity, Equality of Opportunity, and Predictive Equality.
- Disparity Reduction: On the Adult dataset, FairRR reduced Demographic Disparity (DDP) from 0.188 in the original data to a near-perfect 0.007, with only a minor drop in accuracy (from 0.841 to 0.820).
- Stability and Efficiency: Despite its randomized nature, the method is highly stable, with low standard deviations across multiple runs. Furthermore, the bisection method typically converges in just a few iterations, making it computationally feasible for standard tabular datasets.
Discussion and Future Work
While FairRR offers a powerful tool for achieving group fairness, several avenues for future research remain. Currently, the framework is designed for binary sensitive attributes and binary outcomes; extending this to intersectional groups is a key next step. Additionally, while RR is a privacy technique, the data-dependent nature of FairRR's flipping probabilities makes a formal privacy analysis technically challenging. Future work could also explore combining label perturbation with feature space modification to further optimize the utility-fairness trade-off.
Summary updated