Data Bias Mitigation under Coverage Constraints & The Price of Fairness

Machine learning models often exhibit discriminatory outcomes for intersectional subgroups—such as individuals defined by the intersection of race and gender—due to insufficient representation in training data. While existing bias mitigation techniques attempt to balance datasets, they often do so without considering the minimum sample sizes required for models to learn effectively. This paper addresses the challenge of mitigating bias while simultaneously enforcing 'coverage constraints' to ensure that every demographic group remains large enough to support reliable downstream predictive performance.

The authors extend a previous bias mitigation framework to incorporate explicit coverage constraints. They formulate the problem as an integer linear program (ILP) that allows practitioners to minimize the cost of data modifications (additions or deletions) while adhering to specific fairness tolerances. Unlike previous methods that might naively remove data to achieve balance, this approach optimizes the entire dataset transformation process. The authors also provide theoretical bounds for approximation errors and develop a sampling scheme to handle scenarios where the distribution of external data sources is unknown.

The study demonstrates that bias mitigation without coverage constraints can lead to 'pathological' dataset reduction, where the model loses predictive accuracy because it lacks sufficient data for specific groups. By incorporating coverage constraints, the authors show that it is possible to achieve fairness goals without sacrificing model performance. Furthermore, the ILP formulation allows for a precise calculation of the 'price of fairness'—the minimum cost required to reach a specific fairness threshold—enabling data governance teams to make informed trade-offs between data purchasing costs and regulatory compliance.