Classification with Fairness Constraints: A Meta-Algorithm with Provable
  Guarantees
  Developing classification algorithms that are fair with respect to sensitive
attributes of the data has become an important problem due to the growing
deployment of classification algorithms in various social contexts. Several
recent works have focused on fairness with respect to a specific metric,
modeled the corresponding fair classification problem as a constrained
optimization problem, and developed tailored algorithms to solve them. Despite
this, there still remain important metrics for which we do not have fair
classifiers and many of the aforementioned algorithms do not come with
theoretical guarantees; perhaps because the resulting optimization problem is
non-convex. The main contribution of this paper is a new meta-algorithm for
classification that takes as input a large class of fairness constraints, with
respect to multiple non-disjoint sensitive attributes, and which comes with
provable guarantees. This is achieved by first developing a meta-algorithm for
a large family of classification problems with convex constraints, and then
showing that classification problems with general types of fairness constraints
can be reduced to those in this family. We present empirical results that show
that our algorithm can achieve near-perfect fairness with respect to various
fairness metrics, and that the loss in accuracy due to the imposed fairness
constraints is often small. Overall, this work unifies several prior works on
fair classification, presents a practical algorithm with theoretical
guarantees, and can handle fairness metrics that were previously not possible.
