Authors: Alireza Fallah, Michael I. Jordan, Annie Ulichney
Organizations: Department of Computer Science and Ken Kennedy Institute, Rice University · Departments of Electrical Engineering and Computer Sciences and Statistics, University of California, Berkeley; Inria Paris · Department of Statistics, University of California, Berkeley
We study fairness-accuracy tradeoffs when a single predictive model must serve multiple demographic groups. A useful tool for understanding this tradeoff is the fairness-accuracy (FA) Pareto frontier, which characterizes the set of models that cannot be improved in either fairness or accuracy without worsening the other. While characterizing the FA frontier requires full knowledge of the data distribution, we focus on the finite-sample regime, quantifying how well a designer can approximate any point on the frontier from limited data and bounding the worst-case gap. In particular, we derive worst-case-optimal estimators that depend on the designer's knowledge of the covariate distribution. For each estimator, we characterize how finite-sample effects asymmetrically impact each group's welfare and identify optimal sample allocation strategies. Finally, we provide uniform finite-sample bounds along the entire FA frontier, quantifying finite-sample deviations across alternative fairness-accuracy tradeoffs.
Figures & tables
Figure 1: (a) Population FA frontier: The blue shaded area represents the set of error pairs that are achievable by some linear model, and βr and βb are the error-minimizing models for groups r and b , respectively. βfair is the error-equalizing model, which falls between βr and βb in the group-balanced case. The FA frontier corresponds to the purple region along the boundary of the feasible set of error pairs. (b) For any λ∈[0,1] , βλ is the first point of tangency between the line λx+(1−λ)y=c and the FA frontier as we increase c>0 . This point moves along the frontier from βr to βb as λ ranges from 1→0 .
Figure 2: (a) Finite-sample estimation: The error pair corresponding to the empirical estimator βλ lies on the line λx+(1−λ)y=c′ , where c′−c is the welfare loss from estimation. (b) Asymmetric groupwise impact: The displacement from βλ to βλ decomposes into a vertical change in the blue-group error and a horizontal change in the red-group error; their unequal magnitudes show that the estimator affects the two groups asymmetrically.
Figure 3: Group-Balanced vs. Group-Skewed. To avoid cluttering the figure, we label points by their corresponding predictors; for example, fr denotes the point (Rr(fr),Rb(fr)) .
Figure 4: Illustration of FA frontier, parametrized by λ , and its empirical version.
Figure 5: Finite sample contraction of the FA frontier. We plot the population frontier parameterized by λ , sweeping λ on a uniform grid of 50 points in [0,1] . For each λ , we run 100 Monte Carlo repetitions; in each iteration, we draw data Sg={(Xg(i),Yg(i))}i=1ng from the group- g Gaussian linear model with σr2=σb2=1 , build the estimators β~λ,βλ , and calculate the corresponding risk pair (Rr,Rb) for each estimator. We plot the mean empirical frontiers across repetitions and depict the empirical contraction for the choice of λ=0.5 for two regimes: (a) Equal sample sizes: nr=nb=30,d=15,ρr=1,ρb=2.5 , (b) Equal covariance: nr=50,nb=30,d=15,ρr=ρb=1.75 .
Figure 6: Effective frontier position and groupwise sample allocation. Panel (a) plots the effective λ induced by the known- and unknown-covariance estimators. The gray solid line denotes the identity map λeff=λ . Finite sample estimation errors compress the implemented tradeoff toward the interior of the population frontier. Panel (b) studies groupwise sample allocation in the known-covariance case. The horizontal axis is the red-group sample share pr=nr/(nr+nb) and the vertical axis is the λ -weighted excess risk. The empirical risk curve closely aligns with the theoretical rate. Panel (c) studies the unknown-covariance setting. As groupwise heterogeneity ∥βr−βb∥ increases, excess risk rises and the empirical minimizer shifts toward a more balanced allocation. This reflects the impact of the additional bias term which results from the estimation of the groupwise covariance matrices.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 7: Illustration of the four cases used to establish that every feasible risk pair outside of the Pareto frontier is FA dominated, as defined in the proof of Lemma 8 .
Algorithmic fairness studies how automated decisions distribute errors, opportunities, and harms across groups, and how to measure and reduce disparities.
Exact demographic parity requires the same prediction distribution across sensitive groups. In regression, this can be too restrictive and reduce predictive accuracy. We instead bound every pairwise Wasserstein distance between group-specific prediction distributions by a chosen tolerance, allowing the groups to differ while keeping fairness tunable. On the real line, the prediction and constrained transport problems have the same infimum. If the transport problem attains this value and suitable Monge maps exist, a deterministic transport-form predictor realizes it. Under a standard one-dimensional condition, the problem becomes a bounded quantile optimization that is convex when the conditional expected loss is convex in prediction. Under squared loss with two positively weighted groups, the W1, W2, and W∞ constraints yield soft-thresholding, shrinkage, and clipping. Under the stated conditions, we establish rates for the known-cost plug-in estimator. When the cost is unavailable, we describe an observed-loss computational proxy. Synthetic and California 2018 ACS studies illustrate the tunable fairness-accuracy trade-off and distinguish calibration feasibility from held-out fairness and accuracy.
This paper provides identification results to characterize a fairness-accuracy (FA) frontier, and statistical inference tools to test hypotheses and build a confidence set for the FA-frontier, when outcomes are observed only for selected individuals. When the selection process is unrestricted but loss is measured in specific ways, we provide a characterization of the sharp identification region of the FA-frontier. When the observed distribution rules out frontier membership for a binary status quo algorithm, we construct a single alternative algorithm that improves both groups' accuracy without worsening fairness, uniformly over all admissible distributions of missing labels. For any loss functions, under selection on observables and strict overlap assumptions, we obtain point identification and propose a debiased machine learning estimator, derive its asymptotic distribution, and show how this can be used to carry out inference for the FA-frontier.
We revisit the foundations of fairness and its interplay with utility and efficiency in settings where the training data contain richer labels, such as individual types, rankings, or risk estimates, rather than just binary outcomes. In this context, we propose algorithms that achieve stronger notions of evidence-based fairness than are possible in standard supervised learning. Our methods support classification and ranking techniques that preserve accurate subpopulation classification rates, as suggested by the underlying data distributions, across a broad class of classification rules and downstream applications. Furthermore, our predictors enable loss minimization, whether aimed at maximizing utility or in the service of fair treatment. Complementing our algorithmic contributions, we present impossibility results demonstrating that simultaneously achieving accurate classification rates and optimal loss minimization is, in some cases, computationally infeasible. Unlike prior impossibility results, our notions are not inherently in conflict and are simultaneously satisfied by the Bayes-optimal predictor. Furthermore, we show that each notion can be satisfied individually via efficient learning. Our separation thus stems from the computational hardness of learning a sufficiently good approximation of the Bayes-optimal predictor. These computational impossibilities present a choice between two natural and attainable notions of accuracy that could both be motivated by fairness.