When one predictive model must serve multiple demographic groups, improving accuracy for one group can worsen fairness for another. The fairness-accuracy (FA) Pareto frontier captures the set of models that cannot be improved on either dimension without hurting the other. This paper studies how well a designer can approximate any point on that frontier when only limited data is available, bounding the worst-case gap between the true frontier and what can be estimated.

The authors derive worst-case-optimal estimators whose form depends on how much the designer knows about the covariate distribution. They show that finite-sample errors do not affect all groups equally: the approximation gap can be asymmetric across groups, and they identify how to allocate samples among groups to minimize the worst-case gap.

The paper also provides uniform finite-sample bounds along the entire FA frontier, not just at isolated points. This means the results cover a range of possible fairness-accuracy tradeoffs, giving practitioners a clearer picture of what is achievable with finite data and where the limits lie.