Data Bias Mitigation under Coverage Constraints & The Price of Fairness

Source: arXiv:2606.20461 · Published 2026-06-18 · By Bruno Scarone, Alfredo Viola, Renée J. Miller

TL;DR

This work addresses the intertwined problems of algorithmic bias and insufficient subgroup representation in machine learning datasets, specifically focusing on intersectional groups defined by multiple sensitive attributes. The authors extend a prior data-level bias mitigation framework by introducing coverage constraints that guarantee minimum sample sizes for each demographic group-label pair, including intersectional subgroups. This is crucial to ensure that bias mitigation does not degrade downstream model performance by creating sparse or skewed datasets. To balance fairness with data efficiency, they allow small approximation errors in bias but minimize data modifications (additions and deletions). They formulate the bias mitigation problem as an integer linear program (ILP) that optimizes over all possible mitigation strategies to find a globally optimal solution that satisfies fairness and coverage requirements. They characterize the “price of fairness” as the minimal data modification cost required to reach various bias tolerance levels.

Empirical evaluation on well-known fairness benchmark datasets (Adult, COMPAS, Default) demonstrates that incorporating coverage constraints significantly preserves or improves predictive accuracy across classifiers, compared to naive bias mitigation that ignores coverage. Requiring sufficient data representation avoids pathological cases where bias correction shrinks crucial subgroups too much. The ILP-based approach efficiently explores the combinatorial space of dataset modifications (additions/deletions) to meet both fairness and coverage goals while quantifying cost tradeoffs. The paper also provides theoretical error bounds on approximate solutions and statistical sample-complexity guarantees for estimating external data distributions used for mitigation. This comprehensive framework advances practical, data-centric fairness interventions that explicitly acknowledge the interdependence of bias, coverage, and data acquisition cost.

Key findings

• In the Adult dataset, permitting 1,059 deletions alongside additions reduces required new data from 4,201 to 1,599 tuples, a 62% reduction in data modification cost.
• Coverage constraints prevent bias mitigation from excessively shrinking groups and thereby preserve downstream model accuracy across classifiers like AdaBoost, Random Forests, Gradient Boosting, logistic regression, and Extra Trees (Fig. 1).
• Exact zero-bias solutions often require prohibitively large data additions (e.g., 182,394 tuples for COMPAS), motivating approximate solutions with small bias errors but significantly fewer data modifications.
• Approximate mitigation solutions satisfy maximal frequency error bounds of approximately 1/(minimum coverage), which translates into small induced bias errors.
• Formulating bias mitigation as an ILP that optimizes over all mitigation strategies (additions and deletions with different costs) finds globally optimal solutions for any desired fairness tolerance.
• The sample complexity for estimating external source data distributions for mitigation depends logarithmically on the number of group-label pairs and is independent of dataset size, facilitating efficient estimation.
• Employing coverage constraints alongside fairness constraints leads to datasets that maintain both low bias and high ML predictive performance, contrary to assumptions about fairness-accuracy tradeoffs.
• The framework naturally accommodates non-binary sensitive attributes and multi-class label spaces which are underexplored in prior bias mitigation literature.

Threat model

The work does not define a traditional adversarial threat model. Instead, it assumes biased training data arising from sampling and representation bias in sensitive intersectional subgroups. The goal is to mitigate statistical bias and ensure sufficient coverage per group without adversarial manipulation. The framework presumes access to group-label counts and some external data source(s) for possible augmentation but no malicious interference or data poisoning. The adversary is effectively the distributional biases in data, not an active attacker.

Methodology — deep read

The paper begins by defining a classical fairness setting with datasets containing non-binary labels and multiple sensitive attributes S = ⟨S1,...,Sk⟩. Groups s correspond to k-tuples over sensitive attribute values or wildcards (∗) defining intersectional and aggregate groups, and bias is measured via the Uniform Bias (UB) metric: bs,y = 1 - fs,y / fy, comparing group-label proportions to global label proportions.

The key challenge is to mitigate bias while satisfying coverage constraints ms,y, i.e., ensuring that the number of tuples per group-label pair remains above a threshold to guarantee meaningful representation. They assume bias mitigation via data modifications restricted to additions and deletions of tuples (no label changes).

1. Threat Model & Assumptions: The adversary is not explicitly modeled; instead focus is on data bias in classification settings and the effect of changing dataset composition on fairness and accuracy. They assume knowledge of group-label counts but consider unknown external data distributions.

2. Data: They use three benchmark datasets—Adult (~48K rows with binary sensitive attributes sex and race, 2 labels), COMPAS (~60K rows, multi-class 3 labels with sex and race), Default (~30K rows, sex and education as sensitive attributes). These datasets enable assessment across varying levels of bias, label types, and group complexity.

3. Algorithmic Framework: Bias mitigation operates on group-label counts [s,y], adjusting counts by Δ[s,y] denoting additions (Δ>0) or deletions (Δ<0). They generalize prior equations for bias mitigation to incorporate coverage constraints, expressed as linear inequalities on Δ:

   • Fairness goal: achieve zero or bounded bias by solving Δ[s,y] = -[s,y] + (y / yi)*([s,yi] + Δ[s,yi]) for each (s,y), where yi is a reference label per group defining a mitigation strategy.
   • Coverage constraints: [s,y] + Δ[s,y] ≥ ms,y.

They characterize exact solutions requiring integral Δ and minimal total changes k, but these may be large data modifications.

4. ILP Formulation: They formulate bias mitigation as an integer linear program optimizing over all mitigation strategies (reference labels yi per group) with addition and deletion variables and costs. Objectives minimize total data changes while satisfying fairness and coverage constraints. This ILP can find globally optimal solutions including mixtures of additions and deletions.

5. Approximate Solutions: Allowing rounding of Δ yields approximate solutions with small frequency and bias errors. They provide theoretical bounds on error based on group sizes and number of labels, showing errors decrease inversely with coverage.

6. External Distribution Estimation: For settings where external data source distributions are unknown, they apply Serfling's inequality (sampling without replacement) to derive sample complexity bounds ensuring reliable estimation of group-label proportions, used for parameterizing mitigation.

7. Evaluation Protocol: They evaluate on benchmark datasets by applying their ILP mitigation method, assessing (i) bias levels via Uniform Bias metrics, (ii) coverage satisfaction, (iii) downstream ML model accuracy across five classifiers, and (iv) data cost in terms of additions/deletions. They compare exact vs approximate mitigations and baseline approaches ignoring coverage. Ablations test effects of coverage thresholds and bias tolerance parameters.

8. Reproducibility: The paper references appendix materials with full solutions, proofs, and datasets standard in fairness research. Code and exact seeds are not explicitly mentioned; datasets are publicly available.

A concrete example in the Adult dataset context shows that strategic deletions combined with additions reduce required data increases by over 60%, preserving representation for intersectional groups such as Black women whose data is underrepresented but critical to fairness.

Overall, this methodology integrates mathematical fairness constraints, sample size thresholds (coverage), and cost metrics in a principled optimization framework that balances fairness, representativeness, and efficiency.

Technical innovations

• Integration of explicit coverage constraints (minimum group-label counts) into data-level bias mitigation to preserve intersectional subgroup representation.
• Formulation of bias mitigation as a global integer linear program that optimizes simultaneously over all mitigation strategies (reference labels) and both additions and deletions with assigned costs.
• Derivation of theoretical bounds on the frequency and bias errors induced by approximate (rounded) mitigation solutions under coverage constraints.
• Application of Serfling’s inequality to establish sample complexity guarantees for estimating unknown external data distributions to parameterize mitigation.

Datasets

• COMPAS — 60,798 samples — publicly available ProPublica dataset on recidivism
• Adult — 48,842 samples — publicly available 1994 US Census dataset for income prediction
• Default — 30,000 samples — publicly available Taiwan credit card default dataset

Baselines vs proposed

• No mitigation (baseline) on Adult dataset: predictive accuracy ~0.80 (varies by classifier) with high bias vs mitigation with coverage constraints: bias reduced to near zero and accuracy preserved or slightly improved (Fig. 1b)
• Additions-only mitigation: requires 4,201 tuples additions vs additions+deletions mitigation: 1,599 tuples modifications (62% reduction)
• Exact zero-bias solution for COMPAS requires 182,394 tuple modifications vs approximate solutions allow small bias (error < 0.001) with far fewer data changes
• Mitigation without coverage constraints degrades downstream ML accuracy significantly vs mitigation with coverage maintains accuracy across AdaBoost, Random Forest, Gradient Boosting, Logistic Regression, Extra Trees

Limitations

• Evaluation focuses on three standard datasets; real-world data may present more complex distributions and rare intersectional groups.
• No explicit adversarial robustness or worst-case attack evaluation; threat model is implicit and non-adversarial.
• ILP scalability is not fully discussed—large attribute spaces with many groups and labels could pose computational challenges.
• External data distribution estimation assumes sampling without replacement but does not address biases in external sources or domain shifts.
• Data modifications are limited to additions/deletions only; no label flips or feature transformations considered.
• Code release and detailed reproducibility artifacts are not explicitly stated.

Open questions / follow-ons

• How does the framework scale and perform in very high-dimensional settings with many sensitive attributes and non-binary labels?
• What are the effects of distributional shifts between training and downstream application data on coverage-constrained bias mitigation?
• Can the ILP formulation be extended to include other types of data modifications like label corrections or feature perturbations?
• How does mitigation influence individual fairness or fairness-interpretability, given focus here is on group fairness and coverage?

Why it matters for bot defense

This paper provides a rigorous framework for data-level bias mitigation that explicitly incorporates coverage constraints to ensure sufficient representation of all demographic groups, including intersectional ones. For bot-defense or CAPTCHA practitioners, this work highlights the importance of maintaining minimum sample sizes per user subgroup when preparing training datasets, rather than solely focusing on fairness metrics. Neglecting coverage can lead to degrading classifier performance on underrepresented groups, weakening detection robustness.

The integer linear programming approach enables optimized trade-offs between fairness targets and data acquisition cost, which could be valuable for practitioners balancing operational constraints. The sample complexity results also inform data collection strategies to estimate subgroup distributions efficiently before mitigation. While this paper focuses on static bias in supervised classification rather than adversarial bot attacks, its principles on intersectional coverage, explicit fairness-cost quantification, and approximate mitigation with tunable bias thresholds are broadly applicable to any ML system needing fairness-aware preprocessing in high-stakes environments like bot detection or CAPTCHA classification.

Cite

@article{arxiv2606_20461,
  title={ Data Bias Mitigation under Coverage Constraints & The Price of Fairness },
  author={ Bruno Scarone and Alfredo Viola and Renée J. Miller },
  journal={arXiv preprint arXiv:2606.20461},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.20461}
}

Read the full paper

• arXiv:2606.20461 (abstract)
• arXiv:2606.20461 (PDF)