  As algorithmic decision-making systems are becoming more pervasive, it is
crucial to ensure such systems do not become mechanisms of unfair
discrimination on the basis of gender, race, ethnicity, religion, etc.
Moreover, due to the inherent trade-off between fairness measures and accuracy,
it is desirable to learn fairness-enhanced models without significantly
compromising the accuracy. In this paper, we propose Pareto efficient Fairness
(PEF) as a suitable fairness notion for supervised learning, that can ensure
the optimal trade-off between overall loss and other fairness criteria. The
proposed PEF notion is definition-agnostic, meaning that any well-defined
notion of fairness can be reduced to the PEF notion. To efficiently find a PEF
classifier, we cast the fairness-enhanced classification as a bilevel
optimization problem and propose a gradient-based method that can guarantee the
solution belongs to the Pareto frontier with provable guarantees for convex and
non-convex objectives. We also generalize the proposed algorithmic solution to
extract and trace arbitrary solutions from the Pareto frontier for a given
preference over accuracy and fairness measures. This approach is generic and
can be generalized to any multicriteria optimization problem to trace points on
the Pareto frontier curve, which is interesting by its own right. We
empirically demonstrate the effectiveness of the PEF solution and the extracted
Pareto frontier on real-world datasets compared to state-of-the-art methods.
