Pith. sign in

REVIEW 3 minor 37 references

Data Bias Mitigation under Coverage Constraints & The Price of Fairness

T0 review · 0 major / 3 minor · reviewed 2026-06-26 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Bias mitigation under coverage constraints trades small bias errors for data efficiency while preserving accuracy.

desk verdict Extends a prior fairness framework with coverage constraints and an ILP formulation, plus a price-of-fairness function; the evaluation claims need checking but the core moves look consistent. read the letter →

arxiv 2606.20461 v1 pith:D4A2VQ5D submitted 2026-06-18 cs.LG cs.CYcs.DB

Bruno Scarone , Alfredo Viola , Renée J. Miller This is my paper · ORCID
classification cs.LGcs.CYcs.DB
keywords biasmitigationcoverageconstraintspriceoffairnessintersectionalsubgroupsintegerlinearprogrammingdatamodificationcostmachinelearning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper extends an existing bias mitigation approach by adding coverage constraints that require enough samples from every group, including those defined by multiple sensitive attributes at once. It casts the entire problem as an integer linear program that searches over all possible ways to modify the data and shows how the smallest modification cost, called the price of fairness, rises or falls with the allowed fairness tolerance. Because exact zero bias can demand far more data than is practical, the method deliberately accepts tiny bias shortfalls in exchange for far fewer added or changed records. Experiments on public datasets confirm that models trained on the resulting data keep their predictive accuracy, and that the coverage rules themselves are needed to avoid drops in performance on downstream tasks.

What carries the argument

Integer linear program that optimizes mitigation strategies subject to coverage constraints, together with the price-of-fairness function that maps tolerance to minimum modification cost.

What would settle it

A controlled experiment on the same datasets in which adding coverage constraints and allowing the stated bias tolerance produces measurably lower accuracy or higher error on the target prediction task than the unconstrained baseline.

Watch

Extended reading notes

Core claim

By incorporating coverage constraints into bias mitigation and solving the resulting integer linear program, it is possible to guarantee sufficient representation of all groups including intersectional subgroups while expressing the minimum data-modification cost as an explicit function of the fairness tolerance; this formulation supports controlled approximation of zero bias in return for lower data-acquisition expense.

Load-bearing premise

That enforcing coverage constraints and accepting small bias errors will not materially degrade the downstream machine-learning task.

Editorial extensions

If this is right

  • Data-governance decisions can be made by comparing the price-of-fairness curve against concrete purchasing or labeling budgets.
  • Legal thresholds on fairness can be met by solving the program once for the required tolerance.
  • Predictive accuracy is maintained across multiple classifiers when coverage is enforced.
  • Intersectional subgroups receive explicit representation guarantees that were previously missing.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same program could be rerun after each new data purchase to decide whether further collection is still cost-effective.
  • The price-of-fairness curve supplies a direct input for budgeting fairness compliance in production pipelines.
  • If downstream tasks change, the same coverage constraints can be reused without re-deriving the entire mitigation plan.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The paper extends a prior bias mitigation framework to include coverage constraints enforcing sufficient representation of groups (including intersectional subgroups). It formulates bias mitigation as an integer linear program optimizing over mitigation strategies, allows trading small bias approximation errors for data efficiency under the constraints, and characterizes the price of fairness (minimum data modification cost) as a function of fairness tolerance. The approach is evaluated on public datasets, with claims that it preserves predictive accuracy across classifiers and that coverage constraints are essential for downstream ML performance.

Significance. If the ILP formulation, price-of-fairness characterization, and empirical results hold, the work offers a practical, optimization-driven method for balancing fairness, coverage, and data costs. This has direct value for legal compliance (fairness thresholds) and data governance (purchasing trade-offs), while addressing intersectional representation gaps. The explicit function relating tolerance to modification cost is a useful quantitative tool for practitioners.

minor comments (3)
  1. [Abstract] Abstract and introduction: the 'recent bias mitigation framework' being extended is not named or cited; this reference should appear explicitly in §1 or the related-work section to allow readers to assess the precise extension.
  2. [Evaluation] Evaluation section: the claim that coverage constraints are 'essential for preserving downstream ML performance' requires a direct ablation (with vs. without constraints) with reported accuracy deltas, dataset names, and classifier details; the current high-level statement leaves the strength of this result unclear.
  3. Notation: the fairness tolerance parameter and the precise definition of the price-of-fairness function should be introduced with an equation number in the ILP formulation section for traceability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work and the recommendation of minor revision. The referee's description accurately reflects the paper's contributions on extending bias mitigation with coverage constraints, the ILP formulation, and the price-of-fairness characterization.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; derivation is self-contained

full rationale

The paper's central steps—extending a bias mitigation framework with coverage constraints (including intersectional), encoding mitigation as an ILP over strategies, and characterizing price of fairness explicitly as a function of fairness tolerance—are presented as standard optimization and derivation moves. No equation or claim reduces by construction to a fitted parameter, self-defined quantity, or load-bearing self-citation chain. The abstract and description treat the price-of-fairness result as derived from the ILP and tolerance parameter rather than renamed or fitted input. Coverage constraints are motivated by statistical and downstream performance considerations, not smuggled via prior ansatz. This is the common case of an independent methodological extension with no exhibited circular reduction.

Assumptions & free parameters 1 free parameters · 1 assumptions · 0 invented entities

Abstract-only review limits visibility into parameters and assumptions. The fairness tolerance appears as a tunable input that controls the cost function. The extension itself rests on the unexamined claim that the prior framework admits coverage constraints without breaking its guarantees.

free parameters (1)
  • fairness tolerance
    The allowed bias approximation error level that trades off against data modification cost; the price of fairness is defined as a function of this tolerance.
assumptions (1)
  • domain assumption A recent bias mitigation framework exists that can be extended to incorporate coverage constraints while preserving its core mitigation properties.
    This is the starting point for the extension described in the abstract.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Data Bias Mitigation under Coverage Constraints & The Price of Fairness." pith.science (2026). https://pith.science/paper/D4A2VQ5D

@misc{pith2026260620461,
  author       = {Pith},
  title        = {Pith review of: Data Bias Mitigation under Coverage Constraints & The Price of Fairness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D4A2VQ5D}},
  note         = {Machine review of arXiv:2606.20461}
}
read the original abstract

Machine learning models have been shown to exhibit discriminatory outcomes or degraded performance for individuals at the intersection of multiple sensitive attributes, such as race and gender. This stems in part from two interrelated challenges: the lack of principled measures for quantifying bias (potentially intersectional), and insufficient representation of intersectional subgroups in training data. We extend a recent bias mitigation framework to incorporate coverage constraints that enforce sufficient representation across groups, including intersectional subgroups. Since achieving exactly zero bias for all groups may not be data efficient (meaning it may require large amounts of data), our solution trades small approximation errors in bias for greater data efficiency while satisfying coverage constraints. We also formulate bias mitigation as an integer linear program that optimizes over all mitigation strategies, and characterize the price of fairness, the minimum data modification cost, as a function of fairness tolerance. This is essential both for legal compliance, where regulations may mandate specific fairness thresholds, and for data governance, enabling practitioners to make informed trade-offs between bias reduction and data modification (particularly, data purchasing) costs. We evaluate our techniques on publicly available datasets, demonstrating that bias mitigation via our framework preserves predictive accuracy across multiple classifiers, and that coverage constraints, while motivated by statistical considerations, are essential for preserving downstream ML performance.

Figures

Figures reproduced from arXiv: 2606.20461 by the authors.

Figure 1
Figure 1. Motivating example: (a) Bias detected in training data. (b) Satisfying coverage improves ML models. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Effect of fairness tolerance (𝜖) on mitigation solutions for the COMPAS dataset (𝑚s,𝑦 = 1, 𝑐𝑎 = 𝑐𝑑 = 1). 0.00 0.25 0.50 0.75 1.00 Coverage scale 5000 10000 15000 20000 25000 Total changes 0.00 0.25 0.50 0.75 1.00 Coverage scale 0 1000 2000 3000 4000 Additions 0.00 0.25 0.50 0.75 1.00 Coverage scale 0 5000 10000 15000 20000 25000 Deletions 0.00 0.25 0.50 0.75 1.00 Coverage scale 25000 30000 35000 40000 45000 50000 Fi… view at source ↗
Figure 3
Figure 3. Effect of coverage scale on mitigation solutions for the Adult dataset [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (15 more)
Figure 4
Figure 4. Figure 4: Effect of cost ratio on mitigation solutions for the Default dataset [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: a presents accuracy as a function of the fairness tolerance 𝜖 under the min_changes objective. Our results demonstrate that satisfying fairness constraints via data bias mitigation does not meaningfully degrade predictive accuracy. The COMPAS dataset exhibits strong st…
Figure 6
Figure 6. Figure 6: Results for COMPAS (Left) and Default (Center and Right). [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]
Figure 7
Figure 7. Figure 7: Accuracy vs. cost ratio for the min_cost objective (𝜖 = 0.05, 𝑚s,𝑦 = 1). Left: COMPAS, Center: Adult, Right: Default. 7 Conclusions and future work We designed bias mitigation algorithms that incorporate coverage constraints, enforcing sufficient representation across …
Figure 8
Figure 8. Figure 8: Effect of fairness tolerance (𝜖) on mitigation solutions for the Adult dataset. 0.05 0.10 0.15 (Fairness tolerance) 0 5000 10000 15000 20000 25000 30000 Total changes 0.05 0.10 0.15 (Fairness tolerance) 0 100 200 300 Additions 0.05 0.10 0.15 (Fairness tolerance) 0 5000…
Figure 9
Figure 9. Figure 9: Effect of fairness tolerance (𝜖) on mitigation solutions for the Default dataset. 0.00 0.25 0.50 0.75 1.00 Coverage scale 0 10000 20000 30000 Total changes 0.00 0.25 0.50 0.75 1.00 Coverage scale 0 200 400 600 800 1000 Additions 0.00 0.25 0.50 0.75 1.00 Coverage scale …
Figure 10
Figure 10. Figure 10: Effect of coverage scale on mitigation solutions for the COMPAS dataset. [PITH_FULL_IMAGE:figures/full_fig_p029_10.png]
Figure 11
Figure 11. Figure 11: Effect of coverage scale on mitigation solutions for the Default dataset. [PITH_FULL_IMAGE:figures/full_fig_p030_11.png]
Figure 12
Figure 12. Figure 12: Effect of cost ratio on mitigation solutions for the Adult dataset. [PITH_FULL_IMAGE:figures/full_fig_p030_12.png]
Figure 13
Figure 13. Figure 13: Effect of cost ratio on mitigation solutions for the COMPAS dataset. [PITH_FULL_IMAGE:figures/full_fig_p030_13.png]
Figure 14
Figure 14. Figure 14: Fairness tolerance vs. Accuracy: Adult dataset. [PITH_FULL_IMAGE:figures/full_fig_p031_14.png]
Figure 15
Figure 15. Figure 15: Fairness tolerance vs. Accuracy: Default dataset. [PITH_FULL_IMAGE:figures/full_fig_p032_15.png]
Figure 16
Figure 16. Figure 16: Coverage vs. Accuracy: Adult dataset. 0.0 0.2 0.4 0.6 0.8 1.0 Coverage scale 0.63 0.64 0.65 0.66 0.67 0.68 0.69 accuracy adaboost extra_trees gradient_boosting logistic_regression random_forest [PITH_FULL_IMAGE:figures/full_fig_p032_16.png]
Figure 17
Figure 17. Figure 17: Coverage vs. Accuracy: COMPAS min_size objective [PITH_FULL_IMAGE:figures/full_fig_p032_17.png]
Figure 18
Figure 18. Figure 18: Coverage vs. Accuracy: Default min_changes objective [PITH_FULL_IMAGE:figures/full_fig_p033_18.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 8 canonical work pages

  1. [1]

    Angwin, J

    J. Angwin, J. Larson, S. Mattu, and L. Kirchner. 2016. How We Analyzed the COMPAS Recidivism Algorithm. https://www.propublica. org/article/how-we-analyzed-the-compas-recidivism-algorithm

    2016

  2. [2]

    Abolfazl Asudeh, Zhongjun Jin, and HV Jagadish. 2019. Assessing and remedying coverage for a given dataset. In2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, Macau, China, 554–565

    2019

  3. [3]

    Rémi Bardenet and Odalric-Ambrym Maillard. 2015. Concentration inequalities for sampling without replacement.Bernoulli21, 3 (2015), 1361–1385

    2015

  4. [4]

    2023.Fairness and machine learning: Limitations and opportunities

    Solon Barocas, Moritz Hardt, and Arvind Narayanan. 2023.Fairness and machine learning: Limitations and opportunities. MIT Press, Cambridge, MA

    2023

  5. [5]

    Solon Barocas and Andrew D. Selbst. 2016. Big data’s disparate impact.California Law Review104 (2016), 671

    2016

  6. [6]

    Barry Becker and Ronny Kohavi. 1996. Adult. UCI Machine Learning Repository. doi: https://doi.org/10.24432/C5XW20

    work page doi:10.24432/c5xw20 1996

  7. [7]

    Joy Buolamwini and Timnit Gebru. 2018. Gender Shades: Intersectional Accuracy Disparities in Commercial Gender Classification. InProceedings of the 1st Conference on Fairness, Accountability and Transparency (Proceedings of Machine Learning Research, Vol. 81), Sorelle A. Friedler and Christo Wilson (Eds.). PMLR, New York, USA, 77–91. https://proceedings.m...

    2018

  8. [8]

    Irene Chen, Fredrik D Johansson, and David Sontag. 2018. Why Is My Classifier Discriminatory?. InAdvances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31. Curran Associates, Inc., Montréal, Quebec, Canada. https://proceedings.neurips.cc/paper_files/paper/2018/file/...

    2018

Show all 37 references
  1. [9]

    Gaebler, Hamed Nilforoshan, Ravi Shroff, and Sharad Goel

    Sam Corbett-Davies, Johann D. Gaebler, Hamed Nilforoshan, Ravi Shroff, and Sharad Goel. 2023. The Measure and Mismeasure of Fairness.Journal of Machine Learning Research24, 312 (2023), 1–117

    2023

  2. [10]

    Kimberlé Crenshaw. 2013. Demarginalizing the intersection of race and sex: A black feminist critique of antidiscrimination doctrine, feminist theory and antiracist politics. InFeminist Legal Theories. Routledge, London, UK, 23–51

    2013

  3. [11]

    Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012. Fairness through awareness. InProceedings of the 3rd Innovations in Theoretical Computer Science Conference(Cambridge, Massachusetts)(ITCS ’12). Association for Computing Machinery, New York,...

    2012 doi

  4. [12]

    Will Fleisher. 2021. What’s fair about individual fairness?. InProceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society. ACM, New York, USA, 480–490

    2021

  5. [13]

    Forthcoming

    Will Fleisher. Forthcoming. Algorithmic Fairness Criteria as Evidence.Ergo: An Open Access Journal of PhilosophyNA, NA (Forthcoming), NA

  6. [14]

    James R Foulds, Rashidul Islam, Kamrun Naher Keya, and Shimei Pan. 2020. An intersectional definition of fairness. In2020 IEEE 36th international conference on data engineering (ICDE). IEEE, Dallas, TX, USA, 1918–1921

    2020

  7. [15]

    Sorelle A Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. 2021. The (im)possibility of fairness: Different value systems require different mechanisms for fair decision making.Commun. ACM64, 4 (2021), 136–143

    2021

  8. [16]

    Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. 2018. Multicalibration: Calibration for the (computationally- identifiable) masses. InInternational Conference on Machine Learning. PMLR, Stockholm, Sweden, 1939–1948

    2018

  9. [17]

    Corinna Hertweck, Christoph Heitz, and Michele Loi. 2021. On the moral justification of statistical parity. InProceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency. ACM, New York, USA, 747–757

    2021

  10. [18]

    Max Hort, Zhenpeng Chen, Jie M Zhang, Mark Harman, and Federica Sarro. 2024. Bias mitigation for machine learning classifiers: A comprehensive survey.ACM Journal on Responsible Computing1, 2 (2024), 1–52

    2024

  11. [19]

    Mohammad Hossein Jarrahi, Ali Memariani, and Shion Guha. 2023. The principles of data-centric AI.Commun. ACM66, 8 (2023), 84–92

    2023

  12. [20]

    Deborah Dormah Kanubala and Isabel Valera. 2025. On the Misalignment Between Legal Notions and Statistical Metrics of Intersectional Fairness. InProceedings of the AAAI/ACM Conference on AI, Ethics, and Society. ACM, Madrid, Spain, 1363–1374

    2025

  13. [21]

    Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. 2018. Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness. InProceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 80), Jenni...

    2018

  14. [22]

    Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. 2019. An Empirical Study of Rich Subgroup Fairness for Machine Learning. InProceedings of the Conference on Fairness, Accountability, and Transparency(Atlanta, GA, USA)(FAT* ’19). Association for Data Bias Mitigation...

    2019 doi

  15. [23]

    Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. 2017. Inherent Trade-Offs in the Fair Determination of Risk Scores. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (Leibniz International Proceedings in Informatics, Vol. 67). Schloss D...

    2017

  16. [24]

    Kristian Lum, Yunfeng Zhang, and Amanda Bower. 2022. De-biasing “bias” measurement. InACM Conference on Fairness, Accountability, and Transparency(Seoul, Republic of Korea)(FAccT ’22). Association for Computing Machinery, New York, NY, USA, 379–389. doi:10. 1145/3531146.3533105

    2022

  17. [25]

    Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. 2021. A survey on bias and fairness in machine learning.ACM computing surveys (CSUR)54, 6 (2021), 1–35

    2021

  18. [26]

    Williamson

    Aditya Krishna Menon and Robert C. Williamson. 2018. The Cost of Fairness in Binary Classification. InProceedings of the 1st Conference on Fairness, Accountability and Transparency (Proceedings of Machine Learning Research, Vol. 81). PMLR, New York, NY, USA, 107–118

    2018

  19. [27]

    Fatemeh Nargesian, Abolfazl Asudeh, and HV Jagadish. 2021. Tailoring data source distributions for fairness-aware data integration. Proceedings of the VLDB Endowment14, 11 (2021), 2519–2532

    2021

  20. [28]

    Romila Pradhan, Jiongli Zhu, Boris Glavic, and Babak Salimi. 2022. Interpretable Data-Based Explanations for Fairness Debugging. In Proceedings of the 2022 International Conference on Management of Data (SIGMOD ’22). ACM, Philadelphia, PA, USA, 247–261

    2022

  21. [29]

    Joaquin Quiñonero Candela, Yuwen Wu, Brian Hsu, Sakshi Jain, Jennifer Ramos, Jon Adams, Robert Hallman, and Kinjal Basu. 2023. Disentangling and operationalizing ai fairness at Linkedin. InProceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency. AC...

    2023

  22. [30]

    Miller, and Ricardo Baeza-Yates

    Bruno Scarone, Alfredo Viola, Renée J. Miller, and Ricardo Baeza-Yates. 2025. A Principled Approach for Data Bias Mitigation.Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society8, 3 (Oct. 2025), 2273–2283. doi:10.1609/aies.v8i3.36712

    2025 doi

  23. [31]

    Robert J Serfling. 1974. Probability inequalities for the sum in sampling without replacement.The Annals of Statistics2, 1 (1974), 39–48

    1974

  24. [32]

    Nima Shahbazi, Yin Lin, Abolfazl Asudeh, and HV Jagadish. 2023. Representation bias in data: A survey on identification and resolution techniques.Comput. Surveys55, 13s (2023), 1–39

    2023

  25. [33]

    Angelina Wang, Vikram V Ramaswamy, and Olga Russakovsky. 2022. Towards Intersectionality in Machine Learning: Including More Identities, Handling Underrepresentation, and Performing Evaluation. InProceedings of the 2022 ACM Conference on Fairness, Accountability, and Transpare...

    2022 doi

  26. [34]

    I-Cheng Yeh. 2016. Default of credit card clients. UCI Machine Learning Repository. doi: https://doi.org/10.24432/C55S3H

    2016 doi

  27. [35]

    Min-Hsuan Yeh, Blossom Metevier, Austin Hoag, and Philip Thomas. 2024. Analyzing the Relationship Between Difference and Ratio-Based Fairness Metrics. InProceedings of the 2024 ACM Conference on Fairness, Accountability, and Transparency(Rio de Janeiro, Brazil)(FAccT ’24). Ass...

    2024 doi

  28. [36]

    Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P. Gummadi. 2017. Fairness Constraints: Mechanisms for Fair Classification. InProceedings of the 20th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Re...

    2017

  29. [37]

    Indr˙e Žliobait ˙e. 2017. Measuring discrimination in algorithmic decision making.Data Mining and Knowledge Discovery31, 4 (2017), 1060–1089. Generative AI Usage Statement The authors used Claude (Anthropic, models Sonnet 4.5 and Opus 4.5) occasionally for grammar checking of ...

    2017

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.