Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees

By L. Elisa Celis, Lingxiao Huang, Vijay Keswani, Nisheeth K. Vishnoi. 2018

365 citations recorded by the source corpus.

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.

Subfields: Safety Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Safety Research

Citations in the corpus

Stable and Fair Classification (2019, background): “From a technical view, most relevant prior works formulated the fair classiﬁcation problem as a constrained optimization problem, e.g., constrained to statistical parity [75, 55, 32, 13], or equalized odds [37, 74, 55, 13].”
Predictive Multiplicity in Classification (2019, background): “, AUC), predict multiple outcomes, or satisfy additional constraints (e.g., group fairness constraints as in Zafar et al., 2019; Celis et al., 2019; Cotter et al., 2019).”
Learning Fair Rule Lists (2019, background): “With respect to fairness, a significant amount of work has been done in recent years to design fairness-aware machine learning models (Friedler et al., 2019; Celis et al., 2019), which we will review in Section 3.”
Rényi Fair Inference (2019, methodology): “As we experience the widespread adoption of machine learning models in automated decisionmaking, we have witnessed increased reports of instances in which the employed model results in discrimination against certain groups of individuals – see Datta et al. (2015); Sweeney (2013); Bolukbasi et al.”
Value-laden disciplinary shifts in machine learning (2019, background): “For example, to understand whether such models exacerbate existing racial, gender, or other disparities between groups and to intervene to mitigate such disparities [1–6].”
Explainable AI: A Review of Machine Learning Interpretability Methods (2020, background): “[98] highlighted that, although efforts have been made in recent studies to achieve fairness with respect to some particular metric, some important metrics have been ignored, while some of the proposed algorithms are not supported by a solid theoretical background.”
Trustworthy AI: From Principles to Practices (2021, neutral): “For instance, quantitative fairness metrics can be used as regularization [7] or constraints for the optimization of the model parameters [67].”
Toward Controlling Discrimination in Online Ad Auctions (2019, methodology): “Finally, a framework approach to fairness constraints has shown to be effective in various other applications such as classification [8,32,56], selection of representatives [9], and personalization [14].”
Assessing Social and Intersectional Biases in Contextualized Word Representations (2019, background): “Barring the precise construction of datasets that reach representational parity across social groups, other techniques like corpus-level constraints [32], learning constraints [6] or post-processing [2] are likely to be more convenient solutions, though they ignore the origins of the problem [4].”