  Algorithmic fairness plays an increasingly critical role in machine learning
research. Several group fairness notions and algorithms have been proposed.
However, the fairness guarantee of existing fair classification methods mainly
depends on specific data distributional assumptions, often requiring large
sample sizes, and fairness could be violated when there is a modest number of
samples, which is often the case in practice. In this paper, we propose FaiREE,
a fair classification algorithm that can satisfy group fairness constraints
with finite-sample and distribution-free theoretical guarantees. FaiREE can be
adapted to satisfy various group fairness notions (e.g., Equality of
Opportunity, Equalized Odds, Demographic Parity, etc.) and achieve the optimal
accuracy. These theoretical guarantees are further supported by experiments on
both synthetic and real data. FaiREE is shown to have favorable performance
over state-of-the-art algorithms.
