  Fairness has become a crucial aspect in the development of trustworthy
machine learning algorithms. Current fairness metrics to measure the violation
of demographic parity have the following drawbacks: (i) the average difference
of model predictions on two groups cannot reflect their distribution disparity,
and (ii) the overall calculation along all possible predictions conceals the
extreme local disparity at or around certain predictions. In this work, we
propose a novel fairness metric called Maximal Cumulative ratio Disparity along
varying Predictions' neighborhood (MCDP), for measuring the maximal local
disparity of the fairness-aware classifiers. To accurately and efficiently
calculate the MCDP, we develop a provably exact and an approximate calculation
algorithm that greatly reduces the computational complexity with low estimation
error. We further propose a bi-level optimization algorithm using a
differentiable approximation of the MCDP for improving the algorithmic
fairness. Extensive experiments on both tabular and image datasets validate
that our fair training algorithm can achieve superior fairness-accuracy
trade-offs.
