Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees
Open accessAbstract
Developing classification algorithms that are fair with respect to sensitive attributes of the data is an important problem due to the increased deployment of classification algorithms in societal contexts. Several recent works have focused on studying classification with respect to specific fairness metrics, modeled the corresponding fair classification problem as constrained optimization problems, and developed tailored algorithms to solve them. Despite this, there still remain important metrics for which there are no fair classifiers with theoretical guarantees; primarily because the resulting optimization problem is non-convex. The main contribution of this paper is a meta-algorithm for classification that can take as input a general class of fairness constraints with respect to multiple non-disjoint and multi-valued sensitive attributes, and which comes with provable guarantees. In particular, our algorithm can handle non-convex "linear fractional" constraints (which includes fairness constraints such as predictive parity) for which no prior algorithm was known. Key to our results is an algorithm for a family of classification problems with convex constraints along with a reduction from classification problems with linear fractional constraints to this family. Empirically, we observe that our algorithm is fast, can achieve near-perfect fairness with respect to various fairness metrics, and the loss in accuracy due to the imposed fairness constraints is often small.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
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?
When extending the classifier's (convex) loss function with fairness terms, researchers typically seek to balance fairness and accuracy.
“When extending the classiier's (convex) loss function with fairness terms, researchers typically seek to balance fairness and accuracy (e.g.[5,26,36,52,57,98,119,141,153,168,208,314]).”
From Fairness in machine learning: A survey (2024) · cites this paper as [57]
In-processing (constraint) optimization approaches have similar objectives to fairness regularization approaches.
“In-processing (constraint) optimization approaches (e.g.[3, 57, 68, 79, 120, 135, 174, 208, 218, 219, 221, 307, 313]) have similar objectives to fairness regularization approaches, and hence we present them together.”
From Fairness in machine learning: A survey (2024) · cites this paper as [57]
Cites
UCI Machine Learning Repository
Asuncion, A. (2007) · Medical Entomology and Zoology · Cited by 24,190 · see citing works
Proceedings of the 25th international conference on Machine learning - ICML '08
(2008) · doi:10.1145/1390156 · Cited by 6,865 · see citing works
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., & Zemel, R. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090255 · Cited by 3,501 · see citing works
Barocas, S., & Selbst, A. D. (2014) · doi:10.2139/ssrn.2477899 · Cited by 3,048 · see citing works
Equality of Opportunity in Supervised Learning
Hardt, M., Price, E., & Srebro, N. (2016) · arXiv · doi:10.48550/arxiv.1610.02413 · Cited by 2,536 · see citing works
Fair prediction with disparate impact: a study of bias in recidivism prediction instruments
Chouldechova, A. (2017) · Big Data · doi:10.1089/big.2016.0047 · Cited by 2,159 · see citing works
Certifying and Removing Disparate Impact
Feldman, M., Friedler, S. A., Moeller, J., Scheidegger, C., & Venkatasubramanian, S. (2015) · Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2783258.2783311 · Cited by 1,827 · see citing works
Proceedings of the 29th International Conference on Machine Learning (ICML-12)Preprint
Langford, J. C., & Pineau, J. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1207.4676 · Cited by 1,687 · see citing works
Data preprocessing techniques for classification without discrimination
Kamiran, F., & Calders, T. (2012) · Knowledge and Information Systems · doi:10.1007/s10115-011-0463-8 · Cited by 1,305 · see citing works
Algorithmic Decision Making and the Cost of Fairness
Corbett-Davies, S., Pierson, E., Feller, A., Goel, S., & Huq, A. (2017) · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/3097983.3098095 · Cited by 1,149 · see citing works
(2013) · Cited by 1,126 · see citing works
Inherent trade-offs in the fair determination of risk scores
Kleinberg, J., Mullainathan, S., & Raghavan, M. (2017) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/lipics.itcs.2017.43 · Cited by 943 · cited 3× · see citing works
“Unfortunately, this does come at a loss of accuracy, likely due to the difficulty of simultaneously achieving accuracy and multiple fairness metrics [16, 41].”
BackgroundThree naive Bayes approaches for discrimination-free classification.
Calders, T., & Verwer, S. (2010) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-010-0190-x · Cited by 764 · see citing works
Fairness-Aware Classifier with Prejudice Remover Regularizer
Kamishima, T., Akaho, S., Asoh, H., & Sakuma, J. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33486-3_3 · Cited by 694 · see citing works
Automated Experiments on Ad Privacy Settings: A Tale of Opacity, Choice, and Discrimination
Datta, A., Tschantz, M. C., & Datta, A. (2015) · Proceedings on Privacy Enhancing Technologies · doi:10.1515/popets-2015-0007 · Cited by 676 · see citing works
Discrimination-aware data mining
Pedreshi, D., Ruggieri, S., & Turini, F. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401959 · Cited by 676 · see citing works
Zafar, M. B., Valera, I., Gomez Rodriguez, M., & Gummadi, K. P. (2017) · Proceedings of the 26th International Conference on World Wide Web · doi:10.1145/3038912.3052660 · Cited by 632 · see citing works
On Fairness and CalibrationPreprint
Pleiss, G., Raghavan, M., Wu, F., Kleinberg, J. M., & Weinberger, K. Q. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1709.02012 · Cited by 509 · see citing works
Classifying without discriminating
Kamiran, F., & Calders, T. (2009) · 2009 2nd International Conference on Computer, Control and Communication · doi:10.1109/ic4.2009.4909197 · Cited by 409 · see citing works
Kull, M., Filho, T. M. S., & Flach, P. A. (2017) · Cited by 404 · see citing works
Measuring Fairness in Ranked Outputs
Yang, K., & Stoyanovich, J. (2017) · Proceedings of the 29th International Conference on Scientific and Statistical Database Management · doi:10.1145/3085504.3085526 · Cited by 378 · see citing works
A Reductions Approach to Fair ClassificationPreprint
Agarwal, A., Beygelzimer, A., Dudı́k, M., Langford, J. C., & Wallach, H. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.02453 · Cited by 364 · see citing works
Precinct or prejudice? Understanding racial disparities in New York City’s stop-and-frisk policy
Goel, S., Rao, J. M., & Shroff, R. (2016) · The Annals of Applied Statistics · doi:10.1214/15-aoas897 · Cited by 285 · see citing works
Measuring discrimination in algorithmic decision making
Žliobaitė, I. (2017) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-017-0506-1 · Cited by 272 · see citing works
k-NN as an implementation of situation testing for discrimination discovery and prevention
Luong, B. T., Ruggieri, S., & Turini, F. (2011) · Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2020408.2020488 · Cited by 263 · see citing works
Settling the Polynomial Learnability of Mixtures of Gaussians
Moitra, A., & Valiant, G. J. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.15 · Cited by 261 · see citing works
On the (im)possibility of fairness
Friedler, S. A., Scheidegger, C., & Venkatasubramanian, S. (2016) · arXiv · doi:10.48550/arxiv.1609.07236 · Cited by 247 · see citing works
Flores, A. W., Bechtel, K., & Lowenkamp, C. T. (2016) · Federal probation · Cited by 244 · see citing works
Grgic-Hlaca, N., Redmiles, E. M., Gummadi, K. P., & Weller, A. (2018) · Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18 · doi:10.1145/3178876.3186138 · Cited by 207 · see citing works
Fairness in Learning: Classic and Contextual Bandits
Joseph, M., Kearns, M., Morgenstern, J., & Roth, A. (2016) · arXiv · doi:10.48550/arxiv.1605.07139 · Cited by 199 · cited 1× · see citing works
“There are increasingly many works with provable guarantees, including [26, 34, 55, 58], that provide different classification algorithms with constraints on statistical parity or equalized odds, and [36, 40] for fairness in multi-armed bandit settings or ranking problems respectively.”
BackgroundGrgić-Hlača, N., Zafar, M. B., Gummadi, K. P., & Weller, A. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11296 · Cited by 184 · see citing works
Learning Non-Discriminatory Predictors
Woodworth, B., Gunasekar, S., Ohannessian, M. I., & Srebro, N. (2017) · arXiv · doi:10.48550/arxiv.1702.06081 · Cited by 182 · see citing works
A Confidence-Based Approach for Balancing Fairness and Accuracy
Fish, B., Kun, J., & Lelkes, Á. D. (2016) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611974348.17 · Cited by 163 · see citing works
The cost of fairness in binary classification
Menon, A. K., & Williamson, R. C. (2018) · Cited by 157 · see citing works
Satisfying Real-world Goals with Dataset ConstraintsPreprint
Goh, G., Cotter, A., Gupta, M. R., & Friedlander, M. P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1606.07558 · Cited by 131 · see citing works
Adaptive Sensitive Reweighting to Mitigate Bias in Fairness-aware Classification
Krasanakis, E., Spyromitros-Xioufis, E., Papadopoulos, S., & Kompatsiaris, Y. (2018) · Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18 · doi:10.1145/3178876.3186133 · Cited by 127 · see citing works
Vaught, S. E. (2008) · Urban Education · doi:10.1177/0042085908318776 · Cited by 97 · see citing works
Non-Discriminatory Machine Learning through Convex Fairness Criteria
Goel, N., Yaghini, M., & Faltings, B. (2018) · Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society · doi:10.1145/3278721.3278722 · Cited by 79 · see citing works
On the Statistical Consistency of Plug-in Classifiers for Non-decomposable Performance Measures
Narasimhan, H., Vaish, R., & Agarwal, S. (2014) · neural information processing systems · Cited by 59 · see citing works
Fair and Diverse DPP-based Data SummarizationPreprint
Celis, L. E., Keswani, V., Straszak, D., Deshpande, A., Kathuria, T., & Vishnoi, N. K. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.04023 · Cited by 59 · see citing works
Self-citationRecycling Privileged Learning and Distribution Matching for Fairness
Quadrianto, N., & Sharmanska, V. (2017) · Spiral (Imperial College London) · Cited by 52 · see citing works
The Statistical Physics of Learning (in a nutshell):News from the stoneage of neural networks
Biehl, M. L. (2018) · University of Groningen research database (University of Groningen / Centre for Information Technology) · Cited by 40 · see citing works
Can ‘predictive policing' prevent crime before it happens?
(2016) · AAAS Articles DO Group · doi:10.1126/science.aah7353 · Cited by 38 · see citing works
Meritocratic fairness for cross-population selection
Kearns, M. J., Roth, A., & Wu, Z. S. (2017) · International Conference on Machine Learning · Cited by 37 · see citing works
Learning structured distributions
Diakonikolas, I. (2016) · doi:10.1201/b19567-21 · Cited by 32 · see citing works
Fair PersonalizationPreprint
Celis, L. E., & Vishnoi, N. K. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1707.02260 · Cited by 28 · see citing works
Self-citationCreamer, A. J. (1986) · IEEE Engineering Management Review · doi:10.1109/emr.1986.4306187 · Cited by 26 · see citing works
Multiwinner Voting with Fairness ConstraintsPreprint
Celis, L. E., Huang, L., & Vishnoi, N. K. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.10057 · Cited by 7 · see citing works
Self-citationRutherglen, G. A. (2017) · Cited by 6 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Explainable AI: a review of machine learning interpretability methods
Linardatos, P., Papastefanopoulos, V., & Kotsiantis, S. (2020) · Entropy · doi:10.3390/e23010018 · Cited by 2,922 · see citing works
Trustworthy AI: From Principles to Practices
Li, B., Qi, P., Liu, B., Di, S., Liu, J., Pei, J., Yi, J., & Zhou, B. (2023) · ACM Computing Surveys · doi:10.1145/3555803 · Cited by 612 · see citing works
“For instance, quantitative fairness metrics can be used as regularization [7] or constraints for the optimization of the model parameters [67].”
Fairness in machine learning: A survey
Caton, S., & Haas, C. (2024) · ACM Computing Surveys · doi:10.1145/3616865 · Cited by 646 · see citing works
An empirical characterization of fair machine learning for clinical risk prediction
Pfohl, S. R., Foryciarz, A., & Shah, N. H. (2021) · Journal of Biomedical Informatics · doi:10.1016/j.jbi.2020.103621 · Cited by 164 · 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
Fairness-Aware Machine Learning Engineering: How Far Are We?
Ferrara, C., Sellitto, G., Ferrucci, F., Palomba, F., & De Lucia, A. (2024) · Empirical Software Engineering · doi:10.1007/s10664-023-10402-y · Cited by 60 · see citing works
Silva: Interactively Assessing Machine Learning Fairness Using Causality
Yan, J. N., Gu, Z., Lin, H., & Rzeszotarski, J. M. (2020) · Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems · doi:10.1145/3313831.3376447 · Cited by 54 · see citing works
Fairness metrics and bias mitigation strategies for rating predictions
Ashokan, A., & Haas, C. (2021) · Information Processing & Management · doi:10.1016/j.ipm.2021.102646 · Cited by 47 · see citing works
Towards Unbiased and Accurate Deferral to Multiple Experts
Keswani, V., Lease, M., & Kenthapadi, K. (2021) · Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society · doi:10.1145/3461702.3462516 · Cited by 45 · see citing works
Self-citationFAIR: Fair adversarial instance re-weighting
Petrović, A., Nikolić, M., Radovanović, S., Delibašić, B., & Jovanović, M. (2022) · Neurocomputing · doi:10.1016/j.neucom.2021.12.082 · Cited by 40 · see citing works
Algorithmic decision making methods for fair credit scoring
Moldovan, D. (2023) · IEEE Access · doi:10.1109/access.2023.3286018 · Cited by 28 · see citing works
Rodolfa, K. T., Lamba, H., & Ghani, R. (2021) · Nature Machine Intelligence · doi:10.1038/s42256-021-00396-x · Cited by 10 · see citing works
- Authors
- Celis, L. E., Huang, L., Keswani, V., & Vishnoi, N. K.
- Affiliations
- Yale University (US)
- École Polytechnique Fédérale de Lausanne (CH)
- Venue
- Proceedings of the Conference on Fairness, Accountability, and Transparency
- Publisher
- ACM
- Published
- 2019-01-29
- Pages
- 319-328
- OpenAlex
- W2963100392
- Cited by
- 231
- References
- 49
- Citations by year
- 2026: 16 · 2025: 25 · 2024: 33 · 2023: 34 · 2022: 38 · 2021: 46 · 2020: 27 · 2019: 11 · 2018: 1
- FWCI
- 31.76
- Type
- conference paper
- Language
- en
- Open access
- green
- infoscience.epfl.ch
- Licence
- Locations
- ACM Conference on Fairness, Accountability, and Transparency (FAccT) (publishedVersion)
- Infoscience (Ecole Polytechnique Fédérale de Lausanne) (submittedVersion, cc-by-nc-nd)
- Topics
- Social Sciences › Safety Research › Ethics and Social Impacts of AI
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Artificial Intelligence › Explainable Artificial Intelligence (XAI)
- Keywords
- fair classification, fairness constraints, sensitive attributes, meta-algorithms, non-convex optimization, convex constraints, fairness-accuracy trade-off, provable guarantees
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
