Learning Non-Discriminatory Predictors
Open accessAbstract
We consider learning a predictor which is non-discriminatory with respect to a "protected attribute" according to the notion of "equalized odds" proposed by Hardt et al. [2016]. We study the problem of learning such a non-discriminatory predictor from a finite training set, both statistically and computationally. We show that a post-hoc correction approach, as suggested by Hardt et al, can be highly suboptimal, present a nearly-optimal statistical procedure, argue that the associated computational problem is intractable, and suggest a second moment relaxation of the non-discrimination definition for which learning is tractable.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Woodworth et al. [2017] show that finding a linear threshold classifier that approximately minimizes hinge loss subject to equalizing false positive rates across populations is computationally hard, assuming that refuting a random k-XOR formula is hard.
“Most notably, Woodworth et al. [2017] show that finding a linear threshold classifier that approximately minimizes hinge loss subject to equalizing false positive rates across populations is computationally hard (assuming that refuting a random k -XOR formula is hard).”
From Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness (2017) · cites this paper as Woodworth et al. [2017]
Split into 2 atoms — 0 confirmed, 2 partially supported, 0 disputed, 0 misattributed, 0 unverifiable. Expand the claim to see per-atom verdicts.
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 10
- [1][1] Olivier Bousquet, St´ ephane Boucheron, and G´ abor Lugosi. Introduction to statistical learning theory. In Advanced lectures on machine learning , pages 169-207. Springer, 2004. -
- [2][2] Amit Daniely. Complexity theoretic limitations on learning halfspaces. arXiv preprint arXiv:1505.05800 , 2015. - · arXiv
- [3][3] Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. From average case complexity to improper learning complexity. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing , pages 441448. ACM, 2014. -
- [4][4] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference , pages 214-226. ACM, 2012. -
- [5][5] Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. Certifying and removing disparate impact. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages 259-268. ACM, 2015. -
- [6][6] Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems , 2016. -
- [7][7] Matthew Joseph, Michael Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. Rawlsian fairness for machine learning. arXiv preprint arXiv:1610.09559 , 2016. - · arXiv
- [8][8] Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. Fairness in learning: Classic and contextual bandits. In Advances in Neural Information Processing Systems , pages 325-333, 2016. -
- [9][9] Dino Pedreshi, Salvatore Ruggieri, and Franco Turini. Discrimination-aware data mining. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining , pages 560-568. ACM, 2008. -
- [11][11] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi. Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment. CoRR , abs/1610.08452, 2016. URL http://dblp.uni-trier.de/db/journals/corr/corr1610. html#ZafarVGG16;http://arxiv.org/abs/1610.08452 . · arXiv
Cited by
Sorted by citations
A Survey on Bias and Fairness in Machine Learning
Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., & Galstyan, A. (2022) · ACM Computing Surveys · doi:10.1145/3457607 · Cited by 5,812 · see citing works
Ensuring fairness in machine learning to advance health equity.
Rajkomar, A., Hardt, M., Howell, M. D., Corrado, G., & Chin, M. H. (2018) · Annals of Internal Medicine · doi:10.7326/m18-1990 · Cited by 1,341 · see citing works
A comparative study of fairness-enhancing interventions in machine learning
Friedler, S. A., Scheidegger, C., Venkatasubramanian, S., Choudhary, S., Hamilton, E. P., & Roth, D. (2019) · Proceedings of the Conference on Fairness, Accountability, and Transparency · doi:10.1145/3287560.3287589 · Cited by 601 · see citing works
Fairness in machine learning: A survey
Caton, S., & Haas, C. (2024) · ACM Computing Surveys · doi:10.1145/3616865 · Cited by 646 · see citing works
Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness
Kearns, M., Neel, S., Roth, A., & Wu, Z. S. (2017) · arXiv · doi:10.48550/arxiv.1711.05144 · Cited by 381 · see citing works
Timmons, A. C., Duong, J. B., Simo Fiallo, N., Lee, T., Vo, H. P. Q., Ahle, M. W., Comer, J. S., Brewer, L. C., Frazier, S. L., & Chaspari, T. (2023) · Perspectives on Psychological Science · doi:10.1177/17456916221134490 · Cited by 263 · see citing works
Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees
Celis, L. E., Huang, L., Keswani, V., & Vishnoi, N. K. (2019) · Proceedings of the Conference on Fairness, Accountability, and Transparency · doi:10.1145/3287560.3287586 · Cited by 231 · see citing works
Koçak, B., Ponsiglione, A., Stanzione, A., Bluethgen, C., Santinha, J., Ugga, L., Huisman, M., Klontzas, M. E., Cannella, R., & Cuocolo, R. (2024) · Diagnostic and Interventional Radiology · doi:10.4274/dir.2024.242854 · Cited by 168 · see citing works
Interventional Fairness: Causal Database Repair for Algorithmic Fairness
Salimi, B., Rodriguez, L., Howe, B., & Suciu, D. (2019) · Proceedings of the 2019 International Conference on Management of Data · doi:10.1145/3299869.3319901 · Cited by 145 · see citing works
Fairness in Machine Learning: A Survey
Caton, S., & Haas, C. (2020) · arXiv · doi:10.48550/arxiv.2010.04053 · Cited by 646 · see citing works
Perrone, V., Donini, M., Zafar, M. B., Schmucker, R., Kenthapadi, K., & Archambeau, C. (2021) · Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society · doi:10.1145/3461702.3462629 · Cited by 66 · see citing works
Taking Advantage of Multitask Learning for Fair Classification
Oneto, L., Doninini, M., Elders, A., & Pontil, M. (2019) · Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society · doi:10.1145/3306618.3314255 · Cited by 64 · see citing works
Marrying Fairness and Explainability in Supervised Learning
Grabowicz, P. A., Perello, N., & Mishra, A. (2022) · 2022 ACM Conference on Fairness Accountability and Transparency · doi:10.1145/3531146.3533236 · Cited by 37 · see citing works
Promoting Fairness through Hyperparameter Optimization
F.Cruz, A., Saleiro, P., Belem, C., Soares, C., & Bizarro, P. (2021) · 2021 IEEE International Conference on Data Mining (ICDM) · doi:10.1109/icdm51629.2021.00119 · Cited by 28 · see citing works
- Authors
- Woodworth, B., Gunasekar, S., Ohannessian, M. I., & Srebro, N.
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2017
- Pages
- 1920-1953
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1702.06081
- OpenAlex
- W2594166818
- Cited by
- 182
- References
- 0
- Citations by year
- 2025: 8 · 2024: 16 · 2023: 16 · 2022: 21 · 2021: 52 · 2020: 31 · 2019: 24 · 2018: 9 · 2017: 2 · 2016: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Conference on Learning Theory
- Topics
- Social Sciences › Safety Research › Ethics and Social Impacts of AI
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Social Sciences › Law › Discrimination and Equality Law
- Keywords
- algorithmic fairness, equalized odds, protected characteristics, post-hoc correction, computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
