Identification and Inference for Algorithmic Frontiers with Selective Labels

Identification and Inference for Algorithmic Frontiers with Selective Labels

Introduction

Over the last decade, algorithms have come to play an increasingly prevalent role in everyday life, often by supporting high-stake decisions through predictions of quantities such as re-offense risk, repayment likelihood, and health care needs. These predictions enter institutional decision processes that determine who is detained or released, who is granted credit, and which patients receive outreach and care-management interventions. The increasing reliance on algorithms has prompted the emergence of a set of regulatory and oversight processes, known as AI governance, that rule the design, deployment, documentation, and monitoring of AI systems, including, in some settings, restrictions on the use of protected attributes as model inputs. A distinctive feature of these regimes is their evidentiary orientation: for high-risk AI systems, the EU AI Act requires technical documentation, logging capabilities, and appropriate accuracy and robustness over the lifecycle eu_ai_act, while related governance proposals emphasize dataset documentation, model reporting, and internal auditing gebru_etal_2021,mitchell_etal_2019,raji_etal_2020.

This paper extends the research agenda set out in liu:mol25v2 to provide a toolkit for nonparametric estimation of and statistical inference on the fairness-accuracy trade-off that characterizes algorithms. Fairness and accuracy evaluations play a central role in governance, as they determine both the validity of model-supported decisions and whether those decisions impose disproportionate harms on legally protected groups.\footnote{Algorithms may exhibit systematic differences in performance across legally protected groups, both in predictive accuracy and in the decisions they induce ang:lar:mat:kir16, arn:dob:hul21, obe:pow:vog:mul19, cow:tuc20,ber:jei:jab:kea:rot21. Yet, improving parity in expected losses often requires sacrificing accuracy for at least one group, and conversely increasing accuracy for one group may worsen disparities.} At the same time, governance questions are rarely about a single fixed model. In public oversight and non-discrimination doctrine, the relevant question is often whether a challenged procedure can be replaced by an alternative that achieves comparable accuracy with less adverse impact, shifting attention from a single algorithm to a potentially large class of admissible decision rules, e.g., those obtained under constraints on inputs, model classes, or the use of sensitive attributes. Regulators and oversight bodies are called to adjudicate (i) whether a deployed rule is Pareto efficient, (ii) whether design restrictions enable less discriminatory alternatives (LDAs) with comparable accuracy, and (iii) whether such LDAs exist within an admissible class of decision rules.\footnote{For example, US employment discrimination law prohibits selection procedures that cause disparate impact unless the employer demonstrates they are “job related for the position in question and consistent with business necessity.” Even then the practice is unlawful if an alternative practice would serve the employer's legitimate interests with less discriminatory impact civil_rights_act_1991.} As in liu:mol25v2, we build on the theoretical framework put forward by \citet*[LLMO henceforth]{lia:lu:mu:oku24}, which in our view is well-suited to formalize these questions because it characterizes a fairness-accuracy (FA) frontier under broad preferences over group-specific expected losses as well as the implications of banning attributes as inputs to the algorithms.

Our first innovation relative to liu:mol25v2's groundwork is to allow for accuracy and fairness of an algorithm to be assessed through two different loss functions, thereby aligning our treatment with the literature in computer science corbettdavies2017cost,menon2018cost,kim2020fact,gillis2024lda. We show that the support function of a convex feasible set $\mathcal{E}\subset{\mathbb R}^3$ of expected accuracy losses for the two groups and the difference in expected fairness losses between the groups plays a crucial role in characterizing the FA-frontier and carrying out inference.\footnote{In liu:mol25v2's analysis and \citetalias{lia:lu:mu:oku24}'s main text, the same loss function is used to measure fairness and accuracy, so that the feasible set $\mathcal{E}$ is in ${\mathbb R}^2$. liu:mol25v2 propose to use the support function of $\mathcal{E}\subset{\mathbb R}^2$ as the unifying tool for statistical inference.} We extend the results in \citetalias{lia:lu:mu:oku24}'s Appendix O by providing a simple and testable necessary and sufficient condition under which the FA-frontier coincides with the Pareto frontier. When this condition is not satisfied, a policymaker who values fairness may choose to deploy an algorithm that is Pareto dominated in accuracy loss, to ameliorate its performance in fairness loss.

Our second innovation addresses the reality that in many high-stakes settings, outcomes are observed only for selected individuals: pretrial misconduct (or lack thereof) is observed only if bail is granted; repayment behavior is observed only when credit is extended; certain health outcomes are observed only for patients who receive treatment or remain under follow-up within a system; etc. Hence, instead of observing the outcome vector of interest $Y^*$, one observes $\ZY^*$, where $Z\in\{0,1\}$ indicates observability. This selective labels problem creates challenges for governance compliance similar to the ones long recognized in the vast econometrics literature on selectively observed data heckman_1979,manski_1989. Accuracy metrics computed using only observed outcomes may misrepresent true performance, potentially overstating accuracy where it matters most (e.g., if those denied bail would not have re-offended). Hence, assessments of whether a system achieves “appropriate levels of accuracy” eu_ai_act or whether LDAs exist civil_rights_act_1991 may be incorrect and required documentation may systematically exclude the most policy-relevant counterfactual outcomes.

When classification loss is used to measure accuracy and statistical parity is used to measure fairness menon2018cost, and no restrictions are imposed on the selection process, we characterize the sharp identification region for the FA-frontier in the spirit of manski_1989 mol20,can:ill:velez26. Doing so is challenging because the FA-frontier is ultimately about algorithms: it equals the set of expected losses $\varepsilon(a)\in\mathcal{E}$ associated with algorithms $a\in\mathcal{A}(\mathcal{X})$ (measurable functions mapping covariates $X\in\mathcal{X}$ to $[0,1]$) such that no other algorithm $\tilde{a}\in\mathcal{A}(\mathcal{X})$ yields expected losses $\varepsilon(\tilde{a})$ that FA-dominate $\varepsilon(a)$ in a sense made precise in Definition (ref). When labels are selectively observed, both $\varepsilon(a)$ and $\mathcal{E}$ are partially but not point identified. Hence, to pass judgment on whether algorithm $a$ yields expected losses $\varepsilon(a)$ on the frontier, care needs to be taken to couple the same candidate distribution for the missing labels in constructing both $\varepsilon(a)$ and $\mathcal{E}$, and then assess membership across all admissible distributions for the missing labels. We reduce this daunting task to solving a finite dimensional optimization problem.

When the selection process is restricted by a missing-at-random (MAR) assumption, where conditional on attributes, outcome observability does not convey additional information on $Y^*$, we obtain point identification of the FA-frontier. For any loss function, we provide a debiased machine learning (DML) estimator for the FA-frontier based on inverse probability weighting. Our DML approach is particularly appropriate for governance contexts, where high-dimensional administrative data enable flexible nonparametric modeling of selection and formal inference tools are needed for legally defensible determinations. While ideas transfer from the program evaluation and high-dimensional inference literature CHKSS, we extend the methods to carry out inference on a new set-valued estimand, the FA-frontier. We derive the asymptotic distribution of our estimator and test statistics building on liu:mol25v2,sem23,cha:che:mol:sch18,ChernozhukovDML,ber:mol08, and fan:san19, provide inverse-probability weighting correction in the DML estimator, and asymptotically valid confidence sets for the FA frontier and tests for LDA existence.

Accompanying software implementing both the MAR-based and partial identification approaches is under development, along with empirical applications of our methods.

Related Literature. A large literature in computer science, statistics, and economics studies algorithmic fairness; see cho:rot18, bar:har:nar23, and Corbett24 for overviews. Much of this work treats fairness as a constraint or regularizer in an objective that prioritizes predictive performance dwork12, ber:hei:jab:jos:kea:mor:jam:nee:roth17, or studies impossibility results and trade-offs among fairness criteria kleinberg2016inherent. A related literature computes fairness-accuracy Pareto frontiers or ranges of disparities for specific model classes, typically as an optimization or auditing exercise rather than as a problem of statistical inference wei:nie21, lit:wey:all22, cos:ram:cho21. When labels are perfectly observed, aue:lia:tab:oku24 provide a sample-splitting based test for LDA existence, and fal:jor:uli26 study minimax-optimality of the sample analog of a Pareto-optimal linear rule and propose a uniform high-probability bound on its empirical error.

Within the algorithmic fairness literature, other work has focused on selective labels lak:kle:les:lud:mul17, kle:lak:les:lud:mul17, ram:cos:ken25, kha:tam:yao. ram:cos:ken25 develop a general framework for robust evaluation and design of predictive algorithms under selective labels and unobserved confounding, delivering bounds for performance measures under alternative restrictions on the selection process. We view their contribution as addressing a distinct question from ours: how to evaluate predictive performance in the presence of counterfactual outcomes. We focus instead on identification and inference for the fairness-accuracy trade-off of group losses across all feasible algorithms using a given information set, and on hypothesis tests and confidence statements about frontier properties such as LDA existence that directly map to governance questions and design restrictions.

Outline. Section (ref) lays out notation and derives the FA-frontier extending \citetalias{lia:lu:mu:oku24} and liu:mol25v2. Section (ref) formalizes the selective labels problem, derives the sharp identification region for the FA-frontier for specific loss functions and unrestricted selection process, and obtains point identification under a MAR assumption for any loss function. Section (ref) puts forward our DML estimator and derives its asymptotic distribution. Section (ref) proposes a test for equality between the Pareto and FA-frontier. It then puts forward our test for existence of an LDA in the presence of selectively observed labels and derives its asymptotic distribution, building on liu:mol25v2. Section (ref) concludes. Our main proofs are in Appendix (ref); Appendix (ref) reports auxiliary results.

Setup

Let a population of individuals be described by an outcome vector $Y^*\in\mathcal{Y}\subset{\mathbb R}^{d_Y}$, a binary group identity $G\in\{r,b\}$ (red or blue), and a vector of covariates $X\in\mathcal{X}\subset\mathbb{R}^{d_X}$. For example, one component of $Y^*$ may denote an individual's number of active chronic illnesses in the subsequent year and the other component the cost of care; $G$ may denote the individual's race, and $X$ may include age, gender, biomarkers, comorbidity, and medication variables. As in liu:mol25v2, we leave the relation between $G$ and $X$ unspecified, but require $G$ not to be a deterministic function of $X$. Each individual receives a binary decision $D\in\{0,1\}$, e.g., whether they are automatically enrolled in a high-risk care management program; or granted bail; or granted or denied a loan (while we assume $G$ and $D$ to be binary, the results can be extend to multiple groups and multiple decisions). An algorithm $a:\mathcal{X} \mapsto [0,1]$ assigns a probability distribution to $D$ conditional on $X$; e.g., the algorithm assigns each patient a health risk score in $[0,1]$; or a recidivism probability; or a repayment probability. For simplicity, we take $a(X)$ to be the only input to the decision, and hence $D\sim a(X)$. We let $\mathcal A(\mathcal{X})$ denote the set of all (measurable) algorithms that map from the input space $\mathcal{X}$ to a probability distribution over $D$. Extending the framework in liu:mol25v2, we let $\ell^A:\{0,1\}\times\mathcal{Y}\mapsto\mathbb R$ be a loss function used to measure the accuracy of an algorithm for an individual with outcome $y\in\mathcal{Y}$, and $\ell^F:\{0,1\}\times\mathcal{Y}\mapsto\mathbb R$ a loss function used to measure the algorithm's fairness. For example, one could use classification error to measure accuracy ($\ell^A(d,y)=\mathds{1}(d\neq y_1)$), which in a health care example returns the value $1$ if the algorithm mistakenly enrolls a healthy person in the high-risk care program or fails to enroll someone who is very sick. And one could use statistical parity to measure fairness ($\ell^F(d,y)=d$), hence judging an algorithm more fair if the proportion of either group receiving the two decisions is closer.

This paper is concerned with the case where instead of observing $Y^*$, we observe $Y=\ZY^*$, where $Z \in \{0,1\}$ is an indicator variable that records when the outcome of interest $Y^*$ is observed in the testing data. In other words, we allow for selectively observed labels. Before analyzing this problem, however, we provide a tractable characterization of the FA-frontier, under the assumption that $(Y^*,X,G,Z)\sim\mathbb{P}^*$ is observed, when the loss function used to measure accuracy differs from that used to measure fairness. In doing so, we extend the analysis in Appendix O.1 of \citetalias{lia:lu:mu:oku24}. Armed with our novel characterization, we then study what can be learned about the FA-frontier and how can valid statistical inference be carried out, when in fact only the selectively observed labels $Y$ are available.

The Fairness-Accuracy Frontier

We denote $\mu_g \equiv \mathbb{P}^*(G=g)$ the population proportion of group $g \in \{r,b\}$ and, for $d \in \{0,1\}$, the (unobserved) ideal labels associated with loss function $\iota\in\{A,F\}$ by

We denote the conditional expectation of $L_d^{g,\iota}$ taken with respect to $\mathbb{P}^*(Y^*,G|X)$ by

To make sure that the ideal labels are well-defined, we assume:

For each $a \in \mathcal{A}$ and $g \in \{r,b\}$, define the group-wise expected loss associated with loss function $\ell^\iota, \iota \in \{A,F\}$, when $D\sim a(X)$ as:

\citetalias{lia:lu:mu:oku24} (Appendix O.1) derive the FA-frontier and study its properties when the loss function used to measure accuracy differs from that used to measure fairness, which is the framework used in this paper. Here we adapt their definitions to our notation.\footnote{They measure accuracy with $\ell: \{0,1\} \times \mathcal{Y} \to {\mathbb R}$ (our $\ell^A$) and fairness with $\tilde{\ell}: \{0,1\} \times \mathcal{Y} \to {\mathbb R}$ (our $\ell^F$).} They work in ${\mathbb R}^2$ with a feasible set defined with respect to the accuracy loss:

\citetalias{lia:lu:mu:oku24} measure the unfairness of an algorithm $a$ through $|f(a)|$, with $f:\mathcal A\to{\mathbb R}$ a linear functional. Their framework includes as a special case $f(a) = e_r^F(a)-e_b^F(a)$, the disparity in expected fairness loss between groups, and for simplicity we specialize our discussion to that case. For each pair of expected accuracy losses $c = (c_r, c_b) \in \mathcal{E}^A$, define the minimal achievable unfairness as

Given the group-wise expected losses induced by algorithm $a\in\mathcal A$ for $\iota\in\{A,F\}$ in (ref), we instead propose to work with the feasible set for $\left\{\left(e^A_r(a),e^A_b(a),e^F_r(a)-e^F_b(a)\right):a\in\mathcal A\right\}$, where we explicitly include a coordinate measuring the difference in expected fairness loss for the two groups. Doing so allows us to characterize the properties of the FA frontier, extending \citetalias{lia:lu:mu:oku24}'s results, and to provide a representation of it that is amenable to estimation and inference, even in the presence of selectively observed data.

To simplify notation, we omit the dependence of $\mathcal{E}$ on $(\mathbb{P}^*,\mathcal A)$. In Lemma (ref), we show that under Assumptions (ref)-(ref), $\mathcal{E}$ is non-empty, compact, and convex. Definition (ref) leads to an alternative formulation of FA-dominance and to an FA-frontier in ${\mathbb R}^3$, as follows:\footnote{aue:lia:tab:oku24 use a similar definition of dominance.}

We also define the Pareto frontier, which ignores considerations of fairness:

and the points in ${\mathbb R}^3$ that minimize, respectively, $e_r^A$, $e_b^A$, and $|e_r^F-e_b^F|$:

In Appendix (ref) we show that the shape of our FA-frontier $\mathcal{F}$ depends on the position of $\mathcal{E}$, $\mathcal{PF}$, $R$ and $B$ relative to the hyperplane $\{\varepsilon_3=0\}=\{e_r^F=e_b^F\}$. Figure (ref) illustrates several examples. In the next section, we establish that our FA-frontier and \citetalias{lia:lu:mu:oku24}'s FA-frontier coincide in what we argue is the only way that matters, and we provide a characterization of $\mathcal{F}$ that does not depend on the position of $\mathcal{E}$, $\mathcal{PF}$, $R$ and $B$.

Support Function-Based Characterization of the FA-Frontier

To begin, we characterize liu:mol25v2 the support function of $\mathcal{E}$, denoted $h_\mathcal{E}(q)$ for $q$ a direction vector in $\mathbb{S}^2 \equiv \{q\in{\mathbb R}^3:\|q\|=1\}$. This functional turns out to be crucial for all our results. We assume:

Eq. (ref) implies that $\mathcal{S}_\mathcal{E}(q)\equiv\{\varepsilon\in\mathcal{E}:q^\intercal\varepsilon=h_\mathcal{E}(q)\}$, the support set of $\mathcal{E}$ in direction $q\in\mathbb{S}^2$, equals the singleton $\nabla_qh_{\mathcal{E}}(q)$ sch93. It yields that

The next corollary, proven in liu:mol25v2, characterizes precisely which algorithms yield expected losses on the boundary of $\mathcal{E}$:

Corollary (ref) echos the generalized Neyman-Pearson Lemma leh:rom08.\footnote{ To apply that theorem, in its notation set $m=1,\,c_1=0,\,\mu=\mathbb{P}$, and let $f_1(x)=0$ for all $x\in\mathcal{X}$ and $f_2(x)=q^\intercal\Delta\boldsymbol{\theta}(x)$. The critical functions $\phi$ are our algorithms $a\in\mathcal{A}(\mathcal{X})$.} One of its important consequences is that no algorithm such that $a(X)\in(0,1)$ for a set of $X$ of positive probability can yield group risks on $\partial\mathcal{E}$.

As the goal of this section is to characterize $\mathcal{F}$, given $\varepsilon^*=(\varepsilon_1^*,\varepsilon_2^*,\varepsilon_3^*)\in \mathcal{E}$, we define

the set of group-wise expected accuracy losses and fairness disparity $\varepsilon\in{\mathbb R}^3$---whether or not they are feasible---that are both weakly more accurate and weakly fairer than $\varepsilon^*$. In Lemma (ref), we show that the support function of $\mathcal{C}(\varepsilon^*)$ equals:

Given an algorithm $a^*\in\mathcal A$ and $\varepsilon^*\equiv(e^A_r(a^*),e^A_b(a^*),e^F_r(a^*)-e^F_b(a^*))$, we establish in Theorem (ref) that $\varepsilon^*\in\mathcal{F}$ if and only if the set $\mathcal{C}(\varepsilon^*)$, depicted in the two panels of Figure (ref) as the shaded green hyper-rectangle corresponding to two different values of $\varepsilon^*$, can be properly separated from $\mathcal{E}$ sch93. Panel (a) depicts a case where $\varepsilon^*\in\mathcal{F}$ and proper separation occurs; panel (b) depicts a case where $\varepsilon^*\notin\mathcal{F}$ and proper separation fails. We also show that $\varepsilon^*\in\mathcal{F}$ if and only if $(\varepsilon_1^*,\varepsilon_2^*)\in\mathcal{F}^A$ with $\varepsilon_1^*=e^A_r(a^*)$ and $\varepsilon_2^*=e^A_b(a^*)$, and $|\varepsilon_3^*|$ equals the minimum absolute disparity in (ref) associated with $(\varepsilon_1^*,\varepsilon_2^*)$. To do so, we define the projection $\pi: {\mathbb R}^3 \to {\mathbb R}^2$ by $\pi(x_1, x_2, x_3) = (x_1, x_2)$, and let $\pi(\mathcal{E})=\{\pi(\varepsilon):\varepsilon\in\mathcal{E}\} = \mathcal{E}^A$.

An immediate consequence of Theorem (ref) is that $\mathcal{F}$ captures as many features of the trade-off between accuracy and fairness as $\mathcal{F}^A$ does in \citetalias{lia:lu:mu:oku24}'s original contribution, while preserving convexity of the feasible set and yielding a simple characterization of the FA-frontier.\footnote{In fact, $\mathcal{F}$ yields a finer characterization than $\mathcal{F}^A$. Consider algorithms $a,a'\in\mathcal A$ such that $\varepsilon:=\varepsilon(a)=(0.5,0.5,1)$ and $\varepsilon':=\varepsilon(a')=(0.5,0.5,0)$. Then $\varepsilon'\succ_{FA}\varepsilon$ but $c'\not\succ_{FA^{\text{\tiny LLMO}}} c$ for $c=(\varepsilon_1,\varepsilon_2)$ and $c'=(\varepsilon_1',\varepsilon_2')$.} Indeed, using the equivalence $\ref{thm:FequivLLMO_e_in_sF}\Leftrightarrow\ref{thm:FequivLLMO_support}$ in Theorem (ref), similarly to liu:mol25v2, we have

When the same loss function is used to measure accuracy and fairness, as in \citetalias{lia:lu:mu:oku24}'s main text and in liu:mol25v2, it is simple to characterize when the FA-frontier coincides with the Pareto frontier in (ref).\footnote{In that case, $\ell^A=\ell^F$ and $e_g^A=e_g^F,\,g\in\{r,b\}$, so $\mathcal{E}$ can be defined in ${\mathbb R}^2$ and \citetalias{lia:lu:mu:oku24} show that the Pareto and the FA frontiers coincide if and only if $R$ and $B$, defined in (ref), lie on opposite sides of the $45^o$ line.} When different loss functions are used, such characterization is harder to obtain, and \citetalias{lia:lu:mu:oku24} provide only a sufficient condition for it. Working with the feasible set $\mathcal{E}\subset{\mathbb R}^3$ and its support function, we are able to provide a simple, necessary and sufficient, testable condition under which $\mathcal{PF}=\mathcal{F}$. The characterization is valuable because when $\mathcal{F}$ does not coincide with $\mathcal{PF}$, the trade-off between fairness and accuracy becomes substantial: a policymaker who values fairness may choose to deploy an algorithm that is Pareto dominated in accuracy loss, to ameliorate its performance relative to fairness loss. To derive the result, it is useful to distinguish between cases in which $\mathcal{E}$ has kinks, and cases where it does not, through the following condition.

Assumption (ref) is a necessary and sufficient condition under which $\mathcal{E}$ has no kinks (see Supplemental Appendix B.2.3 in bon:mag:mau12, bon:mag:mau12 and Remark 3.3 in liu:mol25v2, liu:mol25v2). It yields injectivity of the support map of $\mathcal{E}$, $\mathcal{S}_\mathcal{E}(q) = \arg \max_{\varepsilon \in \mathcal{E}} q^\intercal \varepsilon$ (see Theorem (ref) and the discussion following it).

The next result characterizes when $\mathcal{PF}$ and $\mathcal{F}$ are exactly the same.

Intuitively, $\mathcal{PF}=\mathcal{F}$ when every point on the FA-frontier is Pareto-optimal. When each point on the boundary of $\mathcal{E}$ has a unique supporting direction (which is guaranteed by Assumption (ref)), this happens if and only if $\mathcal{PF}\subset\{\varepsilon_3=0\}=\{\varepsilon:e_r^F=e_b^F\}$; in this case, all points along the Pareto frontier are fair and there is no conflict between improving fairness and improving accuracy. On the other hand, when $\mathcal{E}$ has kinks, one may have $\mathcal{PF}=\mathcal{F}$ even though $\mathcal{PF}\nsubseteq\{\varepsilon_3=0\}$. The complexity of the geometry of $\mathcal{F}$ in relation to the geometry of $\mathcal{E}$ and the usefulness of our Theorem (ref) are illustrated in Figure (ref). If $\mathcal{E}$ has no kinks and lies completely to one side of the hyperplane $\{\varepsilon_3=0\}$ (Panel (a), where $\mathcal{E}\subset\{\varepsilon_3>0\}=\{e_r^F>e_b^F\}$) or $R$ and $B$ lie on opposite sides of that hyperplane (Panel (c)), then $\mathcal{PF}\subsetneq\mathcal{F}$ since $\mathcal{PF} \not\subset \{\varepsilon_3=0\}$. On the other hand, if $\mathcal{E}$ has kinks properly facing the origin, then it can be that $\mathcal{PF}=\mathcal{F}$ even when $\mathcal{E}$ lies completely to one side of the hyperplane $\{\varepsilon_3=0\}$ (Panel (b)). If $\mathcal{E}$ crosses the hyperplane $\{\varepsilon_3=0\}=\{e_r^F=e_b^F\}$ with $\mathcal{PF}$ fully contained in one of $\{\varepsilon_3>0\}$ or $\{\varepsilon_3<0\}$, then $\mathcal{PF}\subsetneq\mathcal{F}$ regardless of the presence or absence of kinks (Panel (d)), see Corollary (ref). If $\mathcal{E}$ has no kinks and $\mathcal{PF}\subset\{e_3=0\}$, then $\mathcal{PF}=\mathcal{F}$ (Panel (e)), yet having only $\{R,B\} \in\{e_3=0\}$ but not the entire Pareto frontier may yield $\mathcal{PF}\subsetneq\mathcal{F}$ (Panel (f)). Hence, the characterization in Theorem (ref) is particularly useful to avoid case-by-case distinctions and pre-tests.

Selectively observed Labels

Having fully characterized the FA-frontier in the idealized case when $(Y^*,X,G,Z)\sim\mathbb{P}^*$ is observed, we turn to our goal of providing identification results and inference procedures for $\mathcal{F}$ when only $(Y,X,G,Z)\sim\mathbb{P}$ is observed, with $Y=\ZY^*$ the selected labels and $Z$ a selection indicator. This problem has been studied, e.g., by lak:kle:les:lud:mul17,kle:lak:les:lud:mul17,ram:cos:ken25,kha:tam:yao. When evaluating whether algorithmic policies can improve upon human decision-making, selectively observed labels are compounded by the possibility that $Z$ is determined by a decision maker (e.g., a judge) who observes information beyond the recorded covariates made available to the algorithm. In this case, for a specific choice of loss functions, we report partial identification results. We then provide point identification results and statistical inference procedures for the case where label observability is induced by deployment of a decision rule in $\mathcal A(\mathcal{X})$, so that $Z$ is determined by an algorithm that uses only the inputs in $\mathcal{X}$.

Partial Identification of the FA-Frontier

In this section, we allow $Z$ to depend on variables unavailable to the algorithms in $\mathcal A(\mathcal{X})$. This creates substantial challenges for identification and inference, because not only the feasible set $\mathcal{E}$ is partially identified, but even for a fixed algorithm $a^*\in\mathcal A(\mathcal{X})$, the vector of expected losses $\varepsilon^*\equiv\varepsilon(a^*):=(e_r^A(a^*),e_b^A(a^*),e_r^F(a^*)-e_b^F(a^*))$ is also only partially identified. Consequently, extra care needs to be taken, when characterizing what can be learned about $\mathcal{F}$ in (ref), to correctly couple the possible values of $\mathcal{E}$ and $\varepsilon^*$ associated with each candidate distribution for the unobserved labels.

To make progress on this task, we specialize our analysis to the case where $Y^*$ is a binary scalar variable, the accuracy loss measures classification error, $\ell^A(d,y) = \mathds{1}\{d \neq y\}$, and the fairness loss measures statistical parity, $\ell^F(d,y) = \mathds{1}\{d=1\}$. Write $Y=\ZY^*$ for the observed binary outcome. In this case the fairness coordinate depends only on the decision rule and the observable distribution of $(X,G)$, so lack of point identification comes entirely from the selectively observed outcomes entering the two accuracy coordinates.

Denote the unobserved conditional expectation of $Y^*$ when $Z=0$ by

and $\lambda^*(x)\equiv[\lambda_r^*(x),\lambda_b^*(x)]^\intercal$. Without restrictions on the selection process, $\lambda^*$ is unknown. As $Y^*\in\{0,1\}$, every measurable map $\lambda\equiv(\lambda_r,\lambda_b):\mathcal{X}\to[0,1]^2$ is compatible with $\mathbb{P}$, the observed law of $(Y,X,G,Z)$.\footnote{By “compatible with the observed data” we mean that it yields a law of $(Y^*,X,G,Z)$ that reproduces the observed distribution of $(Y,X,G,Z)$ and satisfies $Y=ZY^*$ almost surely.} Let $\Lambda\equiv \left \{ \lambda: \mathcal{X} \to [ 0,1]^2 \right \}$ denote this class of functions.

We next derive the sharp identification region for $h_\mathcal{E}(q)$. To do so, we need to introduce some notation. Define the observable functions

Lemma (ref) shows that the functions $\boldsymbol{\theta}_d(\cdot)$ in Definition (ref) associated with distribution $\lambda\in\Lambda$ satisfy $\boldsymbol{\theta}_0(x;\lambda)=A_0(x)+B(x)\lambda(x)$ and $\boldsymbol{\theta}_1(x;\lambda)=A_1(x)-B(x)\lambda(x)$. Hence, the feasible set associated with distribution $\lambda$ and its support function are, respectively,

Accordingly, the sharp identified set for $h_\mathcal{E}(q)$ in direction $q$ is $\{h_\mathcal{E}(q;\lambda):\lambda\in\Lambda\}$.

For a fixed algorithm $a^*$, let $A_{d,j}(x)$ denote the $j$th coordinate of $A_d(x)$, $d\in\{0,1\}$, in (ref)-(ref) and define

Then we can express $h_{\mathcal{C}(\varepsilon(a^*;\lambda))}$ in (ref) associated with $\lambda\in\Lambda$ as

We now present an assumption on the observable distribution $\mathbb{P}$ under which the margin condition (Assumption (ref)) holds for all distributions consistent with the data.

Under Assumption (ref), Theorem (ref) characterizes frontier membership for a given $\lambda$, where crucially we use the same candidate unobserved distribution $\lambda$ both in obtaining $h_\mathcal{E}(\cdot)$ and $h_{\mathcal{C}(\varepsilon^*)}(\cdot)$. Recall $\varepsilon^*(a^*;\lambda)$ denotes the vector of expected losses induced by $a^*$ under unobserved distribution $\lambda$; then $a^*$ lies on the FA-frontier under $\lambda$ if and only if

The next result shows how to check whether $a^*$ can generate expected losses on the frontier for some distribution of the unobserved labels, through a finite dimensional optimization problem that involves functionals of the observed distribution $\mathbb{P}$.

Theorem (ref) shows that once the source of partial identification is reduced to the functional $\lambda$, the search over the infinite-dimensional class $\Lambda$ collapses to a finite-dimensional criterion involving only the corner distributions $\lambda_0$ and $\lambda_1$.

Our next goal is to characterize the sharp identification region of $\mathcal{F}$ using a finite dimensional optimization problem that does not involve $a\in\mathcal{A}(\mathcal{X})$ and $\lambda\in\Lambda$. Recall $\mathcal{E}(\lambda)$ in (ref) and define the FA frontier associated with distribution $\lambda$ and the FA-frontier envelope as

For a given $q\in\widetilde{\mathbb{S}}^2$, collect all expected loss vectors achievable by an algorithm that takes the threshold form specified in Corollary (ref) for some distribution $\lambda$ and thus are the boundary points of $\mathcal{E}(\lambda)$, in the following set\footnote{The minimization in the definition of $\mathcal{M}_q$ is a sign convention that we use because the first two coordinates are losses (we could alternatively take $\arg\max_d -q^\intercal\boldsymbol{\theta}_d(x;\lambda)$ for $q\in\widetilde{\mathbb{S}}^2$).}

In Lemma (ref) we show that for every $q\in\widetilde{\mathbb{S}}^2$, the set $\mathcal{M}_q$ is nonempty, compact, and convex. In Lemma (ref) we show that its support function, $h_{\mathcal{M}_q}(v),v\in\mathbb{S}^2$, is given by

where $\kappa_0(v,q;x)$ and $\kappa_1(v,q;x)$, formally defined in (ref)-(ref), are known functions of $A_0(x),A_1(x),B(x)$. We then have the following characterization of $\mathcal{F}^\exists$:

Point Identification Under Missing at Random Assumptions

While the distribution $\mathbb{P}$ of $(Y,G,X,Z)$ is point identified by the observed data, in the absence of additional assumptions the distribution $\mathbb{P}^*$ of $(Y^*,G,X,Z)$ is not. The previous section shows that, as a consequence, the support function $h_\mathcal{E}(q)$ and $\varepsilon^*(a),\,a\in\mathcal{A}(\mathcal{X})$, are not point identified either, as the ideal labels and their conditional expectations ($\mathbf{L}_d$ and $\boldsymbol{\theta}_d(X)$, respectively) are a function of $Y^*$ and $\mathbb{P}^*$.

We leverage the fact that all algorithms in $\mathcal A(\mathcal{X})$ can only use the covariates $X$ for training (and no other unobserved variables) to argue plausibility of a selection on observables assumption that we use to point identify the distribution $\mathbb{P}^*$.

Assumption (ref) may look stronger than the typical missing at random (unconfoundedness or selection on observables) assumption, which might instead require $Y^* \perp Z | X,G$. Our approach remains valid under this weaker condition, but here we work with Assumption (ref) because it yields lighter notation and simpler expressions. We argue that, in many settings of interest, the additional requirement $G \perp Z | X$ is a natural consequence of how $Z$ is generated. Specifically, suppose that $Z=D$, where $D\in\{0,1\}$ is the binary decision an individual receives (e.g., granted or denied a loan; granted or denied bail), and that this decision is produced by a deployed decision rule in $\mathcal A(\mathcal{X})$ that takes $X$ as input and, following regulations, does not use $G$ or apply any group-dependent post-processing. Then, for all $g\in\{r,b\}$, $\mathbb{P}(D=1| X,G=g)=\mathbb{P}(D=1| X)= a(X)$, so that $G \perp Z | X$ holds. Combined with the standard selection on observables condition, $Y^* \perp Z | X,G$, this yields Assumption (ref). The more restrictive part of Assumption (ref) is therefore the requirement $Y^* \perp Z | X,G$. This condition is plausible when the assignment mechanism that determines $Z$ depends on recorded variables capturing the main drivers of both selection and outcomes, and when discretion at the decision-making stage is limited or can be accounted for. In such settings, conditioning on $(X,G)$ may reasonably approximate conditioning on the information that drives selection, so that $Z$ does not convey additional information about $Y^*$ beyond $(X,G)$. When instead the assignment process exploits unrecorded “soft information” (e.g., interviews, free text, documents, or unlogged history) or when discretion is systematically related to expected outcomes, $Y^* \perp Z | X,G$ may fail, motivating our partial identification analysis in Section (ref).

The next lemma shows that, under Assumption (ref) the support function of $\mathcal{E}$ is point identified through a standard inverse propensity weighting identity:

A Debiased Machine Learning Estimator and Its Asymptotic Distribution

The DML Estimator

Our goal is to estimate the support function $h_\mathcal{E}(q)$ using a random sample $\{(Y_i,G_i,X_i,Z_i): 1 \le i \le n \}$ drawn from the distribution $\mathbb{P}$. By Lemma (ref), $h_\mathcal{E}(q)$ is identified by (ref), which involves nuisance functions $\pi(X)$ and $\Delta \boldsymbol{\theta}(X)$ that need to be estimated in the first step. As the ideal labels $\mathbf{L}$ depend on $\boldsymbol{\mu} \equiv [\mu_r,\mu_b]^\intercal$ (see (ref)-(ref)), we also need to estimate $\boldsymbol{\mu}$. In order to build an estimator for $h_\mathcal{E}(q)$ that is locally robust to the first-step estimation error, we propose using the debiased machine learning (DML) approach. Consider the estimand

where $\boldsymbol{\eta}\equiv(\Delta \boldsymbol{\theta},\pi,\boldsymbol{\theta}_0)$ is a vector of nuisance functions and

The local effect of the first-step function $\pi$ on the original estimand $h_\mathcal{E}(q)$ in (ref) is accounted for by $ \alpha^h(q;X_i) \left(1 - \tfrac{Z_i}{\pi(X_i)}\right)$. As we show in the proof of Theorem (ref), under Assumptions (ref) and (ref) presented below, it is not necessary to account for the local effect of the first-step function $\Delta \boldsymbol{\theta}$ on $h_\mathcal{E}(q)$. Finally, we note that the estimand in (ref) is based on $\mathbf{L}$, which by (ref) relies on the population means $\mu_g, g\in\{r,b\}$.

Following the DML approach ChernozhukovDML,velez2024asymptotic, we first randomly split the indices $[n]\equiv\{1,\ldots,n\}$ into $K$ equal-sized folds $\mathcal{I}_k$, i.e., $\cup_{k=1}^K \mathcal{I}_k = [n]$. We denote by $n_k$ the size of $\mathcal{I}_k$.\footnote{When $n$ is not divisible by $K$, the number of observations in some folds will be $\lfloor n/K \rfloor$ while in others $\lfloor n/K \rfloor + 1$, where $\lfloor n/K \rfloor$ is the greatest integer less than or equal to $n/K$.} We then estimate $\widehat{\boldsymbol{\eta}}(X_i)$ as $\widehat{\boldsymbol{\eta}}_k(X_i)$ for $i \in \mathcal{I}_k$ and $k=1,\ldots,K$, where $\widehat{\boldsymbol{\eta}}_k(\cdot)$ is estimated using all data except the portion with indices in fold $\mathcal{I}_k$. Finally, the first-stage estimators for the nuisance functions are used to form a second-stage estimator for $h_\mathcal{E}(q)$ based on the expression of the estimand defined in (ref):

where $\widehat\mathbf{L}$ is defined as in (ref)-(ref) with $\mu_g$ replaced by $\widehat{\mu}_g \equiv n^{-1} \sum_{i=1}^n \mathds{1}\{G_i=g\}$.

We also propose a DML estimator for $\varepsilon^* = \varepsilon(a^*) \in \mathcal{E}$. By (ref) in Lemma (ref) and Definition 3, we can write $\varepsilon^*= \mathbb{E}[ \xi_i(a^*;\mathbf{L},\boldsymbol{\eta})]$, where for a given algorithm $a\in\mathcal A$,

and again the local effect of the first-step function $\pi$ on the original estimand $\varepsilon^*$ is accounted for by $\boldsymbol{\alpha}^e(X_i) \big(1 - \tfrac{Z_i}{{\pi}(X_i)}\big)$. Using this notation, we propose to estimate $\varepsilon^*$ by

where $\widehat{\mathbf{L}}$ stacks the feasible labels and $\{\widehat{\boldsymbol{\eta}}_k\}_{k=1}^K$ are estimators for the nuisance functions using cross-fitting, as we described above.

Asymptotic Distribution of the DML Estimator

For the nuisance functions' estimation error to be asymptotically negligible for the DML estimator, the nuisance estimators must satisfy suitable regularity conditions set out next.

A sufficient condition for Assumption (ref) is given in liu:mol25v2, where a partially linear structure is assumed for $\Delta\boldsymbol{\theta}$.

Let $\mathfrak{F}_k \equiv \sigma( (Y_i,G_i,X_i,Z_i): i \notin \mathcal{I}_k)$ be the $\sigma$-algebra generated by the data used for constructing the estimator $\widehat{\boldsymbol{\eta}}_k$ for the nuisance ${\boldsymbol{\eta}} \equiv (\Delta \boldsymbol{\theta},\pi,\boldsymbol{\theta}_0)$. Let $\widehat{\boldsymbol{\mu}}_k$ be an estimator for $\boldsymbol{\mu} \equiv [\mu_r,\mu_b]^\intercal$ that uses only the data outside fold $\mathcal{I}_k$ (similar to how we define $\widehat{\boldsymbol{\eta}}_k$): $$\widehat{\boldsymbol{\mu}}_k = \left(\tfrac{1}{n-n_k} \sum_{i \notin \mathcal{I}_k} \mathds{1}\{G_i=r\},~\tfrac{1}{n-n_k} \sum_{i \notin \mathcal{I}_k} \mathds{1}\{G_i=b\} \right)^\intercal~.$$

We assume that the estimators for $\Delta \boldsymbol{\theta}(X)$ and $\pi(X)$ share the same structure as in Assumption (ref). Furthermore, we treat $\nu(X_1)$ as a low-dimensional nonparametric component that can be estimated uniformly well over $\mathcal{X}_1$, whereas $\gamma(X_2)$ captures a high-dimensional component that can be estimated sufficiently well in the sense that its mean squared error converges to zero sufficiently fast. We assume that $\boldsymbol{\theta}_0$ can be estimated sufficiently well.

Example machine learning methods that, under suitable conditions, are $n^{1/4}$-consistent in the $L^2$-norm include $\ell_1$-penalized methods, boosting, and neural nets ChernozhukovDML.

Similarly to liu:mol25v2, our main asymptotic result shows that $\widehat{h}_{\mathcal{E}}(q;\widehat{\mathbf{L}}, \widehat{\boldsymbol{\eta}})$ converges to a Gaussian process uniformly in $q\in\mathbb{S}^2$, where the score $\zeta_i(q;\mathbf{L},\boldsymbol{\eta})$ in (ref) is the influence function that governs the part of the limit distribution of $\widehat{h}_{\mathcal{E}}(q; \widehat{\mathbf{L}},\widehat{\boldsymbol{\eta}})$ due to the uncertainty in $\widehat{\boldsymbol{\eta}}$, and the remaining part is attributed to estimating $\boldsymbol{\mu}$:

Testing Procedures

We provide test statistics and their asymptotic distribution to test whether (i) the FA-frontier coincides with the Pareto frontier; and (ii) a less discriminatory alternative to a given algorithm exists.

Testing $\mathcal{PF}=\mathcal{F}$

Theorem (ref) provides a necessary and sufficient condition for $\mathcal{PF}=\mathcal{F}$. Here we put forward an equivalent characterization based on the support function process, which is amenable to testing the null hypothesis $\mathcal{PF}=\mathcal{F}$ against the alternative $\mathcal{PF}\neq\mathcal{F}$.

Eq. (ref) translates the geometric condition $\mathcal{PF}\subset\{\varepsilon_3=0\}$ in Theorem (ref) into a criterion involving only the support function. For each Pareto-supporting direction $-q(\alpha)$, the expression inside the supremum checks whether $-q(\alpha)$ already minimizes the support value over fairness-direction tilts $\{-q(\alpha)+s u_3:s\in[-\bar s,\bar s]\}$. In the proof of Proposition (ref), we show that the derivative of this tilted support function at $s=0$ equals the fairness coordinate of the Pareto point; by convexity, $s=0$ minimizes the support value over $[-\bar s,\bar s]$ if and only if this derivative---and thus the fairness coordinate---is zero. Hence, the criterion in (ref) is zero exactly when all Pareto points have zero fairness disparity, i.e. $\mathcal{PF}\subset\{\varepsilon_3=0\}$, which is equivalent to $\mathcal{PF}=\mathcal{F}$ by Theorem (ref).

Assessing the Existence of a Less Discriminatory Alternative

When evaluating whether there exists a less discriminatory alternative (LDA) to a given algorithm, regulators and policymakers need to confront the fact that they can only rely on finite data to do so. Concretely, given an algorithm $a^*\in\mathcal{A}(\mathcal{X})$, we call another algorithm $\tilde{a} \in\mathcal{A}$ an LDA if it yields expected losses that are at least as accurate as those associated with $a^*$ for both groups, and at least as fair, with one of these inequalities strict. In terms of the FA-dominance notion and FA-frontier reported in Definition (ref), the absence of an LDA is equivalent to the fact that $a^*$ yields expected losses with

By Theorem (ref), (ref) and (ref) below are equivalent, hence we can use the latter to test the hypothesis that no LDA exists against the alternative that it does, as follows:

where $h_{\mathcal{C}(e^*)}(q)$ is defined in (ref). We refer to (ref) as the LDA hypothesis.

We propose to reject the LDA hypothesis for large values of the following test statistic:

where $\widehat{h}_\mathcal{E}^\omega$ is a weighted estimator for $h_\mathcal{E}$ defined in (ref) in Appendix (ref) and $\widehat{\varepsilon}^{\omega}$ is a weighted estimator for $\varepsilon^*$ defined in (ref) in Appendix (ref). The former uses weights $\omega_i^h = 1 - \Xi_i/2$ and the latter uses weights $\omega_i^\varepsilon = 1 + \Xi_i/2$, $i=1,\dots,n$, with $\Xi_i$ a Rademacher random variable taking values in $\{-1,1\}$ with uniform probability and independent of the sample data and of the first stage training split. The test statistic in (ref) was proposed in liu:mol25v2. The reason why it resorts to using reweighted estimators for $h_\mathcal{E}(q)$ and $\varepsilon^*$ is that under the null hypothesis that $\varepsilon(a^*)\in\mathcal{F}$, Corollary (ref) yields that there exists a direction vector $q^*\in\tilde{\mathbb{S}}$ such that $a^*(X)=\mathds{1}\{q^{*\intercal}\Delta\boldsymbol{\theta}(X)>0\},\,\mathbb{P}^*_X$-a.s. As a consequence, one can show that under Assumption (ref), for $\varepsilon^*$ a point at which $h_{\mathcal{C}(\varepsilon^*)}(q^*)$ is locally differentiable, the limit distribution of a the test statistic like the one in (ref) but with $\omega_i^h=\omega_i^e=1$ for all $i=1,\dots,n$, has a degenerate limit distribution. liu:mol25v2 show that this test statistic with degenerate limit distribution asymptotically rejects a true null with probability zero, and a false null under local ($1/\sqrt n$) alternatives motivated by practical significance criteria with probability one bla:spi22. The use of Rademacher weights regularizes the limit distribution of the test statistic, trading asymptotic size $\alpha$ for the null and local asymptotic unbiasedness at local alternatives closer to the null than $1/\sqrt n$ times the practical significance threshold, for power above nominal size instead of one just above that threshold.

Our contribution is deriving the test's asymptotic distribution as well as a valid bootstrap procedure to estimate the associated critical values, in the presence of selectively observed labels. We consider a bootstrap-based critical value $\widehat{c}_{1-\alpha}$ defined in Procedure (ref) below. To simplify notation, let $\boldsymbol{\beta} \equiv ( {h}_\mathcal{E}(q),{\varepsilon}^*) \in \ell^{\infty}(\mathbb{S}^2) \times {\mathbb R}^3$ denote the vector of population values and let $\widehat{\boldsymbol{\beta}}^\omega \equiv ( \widehat{h}_\mathcal{E}^\omega(q),\widehat{\varepsilon}^\omega) \in \ell^{\infty}(\mathbb{S}^2) \times {\mathbb R}^3$ denote the vector of their estimators. We can write $T_n^{\texttt{LDA}} = \sqrt{n} \left( \phi(\widehat{\boldsymbol{\beta}}^\omega) - \phi(\boldsymbol{\beta}) \right)$, where $\phi$ is defined in (ref) in Appendix (ref).

Let us define the LDA test by $\varphi_n^{\texttt{LDA}} = \mathds{1} \{ T_n^{\texttt{LDA}} > \widehat{c}_{1-\alpha + \kappa}+\kappa\}$ for a given significance level $\alpha \in (0,1)$, where $\kappa>0$ is an arbitrarily small positive constant. The constant $\kappa$ can be taken equal to $10^{-6}$ as in and:shi13. We can take $\kappa = 0$ when the asymptotic distribution of $T_n^{\texttt{LDA}}$ is continuous at its $(1-\alpha)$-quantile; $\kappa>0$ appears in the critical value used in the LDA test to handle the technicalities arising from possible discontinuity points of the asymptotic distribution of $T_n^{\texttt{LDA}}$.

The next result establishes the consistency of the Bayesian bootstrap outlined in Procedure (ref) and guarantees the asymptotic correct size of the proposed test $\varphi_n^{\texttt{LDA}}$.

Given Theorem (ref), we can build an asymptotically valid confidence set for $\mathcal{F}$ by test inversion, similarly to liu:mol25v2.

Conclusions

In this paper, we consider the problem of identification and inference for the FA-frontier put forward in \citetalias{lia:lu:mu:oku24}, when labels (outcomes) are selectively observed. We build on the methodology developed by liu:mol25v2, who assume away the selective labels problem to focus on deriving moment-inequality representations for the frontier. Selective labels challenge one's ability to (point) identify features of the conditional distribution of the true labels, including the FA-frontier. Naively computed accuracy metrics using only observed outcomes may misrepresent true performance, potentially overstating accuracy where it matters most and distorting conclusions on whether LDAs exist.

Under the assumption that labels are missing at random conditional on a rich set of observed covariates, we obtain point identification of the FA-frontier using inverse propensity score weighting and derive the asymptotic distribution of the test statistic that we use to characterize whether an algorithm is on the frontier. The inference method that we propose is based on a debiased machine learning estimator, which is particularly appropriate in this context, where high-dimensional administrative data enable flexible nonparametric modeling of the selection process and hence make the missing at random assumption more credible, but formal inference with valid confidence statements remains necessary for legally defensible determinations, making the use of methods that control the bias of the first-step nonparametric estimation crucial.

When the selection process is left completely unrestricted (hence, we dispense with the missing at random assumption) we provide a tractable characterization of the sharp identification region for the FA-frontier, for a specific class of loss functions. In work in progress, we derive a DML estimator and its asymptotic theory (along with valid bootstrap methods) to build a confidence set for the partially identified FA-frontier and to test the hypothesis that no LDA exists to a given algorithm.