  Learning a fair predictive model is crucial to mitigate biased decisions
against minority groups in high-stakes applications. A common approach to learn
such a model involves solving an optimization problem that maximizes the
predictive power of the model under an appropriate group fairness constraint.
However, in practice, sensitive attributes are often missing or noisy resulting
in uncertainty. We demonstrate that solely enforcing fairness constraints on
uncertain sensitive attributes can fall significantly short in achieving the
level of fairness of models trained without uncertainty. To overcome this
limitation, we propose a bootstrap-based algorithm that achieves the target
level of fairness despite the uncertainty in sensitive attributes. The
algorithm is guided by a Gaussian analysis for the independence notion of
fairness where we propose a robust quadratically constrained quadratic problem
to ensure a strict fairness guarantee with uncertain sensitive attributes. Our
algorithm is applicable to both discrete and continuous sensitive attributes
and is effective in real-world classification and regression tasks for various
group fairness notions, e.g., independence and separation.
