Learning with Selectively Labeled Data from Multiple Decision-makers
Authors: Jian Chen
Zhehao Li
Xiaojie Mao
Venue: ICML 2025 poster (2025)
Keywords: Selective Labels
Causal Inference
Minimax Learning
Cost-sensitive Classification
Primary area: general_machine_learning

Abstract: We study the problem of classification with selectively labeled data, whose distribution may differ from the full population due to historical decision-making. We exploit the fact that in many applications historical decisions were made by multiple decision-makers, each with different decision rules. We analyze this setup under a principled instrumental variable (IV) framework and rigorously study the identification of classification risk. We establish conditions for the exact identification of classification risk and derive tight partial identification bounds when exact identification fails. We further propose a unified cost-sensitive learning (UCL) approach to learn classifiers robust to selection bias in both identification settings. Finally, we theoretically and numerically validate the efficacy of our proposed method.

Learning with Selectively Labeled Data from Multiple Decision-makers
Jian Chen
Zhehao Li
Xiaojie Mao"
1
Abstract
lation to which decisions will be applied, creating classic selection bias issue. As a result, models trained on se- lectively labeled data may perform well on the observed subjects but fail to generalize to the full population when de- ployed in real-world settings. This challenge becomes even more critical when historical decisions relied on unobserv- able factors not captured in the available data, is common when human decision- (ecision-makers are involved. In such cases, the labeled data can differ substantially from the broader population due to unknown factors, further complicating the development of reliable ML models.
We study the problem of classification with selec- tively labeled data, whose distribution may differ from the full population due to historical decision- making. We exploit the fact that in many appli- cations historical decisions were made by multi- ple decision makieo,,,,,,,, each with different decision rules. We analyze this setup under principled instrumental variable (IV) framework and rigor- ously study the identification of classification risk. We establish conditions for the exact identification of classification risk and derive tight partial iden- tification bounds when exact identification fails. We further propose a unified cost-sensitive learn- ing (UCL) approach to learn classifiers robust selection bias in both identification settings. Fi- nally, we theoretically and numerically validate the efficacy of our proposed method.
Our paper addresses the selective label problem by lever- aging the heterogeneity of decision-making processes in many real-world applications. Specifically, we consider set- tings where decisions are made by multiple decision-maker with distinct decision rules, potentially leading different outcomes for the same subject. Furthermore, since decision- makers often evaluate similar pools of subjects, each subject can be viewed as being quasi-randomly assigned to a spe- cific decision-maker This structure offers a way to mitigate the selective label problem: a subject who remains unla- beled under one decision-maker might have been labeled if assigned to another. For instance, judicial decisions typically made by different judges who vary in their leniency when deciding whether to release the same defendant. The heterogeneous decision-maker framework has also been ex- plored in prior research to address selection bias in model evaluation (e.g., Lakkaraju et al., 2017; Kleinberg et al., 2018; Rambachan et al., 2021; Amoll et al., 2022).
1. Introduction
The problem of selective labels is common in many decision- making applications involving human subjects. In these applications, each individual receives a certain decision, which in turn determines whether the individual's outcome label is observed. For example, in judicial bail, the label of interest is whether a defendant returns to court without committing another crime if released. However, this label cannot be observed if bail is denied. Similarly, in lending, the default status of a loan applicant cannot be observed if the loan is not approved. In hiring, a candidate's 's job performance cannot be observed if the candidate is not hired.
Main Contributions In this paper, we leverage the instru- mental variable framework in causal inference to formalize the selective label problem with multiple heterogeneous decision-makers. This enables principled identification anal- yses to characterize the identifiability of classification risks from the observed data, revealing fundamental power and limits of the multiple decision-makee structure in tackling the selective label problem. This provides valuable insights beyond the heuristic approaches in the prior literature. More- over. unlike the existing selective label literature that pri- marily focus on evaluating fixed models, our work focuses on learning a robust classification model from the selective label data.
The selective label problem presents significant challenges for developing effective machine learning (ML) algorithms to support decision
(Lakkaraju et al., 2017: Klein- berg et al., 2018; De-Arteage, et al., 2021). Specifically, labeled data may not be representative of the broader popu-
"Alphabetical Order. 'School of Economics and Management, Tsinghua University, Beijing, China. Correspondence to: Xiaojie Mao <maoxj @ www..t.ingu.a.eee.cooooo .du......dd.....................
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Specifically, we describe the problem setup and the IV

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Then in Section 4 we establish identification conditions for the classification risk from the observed data with multiple cocision-makenn and highlight the identification assumptions are overly strong. In Sec- tion 5, we further derive tight bounds on the plausible value of classification risk when the exact identification fails. In Section 6, we propose a Unified Cost-sensitive Learning (UCL) algorithm to learn classifiers robust to selection bias in both identification settings. We briefly demonstrate the superior performance of our proposed method through nu- merical experiments in Section 7, with the comprehensive experiments in Appendix E. We defer theoretical guarantees for our method to Appendix D.
framework in Section 3.
learning (Kilbertus et al., 2020; Wei, 2021; Yang et al., 2022), where the decision-maker can control whether to collect the true label of each unit by making appropriate decisions. The goal is to effectively balance the exploration and exploitation. In contrast, our work considers an offine setting where the dataset is already given and the decision- maker can no longer collect labels through exploration.
Identification Analysis with IV This work builds on the instrumental variables (IV) literature in statisties and econometrics. IV methods are widely used to address un- measured confounding in causal inference (Angrist & Pis- chke, 2009; Angrist & Imbens, 1995; Angrist et al., 1996). Several empirical studies, such as Kling (2006) and Mueller- Smith (2015), have already leveraged heterogeneity among decision-makers e.g., j.g.e assignment-as as an IV. How- ever, these analyses typically rely on parametric linear mod- els, whereas our identification strategy is fully nonparamet- ric and does not impose parametric assumptions.
Notations Define x+ = max (ar, 03, x Ay= = min (ar y) and æ V y = max y for z, y E R. We use the symbol [N] as a shorthand for the set {1,2, ,N) and |- to denote the absolute value of number or cardinality of set.
2. Related Work
Our exact identification analysis builds on Wang & Tchet- gen (2018) and Cui & Tchetgen Tchetgen (2021), who study the identification of average treatment effects using binary- valued instruments. We extend their results to multi-valued IVs. Our partial identification results extend the classic bounds introduced by Manski (Manski, 1990; Manski & Pepper, 1998). We show that our bounds also reduce to those of Balke & Pearl (1994) in the case of a binary instru- ment and binary outcome. Furthermore, we establish the sharpness of our IV partial bounds using techniques from Kédagni & Mourifie (2017). For a broader overview of IV partial identification, see also Swanson et al. (2018).
Selective Label Problem The selective label problem arises when labels are observed only for individuals receiv- ing certain decisions. Kleinberg et al. (2018) and Lakkaraju et al. (2017) study this in recidivism prediction using jail bail data, leveraging quasi-random judge assignment and varia- tion in leniency to compare algorithmic recommendations with human decisions. By using a heuristic "contraction" method, they show that algorithms can outperform some judges in reducing recidivism. Bertsimas & (2022) extend this approach to immigration enforcement, using machine learning to assist detention decisions. They exploit quasi-random prison assignments and variation in release rates to enable credible counterfactual comparisons between strict and lenient detention practices. De-Arteaga et al. (2018; 2021) propose to leverage decision-maker con- sistency to impute the missing labels. They impute missing labels as negative when multiple fecision-makke tend to consistently reject case, assuming that consistent rejec- tion implies a negative outcome. Compared to these prior works, we use an instrumental variable framework to ana- lyze the selective label problem from a formal identification perspective. Moreover, these prior works all focus on model evaluation, while our work focuses on learning a robust classification model from selectively labeled data.
Individual Treatment Rule Learning with IV There is growing body of work on individualized treatment rule (ITR) learning, which aims to determine the optimal treat- ment for each individual based on observed features. While early literature focuses on the unconfoundedness setting (e.g., Qian & Murphy, 2011; Zhao et al., 2012: Athey & Wager, 2021), recent literature also considers robust ITR learning under unmeasured confounding. In particular, Cui & Tehetgen Tchetgen (2021) and Pu & Zhang (2021) study ITR learning with instrumental variables (IV) under point and partial identification, respectively. Both are restricted to a binary IV and a binary treatment, and Pu & Zhang (2021) additionally focus on a binary outcome. Our work differs from them in that consider multi-valued IV and multi-class outcome, aiming to learn a classifier that maps features to one label class rather than one treatment arm. Our work advances both works in several ways. Specifically, our point identification extends the identification in Cui & Tchetgen Tchetgen (2021) to a multi-valued IV. Our par- tial identification bounds extend the bounds in Pu & Zhang (2021) to a multi-valued IV and multi-class outcome. Our resulting minimax learning formulation for multi-class
Our work also connects to the literature on counterfactual evaluation under unmeasured confounding. Rambachan et al. (2022) derive IV-based partial identification bounds for evaluating the predictive performance of given risk scores and cite selective labels as an example. In contrast, we focus on learning robust classification rules under both point and partial identification (see Theorems 4.4 and 5.3).
Another line of work addresses selective labels via online
2

---

Learning with Selectively Labeled Data from Multiple Decision-makers
not observe all variables but instead only observe the data Sv {(Y, Di, X,, Z,))==1
3.1. Learning under Selective Labels
Our goal is learn a classifier : X ++ [K] that can accu- rately predict the true label Y* based on observed features pro-
Z
D
X. This classifier will aid in future decision-makes cesses through accurately predicting Y*. The effectiveness of the classifier upon deployment across the full population is evaluated using the expected risk with the zero-one loss:
Figure 1. Causal graph of selective label problem. The dashed nodes U and Y* are unobserved. The dashed line from X to Z means that Z is allowed but not required to be affected by X.
min [X
:= : [I(" * ((x))
(2)
Here I(-) is an indicator function, which equals 1 if the event inside occurs and 0 otherwise. The expectation is taken over the unknown joint distribution of Y* and X. For given classifier 1, the risk ((()) quantifies its misclassification error rate IP + t(X)).
outcome is much more complicated than that in Pu & Zhang (2021), but we give a closed-form form formulation for the inner maximization and provide a cost-sensitive learning refor- mulation. Importantly, our work also provides a unified cost-sensitive learning framework to tackle point and partial identification simultancously rather than separately.
Conventionally, one can train a classifier through empiri- cal risk minimization (ERM), i.e., minimizing an empirical approximation for the classification risk R(t)) based on the sample data, However, this challenging under selective labels since the true label Y* not fully observed. One nat- ural alternative is perform ERM the labeled subsample (subsample size denoted by Ni):
3. Problem Formulation
We address the selective label problem within a multiclass classification setting. Consider a dataset comprising N units, indexed by 1,...,N, N. For each unit let Y E [K] denote the true label of interest for K 2 2 classes. Additionally, let X; E X and U; E U represent observable and unobservable features, respectively, both of which may be correlated with Y Here, "observable" features are those accessible to the ML practitioner, while "unobservable" features are unavailable in the dataset.
1 Σ MY, (XX)). (3) min Rimbel()) = N1 :D:=1 [:X||K]
However, the empirical risk (tabel(t) may not capture the true risk even when total sample size N + xc:
Rectect (t) + P(Y* * t(x) D= R(t).
In the selective label problem, the true label Y is not always observed; its observability depends
This known as a selection bias problem, where the dis- tribution of (Y*, XX] = 1 in the labeled subpopulation and that of (X+,X) in the full population are different. The selection bias arises because the historical decision D can depend on the features X and U that are also correlated with the true outcome Y*. Hence, one has to adjust for both X and U to eliminate the selection bias, as formalized below. Assumption 3.1. Suppose (1) Selection-on-obserrabee and-unobservables: D 1 Y X,U; (2) Overlap: P(D = 1 X, > almost surely.
binary decision D; E (0,1) } made by decision based the features U4) Specifically, we consider J 2 2 different decision- makers and let Z, E [J] denote the specific decision-mann maker assigned to unit The observed label Y, is defined as:
Y NaN
if D: = 1,
Y,
(1)
if D = O.
When D. = 1 (e.g., bail, loan approval, hiring), the ob- served label Y; is exactly the true label Y,, and when D, = 0, the observed label is recorded as Y, NaN (Not Number), indicating that Y remains unobserved in this case. Thus, each unit's ss label is selectively observed accord- ing to the decision D; made by mecesion-maker Z,
The condition D J L X, in Assumption 3.1 means that the labeled subpopulation and the full population would have the same Y distribution if properly adjusting for (X,U). The overlap condition means that the subpopu- lation with almost any X value has a positive chance to be labeled. Both conditions are standard in the missing data literature (Little & Rubin, 2019). features X, U were both observed, then one could correct for the selection bias by adjusting for X, via many methods in the literature
We assume that {(Y,, D,, Z4, X,, U represents in- dependent and identically distributed samples from a popu- lation denoted by (Y,Y*, ",Y"*,,a D, U). The causal structure of these variables is plotted in Figure 1. However, we can-
3

---

Learning with Selectively Labeled Data from Multiple Decision-makers
(e.g., Rosenbaum & Rubin, 1983; Rubin, 2005; Imbens & Rubin, 2015). However, adjusting for the unobservable U is infeasible, so selection bias remains a significant problem in our setting. This setting is referred to the missing-now not- at-random (MNAR) problem in the missing data literature (Little& & Rubin, 2019). Addressing MNAR is notoriously difficult and typically requires additional information.
Based on the IV framework, we will next understand the power and limits of the multiple decision-maker structure in addressing the selective label problem. In particular, we will analyze the identification of the classification risk R(t) in Equation (2), studying under what conditions the risk can be determined from the distribution of observed data with multiple decision-makers.
3.2. Multiple Decision-makers and IV
4. Exact Identification of Classification Risk
To address the selective label problem, we draw on recent literature that leverage the fact that in many applications the selective labels involve multiple makeess with heterogeneous decision- making preference (Lakkaraju et al., 2017; Kleinberg et al., 2018; De-Arteaga et al., 2018). The rationale behind this idea is that, the unobserved true label Y* for a unit in the missing group (D = 0) could have been observed, if the unit had been assigned to a different decision-maker maker.. This is particularly useful when the assignment of decision-man makers Z is random, indepen- dent of the unobserved featured U. For instance, Lakkaraju et al. (2017); Kleinberg et al. (2018) consider that in the judicial bail, defendant is randomly assigned to judge, so a unit who is not granted bail (and thus unlabeled) could have been assigned to a more lenient judge, received bail, and consequently been labeled.
In this section, we establish conditions under which the classification risk R(t) can be exactly identified from the observed data. This represents settings where consistently evaluating the classification risk is possible, if one properly leverage the multiple decision-make maker structure.
Before delving into our detailed analysis, we define m (X) P(Y & X) as the conditional probabil- ity that Y equals k given the observable features X. The Bayes optimal classifier, which minimizes the classification risk (t)), is determined by s" (X) := arg max; [K] 7% (X). In fact, s also minimizes the excess risk, defined as:
R(t, P(Y* ((()) - PPY # (X)).
(4)
Minimizing R(()) over classifier is equivalent to minimiz- ing Rtt,,*) over as the Bayes optimal risk R(s*) is a constant. Therefore, we can equivalently study the iden- tification of excess risk R(t,s"), The following lemma gives a weighted formulation of excess risk in terms of the conditional probabilities.
Although the previous works have already considered the structure of multiple decision-maken they largely rely on some heuristic approaches. In fact, the assignment of Sacision-mmkers can be formalized as an instrumental vari- able (IV). As we will show shortly, this IV formalization allows us to understand the role of multiple decision makers in a principled way. IV is a well-known concept in causal in- ference. Following standard literature (Angrist et al., 1996; Cui & Tehetgen Tchetgen, 2021; Wang & Tchetgen, 2018, e.g..). valid IV has to satisfy the following conditions.
Lemma 4.1. The excess risk R(t, s*) satisfies
K
R(t, s*) E3
(X)) (Lxx(x)= -4()==)]
Lemma 4.1 indicates to identify the excess risk we need first identify the conditional probabilities ny E [0, 1] of the latent Y* from the observed data. We therefore focus on the identification of 17 (x) = (n) (z)...... 7ik (I)) in the sequel.
Assumption 3.2 (IV conditions). The assignment Z sat- isfies the following three conditions: 1. IV relevance: Z L D X; 2. IV independence: Z 1 (U,Y*) X; 3. Exclusion restriction: 7 DDYY.
Identification of Conditional Probabilities In Section 3.2, we show that the assignment of decision- 2 can be viewed as an IV. By adapting the IV identification theory in the causal inference literature (Wang & Tchetgen, 2018; Cui & Tchetgen Tchetgen, 2021), we can identify the classi- fication risk under the following No Unmeasured Common Effect Modifiers (NUCEM) assumption.
The IV conditions above are particularly suitable for the random assignment of decision-makers. makers. The IV relevance means that even after controlling for the observed features X, different drcision-makerr could have systematically dif- ferent decision rules so that the assignment Z is dependent with the decision D. The IV independence trivially holds when the decision-makee assignment random. The exclu- sion restriction automatically holds because the observed label Y is completely determined by the decision D and true label Y* so it is independent with any other variable given D.Y". We note that these conditions are also explicitly or implicitly assumed in the prior literature. Assumption 3.2 connects these conditions to the IV framework.
Assumption 4.2 (NUCEM). We have, for each x E X, Cov (Cov (D, Z X,U),,P(Y = k X,U) x)) = 0. Theorem 4.3 (Point Identification). Define Yv := I[ = k)). Under Assumptions 3.1, 3.2 and 4.2, ni. (X) is identified,
(5) Conversely, (5) holds, Assumption 4.2 is also satisfied.
(x)) CCov(Dy,, 2 X)/ Cov D, 2 X).
4

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Theorem 4.3 shows that Assumption 4.2 is sufficient and necessary for identifying the conditional probability fune- tion nt'' s through Equation (5). This identification equation connects the conditional probability of the latent true label Y with fully observed variables D, Y, 2, X. This lays the foundation for learning Ti (and classification risk) from the observed data using the decision-maker assignment IV.
Example (Separable and Independent Unobservables). Suppose unobservables U can be divided into two cate- gories: Uj influences the decision D, and U2 affects the outcome Y*. Hence, we have Cov D, Z X,U) = Cov(D, Z | X, U1 and E| X = E|y | X, U2] almost surely. If U1 and U2 are (conditionally) independent, then Assumption 4.2 holds.
Example 3 (Additive Decision Probability). Suppose that for every socision-maker j E [J], the conditional decision prob- ability satisfies IP = 1 U, x, 7 = j) = (x) + ((U) for a common function q and potentially different functions gj- That is, all decision-makers use the unobservables U in common and additive way. Under this condition, we can prove that Assumption 4.2 also holds (see Appendix A.2).
Identification of Excess Classification Risk We can now identify the excess classification risk from observed data.
Theorem 4.4. Based on Theorem 4.3, the excess classifica- lion risk 8*) in Equation (4) is also identified:
K
R(t,s*)= E
Σ
wx (X)[(((X) = =k]],
(6)
The examples above show that the NUCEM assumption needs to impose restrictions on the impact of unobserved features U on either the decision D or the true label Y* or both. However, these restrictions may be too strong in practice so the NUCEM assumption may fail. As a result, the identification formula in Theorems 4.3 and 4.4 are no longer valid. In the next section, we will drop the NUCEM assumption and only impose some mild conditions, leading to weaker identification results accordingly.
where (x(x)= := maXpelK] (x) - (x)) denotes the weight function and my. (x) is identified in Equation (5). This can be simplified for binary classification with K-
=
= ((]l(()))))))))))))())))) (L((X) A sgn 10 (X)I),
(7)
where w(x)= == Cov(DY, 2| / Cov(D, 2 |x) 1/2
denotes the weight and sgn: X + } is sign function.
Theorem 4.4 does not only establish the identification of the excess classification risk under Assumption 4.2, but also formulates the identification into a weighted classification form. Specifically, minimizing the right hand side of Equa- tion (6) corresponds searching cost-sensitive classifier, while minimizing the right hand side of Equation (7) corre- sponds to weighted classification problem with the sign of w(X) as the label and [x( as the misclassification cost. In Section 6, we will show that these formulations are useful in the design of effective learning algorithms.
5. Partial Identification of Classification Risk
The last section shows that the exact identification of classi- fication risk often requires assumptions that are untenable in practice (see Assumption 4.2). Hence it is desirable to avoid such stringent assumptions and instead consider weaker and more reasonable assumptions. Nevertheless, without the stringent assumptions, it is generally impossible to exactly identify the classification risk from the observed data. In- stead, there may exist a range of plausible values of the classification risk, all compatible with the observed data, This plausible range is characterized by the so-called partial identification bounds.
The NUCEM Identification Assumption The identifica- tion results in Theorems 4.3 and 4.4 crucially rely on As- sumption 4.2, which generalizes the NUCEM assumption in Cui & Tchetgen Tchetgen (2021). Notably, their NUCEM assumption involves the difference of certain conditional expectations given the two different IV values, which heav- ily relies on the binary nature of IV. We consider a more general assumption that can tackle multi- valued and contin- uous IV, which strictly generalizes their framework. These identification analyses reveal that additional assumptions are needed to fully identify the classification risk, even when the decision- maker structure already satisfies the IV condi- tions in Assumption 3.2. This fact is not shown in the prior selective label literature without the formal IV framework.
Below we impose a mild bound condition on the conditional probability of the true label for the partial bound analysis.
Assumption 5.1. For each fixed x and k. there exist two known functions ax (2r) E [0, 1] and (x(x) E [0, 1] such that ag (z) < P( = le U, X 2) < bx(r) almost surely.
Assumption 5.1 mandates known lower and partial bounds on the conditional probability IP(Y* = k U.X = a), while permitting arbitrary dependence on unobserved fea- tures U. This assumption is mild it is trivially satisfied by setting a& (x) 0 and (x) = 1. In all our experiments, we adopt this default choice for all & E [K]. With these parameters, we derive explicit partial bound for (X).
To understand the NUCEM assumption, it is instructive to consider examples where this assumption holds.
Example 1 (Full Information). If all features needed to predict the true label Y* are recorded, then E[Y* | X, U] =
Partial Identification of Conditional Probabilities Based on this condition, we can derive tight IV partial identi-
E | X] almost surely and Assumption 4.2 holds.
5

---

Learning with Selectively Labeled Data from Multiple Decision-makers
fication bounds on the conditional probability nfe())
each I E [K], the excess classification risk R(1, is also partially identified. Define the feasible region for the conditional probability vector v)* = (M...... 7KK as
P(Y+ =k k xX for each & [K].
Theorem 5.2. Define Ys= := 1[Y k3 and assume As-
sumptions 3.1 and 3.2 and Assumption 5.1 hold. Then for any x E X and l E [K] the value of nig (x) must fall within
S = 17 |mll1 = L, m7 E [1, uxl, E [K]]. (9)
Then the range of plausible value of the excess risk R(t, is given by the interval R()),, where
the interval (2), (z)],,, where
(x) == max E DY, + (1) - DD X = Z = 2)- =E[l
R(t) = E
max NES
Tu (x) I (10)
(2) :- min E[DY; + (z)) -1 D) X x, Z z|.
=E[J]
and R(t) is symmetrically defined by changing the maxi- mization over r) E S into minimization over the same set. We are particularly interested in the upper bound R(t) as it gives the worst-case risk of a classifier f. Minimizing this upper bound, i.e., m R(t), hence leads to a robust classifier safeguarding the perfrmance in the worst case. Be- low we further provide a reformulation of the worst-case risk under mild regularity condition.
Conversely, any value within the interval [x(x)), (x(( can be plausible value of mg (2). Moreover, the interval end- points satisfy that ag(x) S (x) S (x(x)) S (x)..
Theorem 5.2 generalizes the well-known Balke and Pearl's bound and Manski's bound in Balke & Pearl (1994); Man- ski & Pepper (1998), Specifically, our bounds coincide with Balke and Pearl' bounds when applied to a binary IV (see Appendix B.2). Furthermore, if aXX), b(X) are two constants independent of X (such 0, 1), our bounds re- cover Manski's bounds. Theorem 5.2 also demonstrates the tightness of our IV partial bounds, in the sense that our bounds tightly give the range of all plausible values of the conditional probability ni 's (see Appendix B.
Theorem 5.3. Suppose conditions in Theorem 5.2 hold and the set S defined in eq. (9) is non-empty. Given the bounds [k uk] in Theorem 5.2, we define the "realizable" partial bounds for mic as
[x(x)) = [1 Σ
pffk
ūx(x) = [1 Σ
(x)]] A ux()).
Algorithm Unified Cost-sensitive Learning
pofk
Require: function class H. mode E {point, partial), data
Sy {(,,, D;, ) cross-fitting folds L.
We have
1: Randomly split the data into L (even) batches with
indices denoted by ,y....,, Sy respectively.
R(t)= E
Σ wh (X)I(((X =kt]]
2: for each batch 1 E [Z] do
3: if mode- = point then
4: For A [ use dataset SN S'y estimate the weight k (x) = maxpe(K] (Tp ) - -hx (x)).
where wx(xr) := pf pe(K] (ūp(z) ix(x))) denotes the weight function. This can be simplified for binary classi- fication problems:
5: else if mode- = partial then
6: For E [K]. use dataset SN 5%y to estimate the
R(t)= EE [I(())I(((( + sgn[w(X)]3] + C,
weight w:!| (x: = maxp (πp (x) (x))
7: end if
where C is constant not relying on the classifier t and w(x) == max - 1, + min(21, 1,03.
8: end for
9: Construct the empirical risk for each batch e [4]:
The non-emptyness of set S defined in Equation (9) is mild regularity condition. It is easy to verify from The- orem 5.2 that this condition is automatically satisfied for 4 (X) = O and (X) = 1 for all k E [K]. Like Theo- rem 4.4, here Theorem 5.3 formulates the worst-case risk into cost-sensitive form for general multi-class classifica- tion problems and weighted classification form for binary classification problems. This reformulation will be handy for the learning algorithm design in the next section.
K
ex,(h
R1 (h) Rxp
I
EK exp(hp
RE
10: Return the score function h by minimizing:
L
h E arg min NEH
R! oxp (h).
(8)
Discussions Notably, the partial identification results in this section are quite different than the exact identification results in Section Section relies on a strong NUCEM
Partial Identification of Excess Classification Risk When (nt ke([] are only partially identified within [4,, ug] for
6

---

Learning with Selectively Labeled Data from Multiple Decision-makers
identification assumption (Assumption 4.2). This strong assumption has strong implication: we can pinpoint the exact value of classification risk from the observed data with the pocision-maker assignment as an IV. However, the key NUCEM identification assumption is very strong and may be often implausible in practice. In this section, we instead consider a much weaker bound condition in Assumption 5. This condition is arguably more plausible yet meanwhile it also has weaker identification implication. Under this condi- tion, even with the decision-maker assignment valid IV, the classification risk is still intrinsically ambiguous, so we can at most get a range of its values from the observed data. In the next subsection, we will design algorithms to learn robust classifiers by approximately minimizing the worst- case classification risk. These analyses reveal the power and limits of the multiple decision-maker data structure in tackling the selective label problem, which highlights the value of the principled IV framework adopted in our paper.
solving weighted binary classification with pseudo label sgn(ve [x(X)] and misclassification cost [w(X)]-
6.1. Calibrated Surrogate Risk
The cost-sensitive classification risk R(h, w) in Equa- tion (11) involves non-convex and non-smooth indicator functions [(-), making the optimization challenging. To address this issue, we introduce a surrogate risk Rexp(h. (h, w) that replaces the indicator function with the softmax func- tion. This substitution allows us to define the surrogate for cost-sensitive classification risk:
K
exp(ha(X))
Rexp Teep((,, (h,, w) = E
WO (X)
(12)
Σ ex)(M)(X)))
For the binary case, we introduce the weighted ø-risk as
R. (h, w) = 1E [[(xx)) (h((X) sgn[w(X))) (13)
6. Unified Cost-sensitive Learning
There are many possible choices for the convex surrogate
loss Φ including the Hinge loss <(a) max (1 a, 0),
In this section, we propose a unified cost-sensitive learning (UCL) algorithm tailored to learn a classifier from selec- tively labeled data. This algorithm accommodates both the exact identification setting in Section 4 and the partial identification setting in Section 5 in a unified manner.
the logistic loss Φ(a) log(1 + =-) and the exponential loss Φ(a) e e and on (Bartlett et al., 2006).
Theorem 6.1 establishes a calibration bound linking the cost-sensitive risk R(h, w) to its surrogate Rexp (h, w).
Typically, a classifier ((x) is represented by some score func- tion h: X + K through t(x) = arg max ly (z). Here for any given x, (x) quantifies the score of class k.
Theorem 6.1 (Calibration Bound for Cost-sensitive Risk). For any given weight function w : X' - R2K, we have R.h,, un) R(h, w) S K [[eepp (h, w)-inn inl Rh un) h
According Theorems 4.4 and 5.3, the excess classification risk of classifier i with score function h in the two identi- fication settings can be written into the common weighted form as follows:
h
For binary case, calibration bound can also be established for (h, w) (Bartlett et al., 2006; Tewari & Bartlett, 2007).
K
Proposition 6.2 (Calibration Bound for Weighted Risk). For any fixed function X R. we have
Rh,, w) = E
Wh (x)())(arr)) arg max (x) = kt}. (11)
pE[K]
1=1
Specifically, for each k we set (x) (x
R(h, w) - inf R(hh, w) S (R w) inf R w)
h
(x)) to recover the exact identification in Theorem 4.4 and set (x) = maxp<k,pE(k) (()))))) to recover the worst-case excess risk R(t) in Theorem 5.3. In this section, aim to minimize these risk objectives to learn effective classifiers. This corresponds to cost-sensitive multi-classification problem (Pires et al., 2013).
Theorem 6.1 and Proposition 6.2 show that the target risks can be well-bounded by the excess surrogate risks. Hence we can use sample data to approximately minimize the surrogate risks, which can be efficiently solved.
6.2. Empirical Risk Minimization
Theorems 4.4 and 5.3 also show that for binary classification problems with K = 2, the risk function simplifies to:
We now propose Algorithm 1 to minimize the empirical surrogate risk Rexp (h, w) in Equation (12) using observed data Sy. We also establish the finite-sample error bound for the resulting score function h (see Appendix D).
R(h,, w) E (X) [ sgn [x=) * sgn [w( [-)
Cov( (2 1/2, we recover the classification risk in the exact identification setting. By spec- ifying w(x)= = max(2u,(e - 1, 0}- + min (1)- 0}. we recover the worst-case risk (up to some constants) under partial identification. Minimizing these risks correspond to
By specifying w(x) = CDv 2 [
Weights Estimation fer between point-identified and partial-identified settings, requiring separate estimation. For mode = point, we first estimate Cov Z X) and Cov(DY, Z X) in eq. (5),
The weight functions {w])/_ dif-
1,
7

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Accuracy Scores (Model NUCEM)
LogisticRegressionn
FandomForest
GradlentBoosting
AdsBoost
Confounding Strength: 0.5
Confounding Strength: 0.7
Confounding Strength: 0.9
0.750
0.725
0.700
Clogiliacionn Accunsy)
0.675
0.650
0.625
0.000
0.575
Selacted Sample
Selected Sample (P94
full Sample
Paraa Learning
Point Laarning
Sedeected Sample
Selected Sumple (PPW) Full Samele
Partial Loaming
Polnt Leaming
Seteetted Sample
Selected Sample (iPo) Full Sample
Partial Learning
Polst Learning
Methods
Methoos
Methods
Figure The testing accuracy of methods with a E {0.5, 0.7, 0.9) for model NUCEM in FICO dataset.
then compute their ratio. For example, Cov DY,, x) 7
incorporate regularization in Equation (8) to reduce over- fitting. In the binary setting, we can simply solve a weighted classification problem with sgu [xx (X)]ss as the labels and [X)] as weights, and this can be easily implemented by
can be expressed as E[DZY, x²] - E[DY; x] E x].
with conditional expectations estimated via regression on
X x. Alternatively, forest methods, such as General- ized Random Forests, can directly estimate the conditional covariance ratio in one step (Athey et al., 2019).
off-the-shelf ML packages that take additional weight inputs. For example, considering the surrogate risk in Equation (13) with & as the logistic loss, we can simply run a logistic regression with the aforementioned labels and weights.
For mode= = partial, we estimate the bounds 4 and un for each & E [K] as defined in Theorem 5.2, involving conditional expectations E[DY, x, 22] and E[D x, x] via regression. These bounds are then used to construct wx (x). The precision of weights estimation do affect the accuracy of downstream classification task. To illustrate this, we implement the ablation study by injecting the noise to the weights estimation. See Appendix E.2 for the discussion.
7. Numeric Experiments
We conduct experiments on synthetic dataset with a multiclass label (K 3) and semi-synthetic dataset with binary label (K" = 2). Below, we briefly sum- marize our experiment on the semi-synthetic data, with comprehensive results provided in Appendix E. Refers the code and data to hitps: / com/ hanm//heha997 Learning-Selecte -aaeeiiieeaaabl.....ooo
Cross-fitting In Algorithm 1, we divide the dataset into folds and apply the cress-fitting to estimate these weight functions. This approach has been widely used in statistical inference and learning with ML nuisance function estima- tors (e.g.. Chernozhukov et al., 2018: Athey & Wager, 2021), which effectively alleviates the over-fitting bias by avoiding using the same data to both train weight function estimators and evaluate the weight function values.
Semi-synthetic Dataset This dataset consists of 10459 ob- servations of approved home loan applications. The dataset records whether the applicant repays the loan within 90 days overdue, which we view as the true label Y", and various transaction information of the bank account. The dataset also includes a variable called ExternalRisk, which is a risk score assigned each application by a proprietary algo- rithm. We use FxternalRisk and all transaction features as the observed features X. In this dataset, the label of interest is fully observed, we synthetically create selective labels on top of the dataset. Specifically, we simulate J = 10 Decision-maker (e.g.. bank officers who handle the loan applications) and randomly assign one to each case. We generate the decision from Bernoulli distribution with function with softmax being the output layer. We can also
The cross-fitting estimation entails some additional com- putational costs, but this typically only involves a series of standard regression/cassiffattion fitting, which is usually manageable and can be accelerated by parallel computation.
Classifier Optimization The empirical surrogate risk in Equation (8) defines a cost-sensitive classification problem. Once the weight function {wx} ] are estimated, we can then solve for the score function h. which can be imple- mented using PyTorrc by defining a cost-sensitive loss
success rate pD : P(D = 1 X, U) that depends on an
8

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Accuracy Scores (Model UC)
Logiciccoonossionn
SVM
RondomForest
GrodknnBeoccing
AdoBoost
Confounding Strength: 0.5
Confounding Strength:
Confounding ng Strength:
0.75
0.73
0.70
Cussitaaton Accuaayy
0.60
0.65-
0
00
0
0.50
0.55
Selected Sample
Seleczed Sampla (Pen)
Full Sample
Pamall Learnin
Point Leaming
Seiected Sample
Selecead Sampla (Pen
Fue Sample
Partia Leaming
Point Leaming
Seiected Sample
Selected Sampta (een
Full Sampl
Partial Leaming
Point Learning
Methads
Methods
Mechods
Figure 3. The testing accuracy of methods with a E {0.5, 0.7, for model UC in FICO dataset.
"unobservable" variable U, the macesion-maker identity Z, and the ExternalRisk variable:
is comparable with the baseline method which run classi- fication algorithms directly on the selective labeled data. Moreover, we observe that as the degree of selection bias a grows, the gains from using our proposed method rel- ative to the SelectedSample baseline also grows, espe- cially for the PartialLearning method. Interestingly, the PartialLearning method has better performance even un- der NUCEM model when the point identification condition holds. This is perhaps because the PointLearning method requires estimating a conditional variance ratio, which is often difficult in practice. In contrast, the PartialLearning method only requires estimating conditional expectations and tends to be more stable.
NUCEM oo (U) (1 aa)a((1 7) ExternalRisk), PD
PD= (aU + - (1 + Z) ExternalRisk).
(-t) The parameter ap E (0, 1) controls the impact of U on the labeling process and thus the degree of selection bias. The unobservables U is constructed as the residual of a HistGradient Boosting ing regression of Y* with respect to X, which is naturally de- pendent with Y*. Finally, we blind the true label Y* for observations with D
Here we define (t)) = 1
Methods and Evaluation We randomly split our data into training and testing sets at 7 : 3 ratio. We compare five methods: SelectedSample (training classifiers only on the labeled sample), SelectedSample-IPyy (using labeled sample only but with additional inverse propensity weight- ing to correct selection bias due to observed features X), FullSample (ideal benchmark that observes all labels on the full sample), PointLearning and PartialLearning (our proposed methods based on the exact/point and partially identified risks using decision decision-maker assignment as IV). The first three methods serve as the benchmark of our meth- ods. For each method, we try multiple algorithms including AdaBoost, Gradient Boosting, Logistic Regression, Ran- dom Forest, and SVM. All hyperparameters are chosen via 5-fold cross- cross-validation, and we evaluate the classification accuracy of classifiers on the full-labeled testing data.
In addition, we conduct experiments on synthetic dataset with a multiclass label in Appendix E. The results demon- strate that our methods, particularly PartialLearning, achieve higher classification accuracy than benchmark meth- ods under varying degrees of selection bias.
8. Conclusion
We address multiclass classification with selectively labeled data, where the label distribution deviates from the full population due to historical decision- Leveraging variations in decision rules across multiple we analyze this problem using an instrumental variable (IV) framework, providing conditions for exact classification risk identification. When exact identification is unattainable, we derive sharp partial risk bounds. To address label selection bias, we propose unified cost-sensitive learning (UCL) approach, supported by theoretical guarantees, and demon- strate its effectiveness through comprehensive numerical experiments.
Results and Discussions Figures 2 and 3 reports the testing accuracy of each method in 50 replications of the experiment when a E {0.5, 0.7.0.93 under both NUCEM and UC mod- els. We find the performance of SclectedSample(PPW))
9

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Acknowledgements
Cui, Y. and Tchetgen Tchetgen, E. semiparametric instru- mental variable approach optimal treatment regimes under endogeneity. Journal of the American Statistical Association, 166533):162-117 1121)7,,,...1., 2 2021.
thank anonymous reviewers and meta-reviewers of ICML 2025 for their valuable feedback, which led to greatly improved manuscript. Xiaojie Mao acknowledges the support from National Natural Science Foundation of China (grant numbers 72322001, 72201 150, and 72293561) and National Key R&D Program of China (grant number 1022000116700)
De-Arteaga, M., Dubrawski, A., and Chouldechova, A. Learning under selective labels in the presence of expert consistency. arXiv preprint arXiv:1807. 1807000970, 2018.
De-Arteaga, M., Jeanselme, V., Dubrawski, A., and Chouldechova, A. Leveraging expert consistency to improve algorithmic decision support. arXiv preprint arXiv:2101.09448, 2021.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
FICO.
Explainable machine learning challenge, 2018. URL
http::://community...cc..m cttp:icc.ccoo.oooooooooooaaaaaae s/ tabset-158d9
References
Angrist, J. and Imbens, G. Identification and estimation of local average treatment effects, 1995.
Imbens, W. and Rubin, D. B. Causal inference in statis- tics, social, and biomedical sciences. Cambridge Univer- sity Press, 2015.
Angrist, J. D. and Pischke, J.S.. Mostly harmless econo- metrics: An empiricist's companion. Princeton university press, 2009.
Kédagni, D. and Mourifie, Generalized instrumental inequalities: Testing the iv independence assumption. Available at SSRN 2692274, 2017.
Angrist, J. D., Imbens, G. W., and Rubin, D. B. Identi- fication of causal effects using instrumental variables. Journal of the American statistical Association, 91(44)) 444 455, 1996.
Kilbertus, N., Rodriguez, M. G., Schölkopf, B., Muandet, K., and Valera, I. Fair decisions despite imperfect pre- dictions. In International Conference on Artificial Intelli- gence and Statistics, pp. 277-287. PMLR, 2020.
Amold, D., Dobbie, W., and Hull, P. Measuring racial discrimination in bail decisions. American Economic Review, 12(9):2992-3000 2022.
Kleinberg, J., Lakkaraju, H., Leskovec, J., Ludwig, and Mullainathan, S. Human decisions and machine pre- dictions. The quarterly journal of economics, 133(1): 237-293, 2018.
Athey, S. and Wager, S. Policy learning with observational data. Econometrica, 89(1)133-161, 2021.
Kling. J. R. Incarceration length, employment, and earnings. American Economic Review, 96(3):863-87) 876, 2006.
Athey, S., Tibshirani, J., and Wager, S. Generalized random forests. The Annals of Statisties, (7(2):1148-111 2019.
Balke, A. and Pearl, J. Counterfactual probabilities: Compu- tational methods, bounds and applications. In Uncertainty Proceedings 1994, pp. 46-54. Elsevier, 1994.
Lakkaraju, H., Kleinberg, J., Leskovec, J., Ludwig, J., and Mullainathan, S. The selective labels problem: Evalu- ating algorithmic predictions in the presence of unob- servables. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 275-284.11 2017.
Bartlett, P. L., Jordan, M. I., and McAuliffe, J. D. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):38-11) 2006.
Little, R. and Rubin, D. B. Statistical analysis with missing data, volume 793. John Wiley & Sons, 2019.
Bertsimas, D. and Fazel-Zarandi, M. M. Prescriptive ma- chine learning for public policy: The case of immigration enforcement. Under review, 2022.
Manski, C. F. Nonparametric bounds on treatment effects.
The American Economic Review, 80(2):31-322 1990.
Chernozhukov, V., Chetverikov, D., Demirer, M., Duflo, E., Hansen, C., Newey, W., and Robins, J. Double/debiased machine learning for treatment and structural parameters, 2018.
Manski, C. F. and Pepper, J. V. Monotone instrumental variables with an application to the returns to schooling, 1998.
10

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Mao, A., Mohri, M., and Zhong, Y. Cross-entropy loss func- tions: Theoretical analysis and applications. In Interna- tional conference Machine learning, pp. 23803-23828. PMLR. 2023.
Wang, L. and Tchetgen, E. T. Bounded, efficient and multi- ply robust estimation of average treatment effects using instrumental variables. Journal of the Royal Statistical So- ciery. Series B, Statistical methodology, 80(3):531, 2018.
Massart, P. and Nédélec, É. Risk bounds for statistical learning. Annals of Statistics, 2006.
Wei, D. Decision-making under selective labels: Optimal finite-domain policies and beyond. In International Con- ference Machine Learning, pp. 11035-11046 PMLR, 2021.
Mueller-Smith, M. The criminal and labor market impacts of incarceration. Unpublished working paper, 18, 2015.
Yang, Y., Liu, Y., and Naghizadeh, Adaptive data debi- asing through bounded exploration. Advances Neural Information Processing Systems, 35:1516-1528 2022.
Pires, B. A., Szepesvari, C., and Ghavamzadeh, M. Cost- sensitive multiclass classification risk bounds. In Interna- tional Conference on Machine Learning, pp. 1391-1399. PMLR, 2013.
Zhao, Y., Zeng, D., Rush, A. J., and Kosorok, M. Es- timating individualized treatment rules using outcome weighted learning. Journal of the American Statistical Association, 107(499):110--1111 2012.
Pu, H. and Zhang, B. Estimating optimal treatment rules with an instrumental variable: A partial identification learning approach. Journal of the Royal Statistical Soci- ery: Series B (Statistical Methodology), 83(2):318-34 2021.
Qian, M. and Murphy, Performance guarantees for individualized treatment rules. Annaly of statistics, 39(2): 1180, 2011.
Rambachan, A., Coston, A., and Kennedy, E. Counterfactual risk assessments under unmeasured confounding. arXiv preprint ar arXiv:2212.09944 2022.
Rambachan, A. et al. Identifying prediction mistakes in observational data. Harvard University, 2021.
Rosenbaum, P. R. and Rubin, D. B. The central role of the propensity score in observational studies for causal effects. Biometrika, 70(1):41-55 1983.
Rubin, D. B. Causal inference using potential outcomes: Design, modeling, decisions. Journal of the American Statistical Association, 100(469):322-331, 2005.
Shalev- Shalev-Shwartz,5 S. and Ben-David, S. Understanding ma- chine learning: From theory to algorithms. Cambridge university press, 2014.
Swanson, S. A., Hernán, M. A., Miller, M., Robins, J. M., and Richardson, T. S. Partial identification of the aver- age treatment effect using instrumental variables: review of methods for binary instruments, treatments, and out- comes. Journal of the American Statistical Association, 113(522)933-947,, 2018.
Tewari, A. and Bartlett. P. L. On the consistency of multi- class classification methods. Journal of Machine Learn ing Research, 8(5), 2007.
Wainwright, M. J. High-dimensional statistics: A non- asymptotic viewpoint, volume 48. Cambridge University Press, 2019.

---

Learning with Selectively Labeled Data from Multiple Decision-makers
A. Supplements for Point Identification
A.1. Proofs in Section
Proof of Lemma 4.1. By the definition of excess risk in Equation (4), we have
R(t,,*) = P(X," * t(x.)) - F + sxXi)
E P(X ((x)) x.) - P(Y + (X.)) | Xi)
R
(x.)) (xx)) | x.) - P(k # *xx)) x
(x.) (P(6 k (x)) = * (xx)))
(x.) - [B(((5(X.)) = k} - -I((x)) = =b3 xx]
E
(X,) (4(+((x)) = k} - [(((x)) = A1)
E
nt (X.) (T(arg 17, = k} - -(((x)) 12)] PE[K]
We apply the iterated law of expectation in second equality, and the total law of expectation in third equality. The fourth equality comes from the sum-to-one constraint of probability. The fifth equality is established from the definition of indicator function and the sixth equality follows again from the iterated law of expectation. Finally we apply the definition of Bayes optimal s" (X:) arg max Th (X:).
Proof of Theorem 4.3. In this part, we prove that, under Assumptions 3.1 and 3.2, Assumption 4.2 is the necessary and sufficient condition of the exact identification of PPYY = k X). To simplify the notation, we denote two new variables Y := =I{Y = 13 and Ys= := L = k).
Sufficiency: For any 2 E 2, the conditional probability P(Y* k X, = 2) = B| |x = 2] could be expressed as
E|y
X, 7
2| = B B X,U, X,
= E E X,U, =] X,Z =] [ D)YE X,U, =]1 = =
= [E[DY, X,U, 2| X = =] + [1 - D)YE' X,U, x x,Z
= =| X, 2] (14)
= [E[EYYY X,U,Z= =] |X, Z = 2] +
- -D) |X,
[E[DD X,U,2= =| X, = 2] [[ [,0]-B[(1- D) x =
=E[DY, =
X, Z 2] E[E |X,]] |X,U =
In the first and second equalities, use the iterated law of expectation and the linearity of expectation. The third equality follows from the consistency between observed label and true label from Equation (1), that is, Yv = YY when D - 1. The fourth equality follows from the unconfoundedness of Yg and D given X and U, which is guaranteed by the general unconfoundedness (Y* D X, U) in Assumption 1. We use the IV independence (Z 1. Y2 X) from Assumption 3.2 in the fifth equality. The last equality follows again by the iterated law of expectation and lincarity of expectation.
By subtracting E
X] on both sides of Equation (14), we have for any 2 E Z,
0 = E[DY
X, Z = =] - E [
X,U E E
X, U. 2] |X 2 2] X,U E[D X,U. Z = 2) [X],
= DY
X, Z 2| - E E
12

---

Learning with Selectively Labeled Data from Multiple Decision-makers
where the last equality follows from the IV independence (Z T U X) from Assumption 3.2. Now, by multiplying the weight I = X) on both sides of equation ahove, have
0 = E X, 2 = =] E V XXU]
D X, U 2 = =] X X.U] E X.U, = P2 = X) x
E X, Z 2] 1 = = X) E. Y
E|=DYk X
P(Z 2 X) E
X.U] E[ X.U, =]] .P(Z X, x
He we apply the IV independence (Z 1 U X) again in the last equality above. Taking the summation (or integral) for & over 2 yields the following results:
0 EIZDY X] E[E[Y] (XUU-EEZD) X,U x].
Moreover, observe that
BIZDY& XX] = Cov Z () X EIZ XX [[ZD] X, DDv X,U) B|D X, U]- E|Z X, X,U,,
we have
0 Cov(DY Z X) + D[DY X] Z X E EE X,U] Cov Z (2U) X
(15)
E[ X,U] D X, U1
E|Z
X. 51 X].
IV
Here again we use the consistency that E[DY; X] = E X]. By the unconfoundedness (Y* 1. D X, X)U) from
Assumption 3.1 and IV independence (Z 1 U X) from Assumption 3.2, we have EiZ X, U] = E[Z X] and
B X, E XXU] U1 E|Z X,U E U. E[2 x].
Therefore the II and IV terms in Equation (15) cancel out, which lead us to the result
Cov,DY, X) E E |.U] Cov Z X,U) U)) | x|.
(16)
Finally, by assuming Assumption 4.2 holds, that is,
Cov ( (Cov(D, Z | F X,U] x) = 0,
we have
E E Y
X,U] Cov(D, Z XXU) X] E [ X,U x] E Cov D X,U) x]
E|Y
X] E Cov D, Z X. X.U) | x].
According to conditional covariance identity and IV independence (Z T U X), we have
Cov(D,2 Z X) = E Cov(D, Z X,U) |
x E Cov(E D X, U1. Z|Z X,U x
E Cov (D, 2 X,U) X] + E (E X, U], E[Z X]) X]
(17)
B[ Cov 2 X,U) x].
Combining (17) with (16) leads us the desired result, that is,
(x) = E x] = Cov(DY,, 2 X)
Cov 2 X)
Necessity: Given the identification result E X]
Cov(DY, and the Equation (17), we have Cor(D,2[X]
Cov( Dow(DY, | = E X] Cov (D, Z X)
= E E
X.U] x] E Cov (D, Z (X,)) x].
13

---

Learning with Selectively Labeled Data from Multiple Decision-makers
On the other hand, have the identity (16) established when every Assumptions 3.1 and 3.2 hold, that is,
Cov Z X) E| X.U] Cov(D, | [x]]
X.U)
Therefore, combining these results together, we have
IE [ X,U] ( x] which then recovers condition (4.2).
B EE X, []] [[Cov(D, X,U) x] 0,
Proof of Theorem 4.4. By the result in Lemma 4.1, we have
K
(Harg max m7 (X;) = k} - Ift(x,) =k1)
R(t,s*) = E
(x:)
KE[K]
E
max (X,)) (X.) -[(((x)) =k pE[K]
K
=
E
Wk (X,) -T(((X,) = 1}]
For each & E [K]. we define (X) == ma [ (x) - - (x)) According to Theorem 4.3, when NUCEM conditions Assumption 4.2 are satisfied for each & E [K]. the conditional probability Te can be uniquely identified by Equation (5). Therefore, the weight function can be further identified as
{
(Cov Z X) Cov Z X) 2 x) ) Ak (K].
Cov(DY,, 2 x))
}.
PE[K]
Now, consider binary classification with the true label Y {-1,1}. Let (z) = P(Y* = X x)) denote the conditional probability of Y = 1 given X x. The Bayes optimal classifier is 8" s'(x) sgn[n)" (x) 1/2]. As consequence, the excess risk can be then written as
R(t, s*) = PY * t(x)) - +
E =[(((+ (1)) T[Y" *x)) (x)]
(4-1+1(x) E [((((x) [1[1 [(x) 4x) (X))) ((1 (1)--())))((--+10))))
+x)41(
- (()) -1-1++
E (2) (*(x)-(x2)
[1((((x)-1) 1/2| (s((x)(((x)) -((X)]
-
[1) [[(() + sguln" (X) - 1/21]
By defining the weight function exact (X) = (X) 1/2, we have
R(t, s²) B
B 11 exect (x) l[t((x= + sgn exact (x)1
R(t, oxact).
Applying the identification result from Theorem 4.3, we obtain
w exact (X) = Cov(DY, X)
Cov X) 1/2.
14

---

Learning with Selectively Labeled Data from Multiple Decision-makers
A.2. Sufficient Condition for Point Identification
Proposition A.1 (A Sufficient Condition for Point Identification). Suppose Assumptions 3.1 and 3.2 hold. For any 21 [m], define ())(X : B X, U, Z j] - [ X, U, Z = 1]. Assumption 4.2 holds if. for any j. e [J],
Cov A (x, U) P(Y* X; U) x)
a.s.
(18)
Proposition A.I outlines a sufficient condition for Assumption 4.2. This condition permits unobserved features to influence both the decision D and the true outcome Y*, but constrains this influence to specific form. Specifically, the condition is met when [ U, X, Z = Oj X) ((U) almost surely, with functions Øj and reflecting the impact of U is additive and consistent across all Serision-makery
Proof of Proposition A.I. Notice that the conditional covariance Cov [D, 2 X, U) could be decomposed as below:
Cov(D, 2| X, U) E|DZ X.U D
X, U Z X,U
E X,U, 2 P(Z = X,U) - E D x, UJ
j P(Z = X,U)
j=1
E[D X,U, Z = 51 - Σ
D
X, U, Z = 11 P(Z = = x1) E = |X,U)
j. PPZZ (1,) P2 = |(U) EED - x,U,Z= 1]
Define U) = BID X,U, - -- BID X, U, = .j. If for any j. I [m]. we have
Cor(A,1(X,)), P(Y = k X, x = 0 almost surely,
Assumption 4.2 then guaranteed.
15

---

Learning with Selectively Labeled Data from Multiple Decision-makers
B. Supplements for Partial Identification
B.1. Tightness of IV Partial Bounds in Theorem 5.2
Theorem B.1 (Tightness of IV Partial Bound), Assume Assumption 3.1 is valid, and the conditional joint distribution of observable variables (Yg, D, 2) X is fixed. Consider a new set of random variables (Yg D, 2, U) where Y and D are binary, and Z = Z. Define the observed label Y3 as D Y% + (1- - D) - -NNN If the expectation E|y | X = z] falls within the interval (x), ux(x)) for all x E X, then it is possible to establish a conditional joint distribution for (Yg. D, Z) given X- that satisfies:
1. The IV independence in Assumption 3.2 is met.
2. The conditional joint distribution of (Yg, D, 2) X matches the initial distribution (Yx, D, X
3. The natural bounds in Assumption 5.1 are maintained.
Theorem B.1 along with Theorem 5.2 establish a two-way correspondence between the conditional mean outcome E|
X = z] and the IV partial bound [4 (2), uu (z)]. ]. On one hand, any value of E[ X z within this interval corresponds to a feasible conditional joint distribution of (Yr D, 2) X = x that is consistent with the observed data (Y₁, D, Z) X = x. On the other hand, any conditional joint distribution of (Yg: D. 2) X consistent with the observed data must yield a conditional mean outcome E X xx] within the interval (x), un (x)). as established in Theorem 5.2.
These results underscore the tightness of the IV partial bound in Theorem 5.2 and the necessity of the bounded label assumption in Assumption 5.1 for the partial identification of the conditional probability mi.
Proof of Theorem B.I. The proof is adapted from (Kédagni & Mourifie, 2017). Let (Y D. X, be a sequence of random variables such that = Z almost surely and (x) < E[ X = x] < ux(x)) for every x E X.. Given that Assumption 3.1 held and fix X = for some E X, we aim to prove that, for every possible value of E[y; | x] e [4x (z), 24 (z)], there exists conditional joint distribution of (Yg D, Z, () given X = such that: (1) IV independence in
Assumption 3.2 holds, that is, _1 Y X for every X: (2) the new observable variables (Yx, D, Z) X has the same conditional joint distribution the fixed observable variables (Y,, D, Z) X æ, (3) Assumption 5.1 holds.
Without loss of generality, we first consider the case when EE V
X = x² = 4 (z)) As a consequent, we let
P( = X- = x) = ((x) = max
EEDY X = x, Z = x] + a(x) (1 D X = x,, x, =
=Em)
(19)
P( = 0 X x) = (x)).
where the last expression follows by sum-to-ore constraint of conditional probability. Note that we does not impose any observable restrictions on the conditional joint distribution (Y,, D) given x and Z 2, we define the following: for all E Z,
P(Y = D = X = x,
EJDY, X = x, 2 =
P(Y: = 1, - X = =x,,7. ===,ā==: ==)==)=-- :- (x) B(DY; X xx, x. 7. =]
(20)
P(Ý 0, 1 ==,ā==3 =
Z EED' |X =x =]
P(Ý: = 0 -0 0 X = ==x, =,, =)) --1-4xx)) - -EED x = x, Z 2] -EDY X = xx 2 x]).
Notice that all of the conditional probabilities are well-established they are all between 0 and 1, and the sum-to-one constraint is established as follow:
Σ
Σ
P( = = - 1, V...Va [m].
JE
We now prove the three statements mentioned above.
16

---

Learning with Selectively Labeled Data from Multiple Decision-makers
1. IV Independence: To check whether have 2 I & X x, notice that for any = E Z,
x. =) -
- -) D- - 1,
X - = 2) + P(Y = 1, D = =) ((
P(Y 0 =)
0, - 1 z, 2 -= 2) + P(Y 0, x
= (x))
We can see that the conditional distribution of Y given X = and 2 2 does not depends on for any 2 E [m]]. and therefore we are able to claim that Z is conditional independent with Y given X
2. (Yx, D, 2) X x: has same conditional joint distribution as (Y₁, D, 2) X r: Recall that the observed label is defined Yx D + (1 - D) NaN. By Equation (20), we have for any E 2,
P(K = 1, = 1| = = x, = = P(Y = - = = 2)
= E[DY, X = 2-
P(Y: = - x, 7 = 2)
= 0, = P(Ý: = =0. =2)=2)
= E[D x EJDY; X =x, = =
- =x, =2)
(21)
P( = NaN, D= )= P()=0|
= Σ P(Ý; = k = 0 X =x,
(E(0.1)
= =1-E(D | x = x, 2 = =P(D = 0 x=
= -((Y = = D- = -0 0 x, x, =).
As a result, we have shown that the observed variables (Vr,, 2, X x has exactly the same conditional joint distribution with (Yx; D, Z)
X x.
3. Finally, we show that when B[y; X 2| (z),, there exists joint distribution (Ýg, X, Ú) such that E Ú, z] = axx). Without the loss of generality, we assume
20 == arg max (B[DY, x = x. Z = (x()) E((1 - D) X = x. 2 = = E D)
=6(m]
and then we have
B| 1 x| =4((== = B(DY, X = x, 2 = zol + (x) E[([1 - D) X = x, Z = =ol--
(22)
Meanwhile, by the statement of IV independence that 2 Y x = xr, we have for Z 20,
E| x x| = E X = = 20l
= =EDY X= x, 2 = zol + [1 D) | x. 2 un]
=Ei x=
x. ; =0] E - カソ |Ū, -x,=1,77 = 20l x = x, = =z0]
=
B[DÝ xx= x. 2= zu] + EE - - 10, -= za] X xr 2 =z]]-
The first line and second line come from the IV independence and linearity of conditional expectation. The third line follows by the consistency of observed outcome as well the iterated law of expectation. The last line follows by Assumption 3.1 (D 1 Y X, U) and the IV independence.
From Equation (21), we have E
X
= x, Ž = zol E(DY X = x, Z = 20). and therefore
B
X = x|
E
DY
X == =x 20]
(23)
E
Ú, z] E[( - D) Ü X x, 7 20l X = xx 2 z0].
17

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Now, suppose that there is not any conditional joint distribution of (Yg, D, given X such that BIyg Ü X = x| = ax(x) almost surely. Alternatively, we assume there is conditional joint distribution for (Yg, (, U) X z
such that E U, X = x| = (x(x) + (xx U) almost surely. Substitute this condition into Equation (23), we have
EIVE x = E X = = = =o] + ox [[ - D) X - = 20.
+ + ( X ú) B( - 5) U. X = x, = 20] | X = xz, = 20
(24)
= (1) + E e (X, (((,))),(X11)))) D) 1 0,
x, 2 = = 1 = v, 2 20
In the first equality, we use the iterated law of expectation and fact that ag (x) is independent with unobserved variable
Ü. The second equality follows from Equation (21) that PDD = 0| X = x, = z0) = PDD = 0 X = x, Z = 2) for any fixed E X and 2 E [m²] along with the definition of (z).
As a consequence, if
E B[E(X,U) E[( D) (0)10,3 Ü = x, 2 = z01 X = x, 2 = =zo] #0.
then Equation (24) contradicts with Equation (22), implying that there is indeed a conditional joint distribution for (Y,,D,0 X == x such that B[ Ü, X = x] = ax (z). On the other hand, if
B[s(X,0) Ú) [1(11 か) Ü, x x. 7 = z0l x x. 7 = =0] =
(25)
then the conditional joint distribution for (fx, D, D, X = x induced by the Equation (25) is exactly the "right"
distribution for the establishment of [Y | X = x] = ag (z).
Therefore, we have shown that when E| | X = x] = (x), there is always a conditional joint distribution for (YE,D,0) D) X = x such that B|Y 0 X = x] = ag (x) almost surely.
To wrap up, we
that the establishment of statements 1 and 2 do not rely on the condition IP = = (x) in Equation (19). In fact, whenever we choose (z) E [x), ux (1r) for a fixed E X, we can simply choose
P(Y;" = 1 X = x) gb (1). As a result, the IV independence 2 1 Yr X = x always holds, and the new observable variables (Yx, D. Z) X still has the same conditional distribution (Yx, Z) | X = z, which is fixed as prior.
However, the value of P = 1 = 2) condition does affect the value of VE[ 0 X = zz. If we let E[y; | =x x]
Mxxz)) (z), we can show in similar way that E[L; Ü, X = x]| = -bx (z) almost surely. In fact, following the proof of statement
3. one can prove that, for any ga (ar) E (x), ux (Ir) such that Ely; x X = x|| = Ih (2), there is always conditional joint
distribution for (Yg, D, X such that E[ Ü, X 2] Ct (x) almost surely and (x)) E [ax(x)) by (4)]-
Therefore, we have shown that under Assumption 3.1, whenever we have BYE X = a] E [xx(,,,, un (2:). there is always a conditional joint distribution for (YE D, 2,) | X = x such that the three statements in Theorem B.1 hold. To conclude, we claim that the IV partial bound (x), (z)] introduced in Theorem 5.2 is sharp for E|y X = æ] given the establishment of Assumption 3.1, the IV independence in Assumption 3.2 and Assumption 5.1.
B.2. Balke and Pearl's Bound
(Balke& & Pearl, 1994) provides partial identification bounds for the average treatment effect of binary treatment with a binary instrumental variable. In this section, we adapt their bound to our setting with partially observed labels and a binary IV (i.e., the assignment one of two decision-makers). Under Assumption 3.2, we have following decomposition of joint probability distribution of (Y, D, U)
P(Y, D. 2,)) = P(Y| D,U) - P(D) | Z,U) - -P(Z) -PU)).
(26)
Here we omit the observed covariates X for simplicity, or alternatively, all distributions can be considered as implicitly
18

---

Learning with Selectively Labeled Data from Multiple Decision-makers
conditioning X. Now define three response functions which characterize the values of Z. D(0), D(1), and Y*:
if D(0) 0 and D11) = 0
if = 0
1 if D(0) 0 and D(1) 1
0 if Y =
T
Z = TD
ry
2 if D(0) = 1 and D(1) = 00
1 if y==1
3 if D(0) = 1 and D(1) =1
Next, we specify the joint distribution of unobservable variables rD and ry follows:
Uki P(rD ry =) e (0,1, j {0,
which satisfies the constraint ( + qx1) Then the target mean parameter the true outcome can written as linear combinations of the q s. Moreover, we note that the observable distribution P(Y, 2) is fully specified by the following six variables
Pna.0 PP(D 0 ==
P=a,1 - - -
P01,0 P(Y = 0, = 1 Z = 0)
Pu1,1 = P(Y = 00 - = =)
P11,0 = P(Y = D
= 0)
P1L1 = P(Y = = 1 =),
with constraints P11,0 + P01.0 + Pno,0 = 1 and P11.1 + P01.1 Pna.1 1. We also have the following relation between p's
and g's:
Pra.D 900 901 910 911
Pna.1 900
q01
920
921
P01.0 = 920 + 930
P01,1 Q10 930
P11,0 = Q21 +
P11.1 = Q11 + 431
Therefore, we have = Pq where (Pna,0:
P11.1).
(200
431). ) and
1
0
0
1
1
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
1
0
Then the lower bound on P(Y* = 1) can be written as the optimal value of the following linear programming problem
min
411 + 921 + 431
subject to
Σ 9kj =1
(27)
k=
Pq=p
[kj
2 0 k (0,1,2,3), 1).
Similarly, the upper bound on IPYY* 1) can be written as the optimal value of the following optimization problem:
max
90i + Q11 + 021 + 931
3
subject to
Tkj =1
(28)
k=
Pg p
kkj 2 0 k E (0,1,2.3), je (0,1).
19

---

Learning with Selectively Labeled Data from Multiple Decision-makers
In fact, by simply comparing the variables in the objective function P(Y* 1) 901 Q11 + 921 + 431 and those in constraints, could find that
P11,0 921 + 931 S I( 1)
P11,1 911 + 931 S P( =
P11,0 + Pna,0 900 + Q1o + 401 + 911 + 42 + 231 2 P(Y =
P11.1 + Pna.1 = 900 + 920 + 401 + 911 + 421 + 931 2 P(Y" = 1).
we let
L = max(p110.PP1.1) max ==(0,1}
1P(Y=1,1 1 =))
(IP(Y 1, 2 --) = (29)
U min(p11. Pno.0: + Pno,1)
min =E(0,1)
We then have the following partial bounds of PY 1).
L S P(Y = 1) S U.
According to (Balke & Pearl, 1994), the bounds above are tight for P(Y = 1). We note that if we condition X in these bounds, then the corresponding bound on P(Y* 1 X) coincide with the bounds in Theorem 5.2 specialized to a binary instrument.
B.3. Proofs in Section 5
Proof of Theorem 5.2. We first prove the construction of IV partial bound, and then show that the IV partial bound (x), un (1)) is tighter than the natural bound [ox (a:), by (x)] for all & E [K] when is fixed.
1. Under Assumptions 3.1 and 3.2, Equation (14) gives that
P(Y k x = B|yg
X = x]
E(DY& X 7 = E E
UU x] E((1)
xx, x, Z =] =,,
x, Z = =]
As we have assumed that E U, 2| (z), (x)) almost surely in Assumption 5.1, then have
E|y x = x] E DY
= 2 2] +
E [B[(1 - D) | U, = = = x, 2 =
DY
X = +] (x) E[ D) x ==
and
B|y; X = < BDY X = - x
= EDDY | = x, = =] - D)) X = x, x, x]
for every E [m]. Optimizing the lower and upper bounds of E|Y X x|| over Z yields the desired results:
(BIDY&
= x = an (x) (1 - EI x, = =1)}
max 2E2
s E X = x <
min 22
[B[DY,
X = n. -= 2] (x) (1 (1-E X x, 2 == =1)}
2. By taking the conditional expectation on both sides of the inequality, a direct consequence of Assumption 5.1 induces natural bound for E| X = 27), that is.
ax (x) E E X x= S= (x).
20

---

Learning with Selectively Labeled Data from Multiple Decision-makers
We now show that the IV partial bound (x)),, (x)) is tighter than the natural bound [ax (1)) (x)) for any X. Without loss of generality, let
2g = arg max {E|DY&
X x. Z = ax) E((1 D) X z. Z 21}
26 m
and then we have
(x))) R[DYK X x, 20| 04 (2) [F[(1 x =
(x(x) ax(x)) P(D 1 X x 1 = +B X= Z 20.
(-)
-(--)+ + E|DYE U,X = x, 20) X x, 2
= 2
=0
(30)
-(--) E(D U, -x, ===] =u] E| U,, = =x = 20] X Iz 2 =0
(---)+ +B (P(D = U,X r, 20) E|
U, =| X x, 20]
a(x) E P(D = U =, == 20) ( U = x| - (x)) X x. 7 20
The first line comes from the definition, while the second line holds by the consistency between the observed label and the true label (DY, ) and the linearity of conditional expectation. The third line holds by iterated law of expectation, and the fourth line holds by Assumption 3.1 (D T Y X, U). The fifth line follows by Assumption 3.2 U, X x, Z = z). The last line again follows
(Z I. Y X) and the fact that E[D U, X x, Z = =] = (P by the linearity and the iterated law of expectation.
Recall that Assumption 5.1 states that E U, x² (xxx)) almost surely, along with Equation (30) and the fact that PP U, X x, Z =0) 2 0, we have
(x)) 2 (x) Vo X.
Similarly, we can show that (xxxx= S (x() for every fixed x E X. We therefore complete the proof.
Proof of Theorem 5.3. To simplify the notation, for any classifier t: X' + [K] and vector function n 8 [0, 1]K define the function
K
A(L, Σ (x)
(T(rg (Tar max ()(x)) = k) T[(()) k]) 0.
kE(K]
The worst-case risk function can then be written
R(1)= E max A(t, ny x] yES
with = (n E [0, 1] |l7lla = 1, E [4,, un], h = 1, I...., K}. The following proof will rely on computing the maximization A(t, q: x) over all possible values of t(x) [K] for any fixed x e X.
Step 1. We start with the case when ((x) kn for some ko E [K], we have
{ ACC, m) I(t(a)) ko) max {
(A(,,m:)) Ift(x) =kot
max nES
nES
{{ Σ (x)
(arg max (m)) = k:) Σ (x( l1t(z) -k)) -1((()) -ko}}
max nES
kE(K]
PE[K]
kE(K]
{(
Σ
Th (x) Marg max (x)) = k) nho (x)) [(((x)) ko)}
max mES
pE[K]
kE[K]
21

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Given any vector m/x)) E S, we denote Po arg pa(p (2(x) the label with maximal conditional probability. We have
max 7ES
(A(t. 1(t(x))
ko) max
{ (1no
(1)) ((t(x)) ko}
wES
(31)
{(hoo (2) - mio
(x)(o)) (x)) } I[t(xx) = -ko) 2 0,
max
pozka.neS
where (=)+ = max(2,0) 0) for any real-valued z. In the second equality Equation (31), we exclude the case when
Po Kg from the maximization, as this situation only occurs when the lower bound of mи. (z) exceeds the upper bound of (1) for all p + kg. Consequently, we have po arg maxpe]K] (p(x)) = Ko. which implies that
max Po Po=Ro.NES
x)) [[t(z) = ko) Po Po=
(1Kkg (x) 17 (x))) I(t(x)) koo = 0.
Therefore, we expect the maximization of A(t, m7: 2) Ift(z)= = kob over E S to be non-negative. We exclude the case ki from the maximization to facilitate further analysis.
Step 2. As shown in Equation (31), for any fixed x E X and po & ku, the term (Npo (2) Teo (z))) + is non-decreasing (t) function of Up (x) and non-increasing (J) function of 17K (r). Therefore, one may expect that the maximization of (2)) (I))+ over nT(r) E S(x) is realized when Tpu (z) and The (x) achieving their upper-bound and lower-bound respectively. However, due to the constraint ||?(()]|| = for any x E X, the orginal upper-bound up. (2) for 7p (x)
may not be reached, and similar concern arises when treating Thk (x)). To fix these issues, we define a "realizable" upper-bound for 1p (I) as
pp (z)
[
b(0)
A Upo (x),
(32)
which is the maximal value that Mpp (x) can realize under the constraint ΣME(K] [x( = 1. Meanwhile, we define a "realizable" lower-bound for The (I) as
Tho (x) = ilpo (I)) -
Σ u5(xs)
v 1ko (x))
= {[1 (1- Σ 1((x))
Σ ug(z)) (11 [1- (x)
Σ us(c)) (x)
popo
jo
jo
(33)
(100(()) +
Σ (1((x) -u,(x))) v [1- Σ us(co)} V (x)
ko
jzko
Σ
us (x(x)) v 1ko (z).
ko
The last equality is established as (xx) uz(x) < 0 for any j E [K], leading to the fact that (a (x) + Σ Eoppo.h (x(x)
(xxx)] < INo (z). In Equation (33), we replace the upper-bound Upo (z) with uno (I) in the definition of (a (x), because in Equation (31), the lowest possible values of πı. (z) depends on the "realizable" maximal value of 1p. (x). However, notice that Te, (x) does not depend on the label Po involved in the definition, indicating that the "realizable" lower-bound is an intrinsic property for the conditional probability for each ko E [K]. Similar statement can be applied for the "realizable" bound ūμ. (z) for each Ay E [K].
Step 3. Back to the maximization of A(I, x))) I[((x)) = koO in Equation (31), we have
{ All. I(((x)) koo WE
(nho (x)) - 1/kk (xr) [T((x))) -io
max
max PoRkoneS
(34)
(izr((z) - Tan (2z) + Ift(x) = -kot-
max Po
By defining
Wko (x) = max
(ipo(x)) - - (2:)
Po
22

---

Learning with Selectively Labeled Data from Multiple Decision-makers
the weight function corresponding the event (1(x)) Ko). the Equation (34) be written
{A(t.m=)) 1(t(z)= ko} wko (x) [[((x)) ko
max (x))
The worst-case excess risk (() can then be written as
Re(t) =
max nES
Σ
X(t,m;))-Ittt = kob
k[E[K]
max -)) -IIU(X - } WES
AoE[K]
E
Who (X) 1(t(X) kob
koE|K]
The second inequality holds because (t(x)) ko ki [K] defines sequence of disjoint events for every fixed
X. By replacing the subscript ku with k complete the proof.
Step 4. We now left to check whether there exists vector 1) S such that the second equality in Equation (34) is guaranteed, that is, there is indeed a feasible solution of ny()) with 17po (I)) = pn (z), Mea (x) = T (x) such that
[|]())] = 1 and (x) E (x), uy (x)] for every E [K]. Before we go deep into the details, the non-emptyness of set S reminds us that, for every x E EX
Σ uz(x). JE(K]
(35)
JE[K]
In the following, we check the feasibility of E S for a fixed x E X' in three aspects.
1. For 1/po (x) po (ar), check 7p (1) E (x)) Upo (x)). (2r),
For the upper-bound by the definition of up (x)) in Equation (32), 1pp (2) S Up(2)) is guaranteed.
For the lower-bound, on one hand, if pp (ar) "p (1r) then Upo (x)) 2 1po (x) naturally holds. On the other hand, suppose upo (x) = Eistro (x:). By Equation (35), we have 2 ΣxE[Ky (xx), which suggests that Uno (x)) 2 po (1r). Hence, upo (x) 2 po (ar) always holds.
For 1/ke, (x) Tho (w)), check T/s (1) [AAo (x), uno (x:]. For the lower-bound, by the definition of LAD (z) in Equation (33), Thk (x) 2 4ag (I) always holds.
For the upper-bound by Equation (33), we have
- [1- -x) Σ us(x)]
I (x)).
jtko
Equation (35) ensures that 1 - E Ejtko 2y (x) < uko (x). and on the other hand (no (x) S uxo (I) simply holds. Therefore, we establish the upper-bound 7i, (z) I uko (z).
3. Check [|](=]]] = 1. We start with computing the summation
Tp (I) + Vik (x:) = u (x) + Teo (z).
If the summation stays with in the capacity region [1 Eipmyo (2(2), 1- Σ Enepo (,(2)] we can always find a series of feasible solutions n, (z) E (z)( [x) for j # Po- ko such that E)E[K] Th (2) = 1 is satisfied. The discussions are summarized below.
(a) Suppose upo (x) < 1 - po (r(x), by the definition of ūno (x) in Equation (32), we have up (x) = Uno (1)
and Tho (x) = [1 - E, i uj [x)] V tNo (æ). We then have
uz(x),
Σ Uz(x)
(Case 1)
upo (x) + (x))
Upo (x) + 400 (x), if4
Σ uy
(Case 2).
jo
23

---

Learning with Selectively Labeled Data from Multiple Decision-makers
For the Case 1, we can simply let (x) uy (x) for Po, Ko. and this arrangement fulfills the requirement ΣjE[K] m5 (2r) 1. For the Case 2, we have
ug(x)= S upo (2) + Les (1) S1
E ((x).
jo
As a result, there exists a sequence of (n)(()) iitpoooo such that 17522) E (x)(),, uy(x)) for all j # Po, ko that
satisifes Upo (x) + 400 (x) Eo 72 75(2) =1,
(b) Suppose upo (x) 2 1 Ejero (2),, we then have upo (x) = =1 Ey 4(x) and
[x) = [[1 [1- upu (x)
E u)(x)] 42 (x)
= INoo (2r) +
Σ - V (z)
j#ko.Po
= 40 (z),
where the last equality holds because (x(x) uz(x) for all j E [K]. Therefore, we have
Upo (x) + (2) = E 4(2).
Ro
As a result, we can simply let (2)x)) 15(x) for j + po, ko. and this arrangement agains fullfills the requirement Σje(k] (15()) 1.
The above analysis show that validity of the second equality in Equation (34).
Proof of Theorem 5.3 (Binary Classification Setting). Recall from the first part of Theorem 5.3 that
R(1)= = E (x) T(((X)= k}}
where
{ (in((t)) - [x(x0) +}. p
wx(()= = max
Consider the binary case when Y E {-1,1} and t: + {-1, 13. Recall that in Theorem 5.2, we derive the partial bound
for vi (a:) = = X x) [4 (I), ui (zr). By the constraint ni (xx + 7 (ar) = 1 for each X, we define the partial bound [-1 (z), ==)(z)] for (x) (x) as (z(z) = 1 2n (z) and v-1(z) 1 - (x).
We can then compute the "realizable" upper- and lower-bounds for both my (x) and n/ (z) as below:
(=(x) = (1--1-1) (1))-(x)) A (x) = u1 and ū=((x) = (1 (z)) ( (=) 11-14 41 (zx),
(xx) (1 (z) = (x) and ()(x) (1 ()))(((11)))))))))01 V((z)) = 1- (u)(x)
The weight functions (x) for A: = +1 are therefore
w1 (x) = (ūo(x) - [x)))* = (1 (1-22
(z)) = (1- (1)()) 114(x) s 1/2] (2u1 (I) - 1) = (2u, (x) - 1) ((r(()) 2 1/2).
wo = - (z))))(
Hence, in binary outcome case, the risk function R(t) takes the form
R(t)= = | (X) T,00)//2 T(((X)==-))))))) = 1) + 22, (X) - 1| (X)(1/1 T(((X)= = 03]
= E (X)
(x)) (1 - L[t(XX= 0}) + |2u1 (X) 11 (x)21/2 l[(((X) o3}
= E 2x)
(x) + E Ift(X) 1} (120) (X) (X) - 1| II, - |1 1-24(()) (((())1112)
1 t(x(( ((2n((X) 1/ [,, 11 11-20 2x)x (1(0)5112))
B 21 (x) (1/(2) E
=
2
24

---

Learning with Selectively Labeled Data from Multiple Decision-makers
For every fixed X, define weight function
w(x)= == (z) 1/2 - - 1/2) [4(x)) 1/2 14((x) 1/2)
max (u1(X) - 1/2,0) + min -
we then have
R(t) E [ 2x)( (X((X) < 1/2] +B (x(w(()) (1 (1- -(x))
(a0)
(**) + E (X)) E - ((X) +(X)
(**) + EE [X) + E [x)xX] w(n[-w(X]] ((x))
(36)
= (**) + E [x) + (x)) 2 sgn (x)] # t( {(x} - 1)
(**) + E2 -
- (Xx + 2E |o0 (X) [((gnn| w X)] * sgn sgn[m(X)))
For any fixed æ, notice that wxx) - [w(x)] 0 when w(x) 2 0 and w(x) w(x)] 2w(x) when w(x) O, we then have
B (X() |x( TF (x)( [(w((() < 0]]
18 (12 1| -f (x) 2 1} |1 (x)( -14)))) < 1/23) -[w(X) <0}
(1)
Consequently, by observing the establishment of the event
(XX) < 0
+ [2u1 11 I( (X) 2 1/2] < (1(2) ((4()) < 1/2),
the first two term in Equation (36) can be further organized as
E - 2/1 (X)) (x) < 1/2] - E wXX) - [x(i]]
E 221 (X) - 1| (X) 2 1/2)]. if wX) < 0
(37)
E 1 21 (x)) -11)))(((()))) < <1/2)].
if wf)(X) 2
- min (R]i - 21, 2x) (X) < 1/23] B 22n ( -I|-I(u(X) 2 1/2]1).
Finally, we define
Partial (x) = 2w((x) = max (2u1 (X) 1,0) + min (Xl 1,0)
for every x E X. Combining Equations (36) and (37) together, we have
R(h) = partial (X) -1 [T(sgn| (u: partial (X)) # (x))]
(8 (11-22(())) 2x)) (X) < (2u 11 (x)(()) 2 1/2H)
min
B.4. Comparisons of Point and Partial Identification
Point identification hinges on decision-makers' homogeneity in their use of unobservables, as defined by the generalized NUCEM assumption in Theorem 4.3. Concretely, the conditional irrelevant of Cov(D, Z X, X,U) and E|y; X,U] given X reflects the uniformity of decision-makerss reliance unobserved information. Conversely, partial identification benefits from the heterogeneity of decision-matee
use of observables X, not requiring the homogeneity of selection on unobservables U. This approach uses IV partial bounds that consider variations in the decision rules P(D = 1 X, Z) and the labeled probabilities P(Y = k. D = 1 X, Z) across decision-makers Z. Such heterogeneity helps construct tighter bounds for 7i. (x) Moreover, we having the following claims.
25

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Theorem B.2. The partial bounds (x) and ug(x) in Theorem 5.2 are achieved by the most lenient and most stringent decision-makers, respectively.
We claim that for any fixed X and U, the lower-bound is achieved by the most lenient decision-maker and the upper-bound is achieved by the most stringent decision-maker. To see this, notice that the lower-bound for nig with respect to decision-maker Z = j in Theorem 5.2 satisfies
Proof of Theorem B.2.
(xx,2) == [[DY; + (x) (1 - D) -
E DY? (X) (1 (1-D) D) = ==
| = -E[P(D - E U,X,2 +ax(X) PLD = = U;X, X 2, =
-E[EDE + (X) - (1 (1-D) U,XX2 - =
x, 2 =
ax) + E P(D U, (E xxU]-a(())) xx= 1x=2,Z=1]
The second equality holds consistency, and the third equality follows by iterated law of expectation. The fourth equality holds by Assumption 3.1 and the final equality is established by the IV independence in Assumption 3.2 (Z 1 (U, YU, XX). Note that the Assumption 5.1 states as (X) < E X, UJ I (xx almost surely, the lower bound 1 (2,, 2) is an increasing function of decision rule PPD = U, X, Z z). Therefore, for any fixed X and U, the maximization over lower bounds ma (xx 2) is achieved by the most lenient decision-maker with the highest decision rule P(D = 1 X, U, 2 = 2), that is,
(x) max 2x)
max a& (x) + P(D U,X, 2) (E X, X, U] - ox (X)) Xx = x 262
a (x) + E
max P 2)} (E X,U] ax(x)) X
2E2
Similarly, for the upper-bound the minimization minze(m] 4y (I. 2) is achieved by the most stringent maker when X and U are fixed.
26

---

Learning with Selectively Labeled Data from Multiple Decision-makers
C. Supplements for Unified Cost-sensitive Learning
Proof of Theorem 6.1. To facilitate the analysis, for fixed weight function w - IR and score function 4: X + RRK we define the class labels
Ko = arg min (z) and Ay == arg max (2))
ke[K]
kE(K]
Namely, when E is fixed, Ko denotes the class label with the minimal weight Wky (4)) while kn corresponds the class label with the highest score hy., (2)). According to the definition of cost-sensitive classification risk R.(h, w) in Equation (11),
define the cost- classification loss
2(h, w;
wk (arg max (x))) = kj.
PE|R]
Obviously, the excess classification risk can be written as R(h, w) inf R(h, w) = E (1h, wx X) inf ((h, we X)] = E [wk, (X) Wkk (x)].
Correspondingly, we define the cost-sensitive surrogate loss for Rexp (h, w) in Equation (12) as
Σ wx(x) exp(hx(x))
K
texp wi x) =
Σ K
p=1 exp(hp(x))
As result, the excess surrogate risk can be written
Rexp (h, w) - inf Rexp(h, w) E Mexp w; X) - inf lexp (h, w; X)]. h
h
Therefore, we are left analyze the excess surrogate loss leep(tt (h, w; x) inf,, leep (h, wi x) for every fixed æ X.
Following the idea of (Mao et al., 2023), for every fixed scored function h X R& define new function h" induced by some realevalued parameter y as follow: for fixed x E X,
h (x) (z),
k + ko. ki
h (z) = log ( (exp(hxx (x)) - 1))
k = ko
hg, (x) log (exp(hee (z:) + -1), k = kn-
Since the domain of log function is (0, +oo), we should restrict the value of to ensure that exp(hu, (x)) + + > 0 and exp(ha, (x)) - 4 > 0. Therefore, for fixed æ X. we define the feasible region of μ as
M(n) = {u E R: exp(hi (x)) exp(hua (x))}.
direct consequence above definition is that ΣK exp(hx(x)) Σ -= exp the surrogate loss 1(h!, w; takes the form
exp (h' (x)) for every fixed x. Consequently,
wk wx(x) exp(hx(x)) + Wh, (x) exp(ium (z)) - / + wkn (x)
exp(hea (x)) + μ
lexp (ft", w;x) x) = Σ
ER exp(hp(ar)
Σ exp(hp(z))
EKe exp(hp (x))
k
Now, the excess surrogate loss Lexp (h, w; x)- - inf lexp (h, wi x) can be lower-bounded by
lexp w;,)) inf Lexp (h, w;
2 hexp (h, w; nEM(N)
inf lexp(1t w;x)
Why (x) exp(hnn (x)) - exp(1uno (x)) - + wko (x)
(xp(hoo(x)) - exp(he, (x)) + 1 EØ exp(1p(ax)
= sup wEM(j)
E exp(1t(aa)
(Wk, (x) Who (x)) exp(hs,, (x:) - (xp(l)s,()))
= suu HEM(j)
Ex exp(hp(x))
27

---

Learning with Selectively Labeled Data from Multiple Decision-makers
The first inequality holds by the fact that the infimum of I over set M(n) is always greater then the infimum of h over all measurable functions. Notice that kg is the class label with the minimal weight, we have wi, (x) wko 2 0 for any Consequentyy, the supremum of the above expression is achieved when μ exp(he (r)), and the excess surrogate loss is therefore lower-bounded by
texp (h, wi x) inf texp (h, w; x) 2 (wk,. (2)) - -wkk (x)) exp(Nin (x)
Σø exp(hp(z))
1
2 Uk),, (x) 1 -kk (x))
K [(h, w;x) - inf [(h, w: x)
The last inequality follows by the definition that & is the class label with the highest score hag, and therefore we must have exp(hi,, (x)) 2 for any fixed x E X. By taking the expectation over X on the both sides, we completes the proof.
Ep-1 exp(bp(x))
Proof of Proposition 6.2. For the weighted classification risk R(h, w). if we choose h(x) = w(z) for X, we simply have Rh, w) = O, and this suggests the Bayes optimal risk equals to zero, that is, inf, R(h, w) = 0. Therefore, the excess weighted classification risk can be written as
Rh,, w) inf R(h, w) R(h, w) 0 = [[[[(()) M(sgn [xx)] # sgn (wo x)1) h
Here we use the fact that h² (x) has the same sign as weight function w(xx) for any fixed x E X. For the girisk introduce in Equation (13), we consider the following surrogate loss functions:
Hinge loss
Φ(a) max a, 0}
logistic loss : ((a) = log(1 + =
exponential loss (aa)) = e
Notice that for any & E (Hinge, logisticc.xponeeeiiieeeiiieieeei exponential). the surrogate loss ((a) is lower-bounded (in fact, inf, Φ(a) = 0), then we have inf, E[o(a(X))) = Elinf, ((a(X)]] = 0. Therefore, the excess ø-risk takes the form
(h, w) - inf (h, w) = Ro w) - 0 = E [w((X) <(((X) sgn[w(X)])]
h
In the sequel, we only need to check if the surrogate loss o(h(x) w(x)) provides an upper-bound for the 0 loss [[sgu[h(<)) # sgn[w(xx)}} for each é in the set (Hinge, logistic, exponential]. We fix the weight function w and the observed features x E X' in the following discussion.
Consider the case when sgn [x() sgn [w)x,, we then have 1(sgn h(x) + sgn[w(x))} 1. For the d-risk, we have
o (h(x) sgn[w(>))) = =<-1h(x)))
for any & (Hinge, logistic, exponential). Concretely, we have
Hinge (-1h(x))) (1+ h(x)))++++++)))))))))))))) 2 1,
Plogistic ( -[h(z))) = loog + elb(rrl)) 2 1,
-1((x))) (-1onn)) = -!(((²)] > 1.
@exponential
Therefore, we have for any & E (Hinge, logistic, exponential].
@(h(x) sgn sg)(w(x))) ((ggn/h(hhh [xx] + sgn[w(x))}
28

---

Learning with Selectively Labeled Data from Multiple mecision-makers
Consider the when sgn [ax) sgn [w(x)), then have [sgn h(x)) A sgn [x]]][ O. For the ø-risk, we have
(h(z) sg)[w(>)]] <(h(2)))
for any & E (Hinge, logistic, exponential). Concretely, we have
Hinge (1((x)) = (1 [k(x))) + 2 0,
(logisticc in (I((x))) 1ogg + e [b(x))) 2 0,
Pexponential (I(()))) --1((x)] 2
Hence, have
<(h(z)
.gn sgn (x)))) 2 I[sgn[h [h(x)] + sgn[w(>)]]
for any @ E (Hinge, logistic, exponential).
Finally, by multiplying the common weight [w(X)] and taking the expectation over X, we conclude that when weight function w fixed, the excess ø-risk is always an upper-bound for the excess weighted risk for any (Hinge, logistic, logisti,,ciooonneeeeeeeeee exponential):
Rh w) - inf Rs, w) 2 R(h, w) inf R,,,, w).
h
h
29

---

Learning with Selectively Labeled Data from Multiple Decision-makers
D. Generalization Error Bound
In this section, we theoretically analyze the performance of the UCL algorithm in Algorithm by deriving a generalization emorr bound for the output score function h. Specifically, Theorem 6.1 establishes a calibration bound for the cost-sensitive excess risk Rh) innf (h) induced by the output score function. To leverage this result, we first derive generalization emror bound for the excess surrogate risk Rexp (h) infRcH Rexp (h).
To facilitate the analysis, we define the surrogate risk induced by the estimated weight functions w from batch / E [K]
exp(hx(X))
Rexp (h, i0 ")
E
2pmr exp(h,
The below lemma provides decomposition of the upper-bound of the excess surrogate risk into two components: the estimation error of the nuisance functions {wr. } and the empirical process error.
Lemma D.1. The excess surrogate risk {HH) == Rexp(() inf Rexp(h) satisfies
E(H) -
2 L 1=1
sup hcH
Rexp (h, T Rexp (h, w)
+
2
Σ
sup Rexp (h, w Rexp(h, (h, w!!) nCH
L 1=1
Nuisance Estimation
Empirical Process Error
The first term in Lemma D.1 captures the error arising from the estimation of the unknown weight function w, which is evaluated on the true excess surrogate risk with the supremum over all h E H. The second term reflects the error incurred by the estimated score function h, evaluated as the supremum of an empirical process. To bound these two terms, we need to further specify the estimation errors of the nuisance estimators, as we will do in Assumptions D.2 and D.3.
Assumption D.2 (Nuisances Estimation). We assume that the true weight functions { ) and their estimates [1]]
1 ]==1 satisfy the following conditions:
1. they are uniformly bounded by some constant Cw over X. namely, || < Ow |1 loo < Cw for all A E [K] and E [L];
2. there exists 7 > 0 such that
10 11 (() w (X)I) V
|| K Assumption D.2 requires that the nuisance functions { and their estimates {w] Jkmi are uniformly bounded over the feature space X' and that the estimation error of the nuisance functions decays at a rate of O(N-7) for some 7 >> 0.
Assumption D.3 (Function Class Complexity). Let Cy > 0 and r > O be some constants. For any score function candidate E H. we assume ||/ lox < C₁ for any E [K]. Moreover, assume that the e-bracketing number H with respect to the metric p, denoted as (e, H. p). satisfies log (e,
, H. p) S - for any E (0, 1) and some T < 2.
In Assumption D.3, we further restrict the complexity of the hypothesis class H by imposing the boundedness on each component of score function h, and limiting the growth rate of its covering number. The boundedness condition is reasonable, as if any component of score function, say hus goes to infinity, then we cannot get reasonable classifier by the arg min operations. At the same time, limiting the growth rate of covering number is common way quantify the complexity of function class in statistical learning theory (Massrtt & Nédélec, 2006; Shalev-Shwartz & Ben-David, 2014; Wainwright, 2019).
Nuisance Estimation Error To provide finie--smple error bound for the estimation error, we start with bounding the nuisance estimation error introduced in Lemma D.I.
Proposition D.4 (Nuisance Estimation Error). Suppose Assumption D.2 and Assumption D.3 hold. We have, for any I E [4].
sup Rexp (h, ) - Rexp (h, w) O(N-)). NCH
30

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Empirical Process Error We now consider bounding the supremum of empirical process introduced in Lemma D.1. We focus on analyzing the empirical process define on the I-th batch, that is,
K
exp(hx(X.)) Ep= exp(h,(X.))
exp(hx((X) Σp=1 exp(h,(X))
]
Rexp (h. (h. Rexp (h, (h,
E
l
L1l
K
iET, R=1
As the cross-fitting batch size I, involved in Algorithm is usually smaller than the sample size N, here we simply assume /mm| R N. Note that, the estimated weight function in the I-th batch wh a random variable which relies on observed variables (Y, D, Z). To facilitate our analysis, we denote a new variable V DY, Z) over the domain V = D X x Z with some joint distribution Pv. We will omit the superscript [4] for simplicity in the sequel. For every given estimates {w) k=1 we define excess surrogate risk class Fu
K
exp(h& (x)))
/hEn H
Fn Fr:=
fh 1
(38)
K E cxp (2)(
To simplify our analysis, shorthand notation Pf B[f(V) and PNf 2/4 N f(V)). where PN is the empirical measured associated with the i.i.d. sample of size N. Then the supermom of empirical process can be written
Pxf - Pfll=u = sup Pnf Pf = sup Rs (h, w) - (h, w).
(39)
feJx
hEH
Therefore, our goal is now provide uniform bound for the empirical process Px. - Pf over function class Fx.. To realize this target, we shall notice that F& is a uniformly bounded class, that is, for any J E Fr, we have ||/ == sup.ev f(v) being bounded. To see this, notice that in Assumption D.2, we assume 1xllox = suprex 2x(2) < C. for any k [K]. Consequently, we have
[f(e)| = Σ (x(T) (x)(
K
K
exp(hi((z)
Wp (x)
Σ/ exp(h)(z))
ΣØ exp(h,((x))
k=1
k=1
exp(()((r))
Wh (a:)
Eper exp(hp(x))
km
$ KC == Cj.
Now, given a sequence of i.i.d. sample (W,..., WN], we define the empirical Rademacher complexity with respect class FH
N
RN(FHH) = E,
sup FEFR
Σ f(W.)
(40)
where (01....,ON N is a vector of i.idd. Rademacher variables takin values in {-1,+1} with equal probability. The empirical Rademacher complexity provides an upper bound for the supremum of empirical process in Equation (39). See the lemma below.
Lemma D.5 (Symmetrization Bound, Wainwright (2019) Theorem 4.10). For the Cy-uniformly bounded class of function FH. , with probability at least 1 8, have
2log(1/8)
|Pws - Pfllsx S (2 + +Cy
N
Define the norm (2())) for the function ʃ E FH such that ||S - gll <2(W)) = V EE (S(V)) - =(V))) for any function f.g E Fr. As the function class Fx is Cy-uniormmly bounded, we then have
sup || - gllea(PN) S 2C,.
1.9EFn
Moreover, let (e, L2(w)) be the covering number of class F& with respect to the metric induced by the (2(Px) norm. According to the definition of Fu in Equation (38), we have A (c,, Fu, Lz(Pw)) s Mcc, H, L2(Pr)). Along with the limitation of the growing rate of (e, H. L2(p))) in Assumption D.3, we establish the following Dudley's 's entropy integral for the empirical Rademacher complexity defined in Equation (40)
31

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Lemma D.6 (Dudley's Entropy Integral). Assume Assumplion D.3 holds. Given that sup - 2lx))(Px) 2
there exists a constant Co > such that the empirical Rademacher complexity is almost surely upper-bounded by the Dudely's y integral: 0 < < <
Co f20) VN 0 Clc
Co
20;
2Ca(2C,) 1-72 -
{
N-1/2
2-T
Given the establishment of Assumption D.3, we can now provide generalization error bound for the empirical process error in Lemma D.1 by combining Lemma D.5 and Lemma D.6: with probability at least have
sup hEH
Rexp (h, (h, w) Rexp (,, x)} PPPbf PfllF - (1g
(41)
Generalization Error Bound for Excess Cost-sensitive Risk Combining with the calibration bound in Theorem 6.1, the decomposition error of the excess surrogate risk in Lemma D.I, the nuisance estimation error Proposition D.4, and the empirical process error Equation (41), we can now provide a generalization error bound for original the excess cost-sensitive risk R(h) infΛcH R(h) induced by the output score function h in Algorithm 1, Formally speaking, we probability at least 1 - 6, we have
R(h, w) inf R(h, w) = O(K max {N-T,N- vlog(1/8)) }) hEH
(42)
This result shows that the excess cost-sensitive risk of the output score function h converges to the optimal risk at of K N-1/22 which is the standard rate for the multiclass classification risk in statistical learning theory (Massart & Nédélec, 2006; Shalev-Shwartz & Ben-David, 2014; Wainwright, 2019).
D.1. Remaining Proofs
Proof of Lemma D.I. Let h2 E H denote the best-in-class function that minimizes the excess surrogate risk Rexxp (h, w). We use w denote the true weight function and llll representes its estiamte from batch / E [4]. By defi- nition, we have
(H)) = Rexxp(h (h,, w) - Rexp (lije w)
Rexp(ho ())
1
Σ
Rexp (hi wlll) +
1 Σ
Rexp (h, wl
1 Σ
Resp (h, wll)
1=1
1=1
1-1
1
1.
Rexp (h, (.""ll)))
Rexp (1ige ")
Rexp (hips wdll)) Rexp (1ip w.
+
L
4
R Rexp (h, w) - Rexp (h, w))
Σ
Rexp (h, 1ll) - Rexp (h, a6 m011
<
sup NEW
+
sup heR
L
1=1
1=1
Nuisance Estimation
Empirical Process
32

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Proof of Proposition D.4. Notice that for any function h E H and batch E [Z].
K
exp(h (X))
Rexp (h, (ol!) Rexp(h w)
E
(x)
-x((
p=1 exp(hi(XX))
K
K
exp(hu (X))
E
(x)
(x) - =xx(x))
> exp (xp(()((x))
exp(hx((X))
(x) wxx())
IE
E exp(1x((X))
K
IE
(x(() wa wx(x
= E xx( wxx
The first inequality comes from the fact that the absolute value function is convex and we use Jensen's inequality, The second inequality follows from Cauchy-Sehwarz Schwarz inequality, and the third inequality follows from the fact that the softmax function is uniformly bounded by for all x E X' and H. Finally, combining with Assumption D.2 and the results above, we have for every batch E [Z]
Rexp(h, (ol!) - Rexp (h, w) = =ONN7)
sup bEH
33

---

Learning with Selectively Labeled Data from Multiple Decision-makers
E. Supplement to Numeric Experiments
E.1. Synthetic Dataset
In this section, we construct a synthetic dataset with multi-valued selective labels. The experiment results are illustrated in Figures and 5, which show that our unified oest-sensitive learning (UCL) can achieve superior performance under various strength of selection bias.
Data Generating Process Consider dataset consisting of observable variables X X2, ... Xp). and an unob-
servable variable U (U1, U2..... ..)... following the joint Gaussian distribution. We also introduce the variable Z that represents the random assignment of decision-makers which is uniformly drawn from the set 2 .1. J). The missingness decision D E {0, } is modeled as Bernoulli distributed variables with parameters pD == IP(D = =1 X, U, 2), and the true label Y* E {1...., , }} is modeled as a categorical variable with parameters ps := P(Y = X, U, Z) for k E [K] The complete data generating process is summarized in Equation (43).
.,,
Observed variables:
X (X1. ........ Xp) 2-N Z ~~ Uniform ((lior,, J})
Unobserved variables:
U (U1, UU)) 2.
Coefficients:
Wx-Y li+ pxk iE [I....,
p}:
k {I...., K]
WU-Y | k] qxk
ie (1......h
k (1....., K}
WX-D [2 --1 pxl
iE (l......p,
(43)
WU+D = [1 + 9x1
ie (1..... .4}.
Decision (NUCEM):
PD (1 aD) expit (Z- 2XW X-D) + aD - expit (3UWe-D],
Decision (UC);
PD = expit {(1-au) aal-ap) aD) Z 2X tap 3UWU-D).
Outcome:
Pk = softmax {11 - σr) XWx x- +ay 4UWu-y), kE (1,.....
Y- = Cate
Here we define the functions expit 4 1/(1 + exp(-v)) and softmax : V H exp(v)/ / exp(ux) for any vector V E K In both UC and NUCEM models, the parameter op E (0, 1) controls the impact of unobservable variables U on the probability missingness Pp. while the parameter ay E (0, 1) adjust the magnitude of U affecting the distribution of outcome y Overall, the pair of (aD, ay) jointly determine the degree of selection bias in our data generating process.
In this experiment, we simulate a full dataset with sample size N 10000, feature dimensions p = q q= 5, the number of instruments level J = 5, and the label classes K- = 3. Each data point in the dataset is tuple {(X,, U, Zí. D,,Y," Y The observed dataset consists of a tuple of variables [(X;, Z,, D., Y with Y; == Yr if D; = 1 and Y; == NaN if D, = 0 for each i E [N].
Model UC and NUCEM The missingness model NUCEM captures one of the setting of No Unmeasured Common Effect Modifier, and this ensures the satisfaction of sufficient condition in Proposition A. and therefore the conditional probabilities {p can be exactly identified according Theorem 4.3. Meanwhile, the model UC captures general setting of Unmeasured Confounding which the point-identifictiin condition cannot be realized in this situation.
Baseline Methods and Our Proposed Methods We divide our dataset into two parts: training set and testing set, using 7:3 split ratio, denoted as Syain and Sest- In the training set, five different meta-learing methods are trained on selectively labeled data, using simple neural network classifer with softmax output layer. We then evaluate the performance of these methods on the testing set with fully labeled data. The five methods under consideration are as follows:
The first two methods act baselines. The SelectedSample method involves running multiclass classification algorithm solely on the labeled portion of the training set {i Stain D, 1). For the second method, SelectedSumple((PW) we firstly estimate the inverse propensity weighting (IPW) for the labeled subset, and then implement the weighted multiclass classification for the labeled training set. These baseline methods establish a "lower bound" for any other meta learning algorithm, as any enhanced method with the use of selectively labeled data should least beat the performance of these two methods.
34

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Accuracy Scores of NUCEM Models
Confounding Strength: Y=0.3, Dm0.3
Confounding Strength: Y=0.3, Dm0.5
Confounding Strength: Y=0.3, D=0.7
0.80
0cc2/icccnnnn Accursc)
0.70
0.60
0.45
Selected Sample
Selected Sample (PW)
Fulf Sumple
Portial Learning
Point Learinn
Selacted Sample
Selected Sample (Pe)
Full Sample
Portial Learting
Point Loaning
Selected Sample
Selected Sample opw)
Full Sample
Partial Leaning
Point Learing
Mathods
Methods
Metheds
Confounding Strength: Y=0.5,
Confounding Strength: Y=d.5,
Confounding Strength: Y=0.5, D=0.7
0.50
0.70
Caziiiction ACCUSSC
0.60
0.55
0.45
Selected Sample
Selested Somele (PW)
Full Sample
Partial Learning
Point Learnng
Selected Sanple
Selected Somple (Pen
Full Sample
Partial Learning
Pobit Leaming
Selected Sample
Selected Samole (pw)
Full Samste
Partisl Leaming
Point Learning
Methods
Methods
Confounding Strength:
Confounding Strength:
Strength:
0.50
0.30
Classlicctin ACU/ac)
0.65
0.55
0.45
0.40
Selected Sample
Selected Sample DPWN
Full Semple
Pertial leaming
Point Leaming
Selected Saraple
Selected Sampla (PWn Full Samuta
Portial Leaming
Hoint Leaming
Selected Sampla
Sedected Sample (1P8) Full Sample
Partial Leaming
Point Leariing
Methads
Methods
Methods
Figure 4. The testing accuracy of different methods with ay (0.33 0.7) and ap E (0.3, 0.5, 0.7) of Model NUCEM in synthetic dataset.
35

---

Learning with Selectively Labeled Data from Multiple Decision-makers
The third method, FullSample, runs multiclass classification algorithm on the entire training set. This represents an ideal but impractical scenario since we cannot actually observe the true label Y;" for the missing data (where D; 0). This method serves as an 'upper bound' for learning performance, indicating the highest possible effectiveness if full information were available.
Finally, our two proposed methods correspond to the point- and partial- identification settings, named Poining and PartialLearning respectively. We anticipate that the performance of these methods will fall between the established "lower" and "upper" bounds, representing a realistic estimation of effectiveness under selective label conditions. Similar to the method SelectedSample((PW)) our method involve estimating series of weight functions Wk, k = 1,..., K to correct for selection bias (refers to the details in Section 6). In this experiment, we estimate these weght functions using Histogram Gradient Boosting with 5-fold cross-fitted approach. We selected all hyperparameter through 5-fold cross-validation. The cost- sensitenn classification problem is solved by simple neural network with softmax output layer.
The Role of Observed Variable Z different roles in these methods. In our proposed method, Z is treated as an instrumental variable, aiding in correcting for selection bias, while in the baseline methods (SelectedSample, SelectedSampl((PPW)) and FullSample), Z is only one of the observed features.
It's important to note the random assignment of decision-maker, denoted as Z, play
Experiment Results Figures 4 and report the testing accuracy of each method on the data generated by the NUCEM and UC models in Equation (43) respectively. All the experiments are repeated 100 times with confounding strengths ODD Cty E (0.3, 0.5, 0.7). Each boxplot then shows the distribution of the testing accuracy for distinct methods under different combinations of confounding strength ap and ay.
Transition from the top to the bottom panel, ay increases from 0.3 to 0.7, indicating a stronger influence of the unobservable variable U on the true label Y*. As we can see from Figures 4 and 5, the accuracy of each of five methods decreases as ay increases, reflecting the growing challenge in accurately predicting outcomes as the influence of unobservable factors intensifies. Moreover, transition from the left to the right panel, on rises from 0.3 to 0.7, indicating an enhanced role of the unobservable variable U in determining the missingness decision D. A larger value of ap within the range (0, 1) suggests that the missingness decision D predominantly influenced by the unobservable U, hinting at a potential larger difference of the distribution among selected group and missing group. This visually corroborated in Figures 4 and 5, where the performance disparity between the SelectedSample and FullSample methods widens as o. increases, illustrating the growing challenge in correcting the selection bias.
The results in Figures 4 and 5 demonstrate the effectiveness of our proposed methods in handling selection bias in the data generating process. In each combinations of ,ap), our Partialleearning method consistently outperforms the baseline methods, including the SelectedSample and SelectedSample((PP)) methods. Moreover, the perforamnce of PartialLearning close to the FullSample method, which is the upper bound of the performance. The performance of the PrintLearnie method is also competitive, although it slightly less robust than the PartialLearning method. The results in Figure 4 are consistent with those in Figure 5, except that under this setting, the point identification requirement in Theorem 4.3 is not satisfied, and the PointLearning method is therefore less effective than the PartialLearning method.
Below we provide detailed analysis of the performance of each method.
SelectedSample(PPW)) As we see from Figures 4 and 5, the performance of the SelectiveSample(PP)) approach is close to the baseline of naively running multiclass classification algorithms on the selected subsample (named SelectedSample), and it is outperformed by our proposed algorithms. This is not surprising since the propensity score P(D - 1| 2) cannot correct selection bias due to the existence of unobserved variables U.
PointLeariing:: Our proposed PointLearning method shows promising results in the bottom right panel of Figure 4 with parameter (ay, an) = (0.7,0.7), in which case the unobserved confounding strength is large. Although the NUCEM model in Equation (43) satisfies Proposition A. which enables the point identification of the conditional probabilities and therefore the classification risk R(h, w), PointLearning does not outperform the baseline methods when the unmeasured confounding strength is not so large. This limitation is attributed to the complexities involved in K accurately estimating the weight function { as outlined in Equation (6).
36

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Accuracy Scores of UC Models
Confounding Strength: Y=0.3, Dm0.3
Confounding Strength: Y=0.3, Dm0.5
Confounding Strength: Y=0.3, Dm0.7
0.80
0cci/iccconnn Accursc)
0.70
0.60
0.45
Selected Sample
Selected Sample (PW)
Fulf Sumple
Portial Learning
Point Learnnn
Selacted Sample
Selected Sample (Pe)
Full Sample
Portial Learning
Point Leaning
Selected Sample
Selected Sample opw)
Full Sample
Partial Leaning
Point Loaming
Methods
Methods
Metheds
Confounding Strength: Y=0.5,
Confounding Strength: Y=d.5,
Confounding Strength: Y=0.5, D=0.7
0.50
0,70
Caziiicttoo ACCUSSC
0.60
0.55
0.45
Selected Sample
Selested Somele (PW)
Full Sample
Partial Learnin
Leaming
Selected Sample
Selected Somple (Pen
Full Sample
Partial Learning
Pobit Leaming
Selected Sample
Selected Samole (pw)
full Samste
Partisl Leamnng
Point Learning
Methods
Methods
Confounding Strength:
Confounding Strength:
Strength:
0.50
0.30
Clasalicttin ACU/ac)
0.65
0.60
0.55
0.45
0.40
Selected Sample
Selected Sample DPWN
Full Semple
Pertial leaming
Point Leaming
Selected Saraple
Selected Sampla (PWn Full Samuta
Portial Leaming
Hoint Leaming
Selected Sumpla
Sedected Sample (1P8) Full Samuli
Partial Leaming
Point Leariing
Methads
Methods
Methods
Figure 5. The testing accuracy of different methods with ay E (0.3,0.5.007) and ap (0.3, 0.5, 0.7) under Model UC of synthetic dataset.
37

---

Learning with Selectively Labeled Data from Multiple Decision-makers
The crux of the challenge lies in estimating the ratio of two conditional covariances, CDv,DY, Z X) and Cov (D, Z X) for each & E [K]. Estimating conditional covariances is inherently more difficult than estimating conditional expectations, primarily because the process of calculating the ratio of these estimates is fraught with potential inaccuracies. If the denominator is not precisely estimated, the resultant ratio can become unstable, leading to exaggerated or diminished values. Such inaccuracies can severely impact the effectiveness of the downstream cost- sensitive classification, undermining the robustness of Point Learning under these conditions.
Partiallearning: The cornerstone of our learning framework is Partiallearming. As evidenced by the graphs in Figures 4 and 5, Partiallearning significantly enhances the accuracy of performance predictions while maintaining low variance, showcasing its potential for real-world applications. Remarkably, this improvement in prediction accuracy is consistent across almost all combinations of confounding strengths (ay, ap)), as well as the decision models NUCEM and UC.
Reflecting on the conditions outlined in Theorem 5.2, PartialLearning only requires the conditional mean function B|yg | U,X = x]. k = 1,.... K to be almost surely bounded, aside from the basic instrumental variable (IV) conditions. This requirement is generally more feasible in real-world scenarios than the point-identification assumptions detailed in Theorem (referenced as Theorem 4.3). The success of PurtialLearning can be attributed to two key strategies: Firstly, we adopt robust optimization approach to develop a prediction rule that remains effective under the least favorable conditions of 1)" (X), detailed in our minimax risk function formulation (see Equation (10)). Secondly, the weighting functions {wx J 1- are based on the summation of several conditional expectations, which is inherently more stable than the ratio of conditional covariances required for point identification.
K
Overall, the compelling performance of Partiall earning demonstrated in Figures 4 and convinces us of its practical viability. It stands as a reliable method that consistently outperforms baseline approaches, even in situations where the presence of selection bias (missing not at random) in the data generating process is uncertain.
E.2. Sensitivity Analysis of Weight Function Estimation
The accuracy of weight estimation can directly impact the performance of our method. In fact, our learning guarantee in Appendix D already captures this. The excess risk bound in Equation (42) involves a term capturing the weight estimation error. Notably, the weights to be estimated are different for the point and partial identification settings. Estimating the weight for point identification involves estimating two nuisances and their ratio. In contrast, the weight in the partial identification only involves the sum of series of nuisance functions and does not involve any ratio. The latter is generally more insensitive to the nuisance estimation error.
To illustrate the impact of weight estimation accuracy, we implement additional experiments using synthetic data with confounding strength ap = 0.5 and ay = 0.7 on both the NUCEM and UC settings (see details in Equation (43)). To introduce controlled errors into the nuisance function estimates, we inject Gaussian noise as follows:
T(x,) = x(X.) o ((O,
We vary the noise level a across the values (0.0,3.0, 5.0, 7.0] and repeat each experiment 50 times. Based on the perturbed nuisance estimates
estimates--seciffcallyy specifically, the conditional probability ny in the point identification setting, and the bounds (xx) and (x) in the partial identification setting- we compute corresponding weights and analyze their influence on downstream classification accuracy.
Our results in Table show that inaccuracies in weight estimation degrade classification performance for both PointLearning and Partiall earming Nevertheless, the performance of both methods remains stable under small perturbations (a < 0.3) in both the NUCEM and UC settings. Notably, PartialLearning achieves higher accuracy across most of noise levels, demonstrating greater robustness to errors in nuisance estimation.
E.3. Semi-synthetic Dataset: FICO
In this section, we evaluate the performance of our proposed algorithm in a semi-synthetic experiment based on the home loans dataset from (FICO, 2018). This dataset consists of 10459 observations of approved home loan applications. The dataset records whether the applicant repays the loan within 90 days overdue, which we view as the true label Y* E {0, 1). and various transaction information of the bank account. The dataset also includes a variable called ExternalRisk, which is a
38

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Settings
Methods
o 0.0
= 0.3
0 = 0.5
0.7
NUCEM
Point Learning
0.601 (0.0124)
0.592 (0.0161)
0.586 (0.0212)
0.534 (0.0381)
Partial Learning
0.607 (0.0121)
0.592 (0.0196)
0.564 (0.0277)
0.549 (0.0343)
UC
Point Learning
0.553 (0.0241)
0.561 (0.0232)
0.559 (0.0235)
0.439 (0.0604)
Partial Learning
0.602 (0.0136)
0.586 (0.0188)
0.559 (0.0300)
0.533 (0.0370)
Table 1. The testing accuracy of point learning and partial learning under NUCEM and UC settings with different noise level 00.0,0.3.00 0.7].
Accuracy Scores (Model NUCEM)
LoglsticRegression
FandomForest
GradientBoesting
AdsEoost
Confounding Strength: 0.5
Confounding Strength: 0.7
Confeunding Strength:
0.750
0.725
0.700
Clociliccroon Accursc)
0.675
0.650
0.625
0.600
Sedeectdd Sample
Selected Sample (PM)
full Sample
Partaa Lawr ning
Poine Laurning
Sedecced Sample
Selecced Sample (IP))
Full Samole
Partial Loaning
Polot Lewminn
Selected Sample
Selected Sample (P90)
Full Sample
Partial Leaming
Polst Learnnng
Methods
Methoes
Methods
Figure 6. The testing accuracy of methods with a E {0.5, 0.9) for model NUCEM in FICO datasct.
risk score assigned to each application by a proprietary algorithm. We consider ExternalRisk and all transaction features as the observed features X.
Semi-synthetic Dataset with Selective Labels In this dataset the label of interest fully observed, so we choose to synthetically create selective labels on top of the dataset. Specifically, we simulate 10 decision- (e.g.. bank officers who handle the loan applications) and randomly assign one to each case. We simulate the decision D from Bernoulli distribution with success rate PD that depends on an "unobservable" variable U, the decision-make identity Z, and the ExtemalRisk variable (which serves as an algorithmic assistance to human decision-making We blind the true label Y* for observations with D = 0. Specifically, we construct U as the residual from a random forest regression of Y with respect to X over the whole dataset, which is naturally dependent with Y*. We then specify PD = P(D = 1 X, U) according to
Decision (NUCEM): PD = a expit ( } + (1 - a) expit (1 + Z) ExternalRisk],
(44)
(UC): PD = expit/a a U (1 - a)) (1+ 2) ExternalRisk].
Here the expit function is given by expit(t) the labeling process and thus the degree of selection bias. We can easily verify that the sufficient condition in Proposition A. is guaranteed and therefore the voint-identificatinn of classification risk R(h, w) is realizable under the NUCEM model in Equation (44).
cxp((tt) The parameter op E (0, 1) controls the impact of U on
Baseline Methods and Our Proposed Methods We randomly split our data into training and and testing sets at a 7 3 ratio, Similar to what we discuss in Appendix 1. on the training set, we apply five types of different methods: Selected Sample, SelectedSample(1PW) FullSample, PointLearning and PartialLerrnig. The first three methods serve as the benchmark of the last two methods. For each type of method, we try multiple classification algorithms including AdaBoost, Gradient
39

---

Learning with Selectively Labeled Data from Multiple Decision-makers
Accuracy Scores (Model UC)
Logicikcoonnssionn
SVM
RondomForest
GrodknnBeoccing
AdoBoost
Confounding Strength: 0.5
Confounding Strength:
Confounding ng Strength:
0.75
0.73
0.70
00
Cussifatton Accuasyy
0.60
0.65-
0
00
0
0.50
0.55
Selected Sample
Seleczed Sampla (Pen)
Full Sample
Pamall Learning
Point Leamnng
Seincted Sample
Seleccad Sampla (een
Fue Sample
Partial Leaming
Point Leaming
Seiected Sample
Selected Sempta (eee
Full Sampl
Partial Leaming
Point Learning
Methads
Methods
Mechods
Figure 7. The testing accuracy of methods with E 0.,, for model UC in FICO datasct.
Boosting, Logistic Regression, Random Forest, and SVM. Our proposed method also need to estimate some unknown weight functions, which we implement by K 5 fold cross-fitted Gradient Boosting. Again, all hyperparameters are chosen via 5-fold cross-validation, and we evaluate the classification accuracy of the resulting classifiers on the testing data.
Similarly, we remark that the decision-maker assignment Z plays different roles in different methods. Our proposed methods (PointLearning and PartialLearning) treatment the cecision-makerr assignment 2 as an instrumental variable to correct for selection bias. In contrast, the baseline methods (SelectedSample, SelectiveSample(IP)) and FullSample) do not necessarily need Z. However, for a fair comparison between our proposals and the baselines, we still incorporate Z as a classification feature in the baseline methods, so they also use the information of Z.
Results and Discussions Figures 6 and presents the testing accuracy of each method over 50 experiment replications for (0.5, 0.7, 0.9) under both the NUCEM and UC models defined in Equation (44). First, observe that the performance of SelectedSSmple((PPW) is comparable to the baseline SelectedSample, which applies binary classification algorithms directly to selectively labeled data. Notably, as the strength of unmeasured confounding (a increases, the gains from using our proposed methods especillyy PartialLearnigg-vver the baseline methods (SelectedSample and SelectedSample((PW) become more pronounced. Interestingly, the PartialLearning method outperforms even under the NUCEM model, where the point-identification condition is satisfied. As discussed in Appendix E. 1, this may be because the PointLeurning method relies on estimating a conditional variance ratio, which challenging to estimate accurately in practice. In contrast, the Partiallearming method requires only the estimation of conditional expectations, making it more stable and robust. This highlights the advantage of the PartialLearning method: it is robust to violations of the point-identification assumption and achieves more stable performance even when point-identification holds.
To summarize, among all the methods we evaluated, PartialLearning emerges as a reliable approach that consistently outperforms baseline methods, even in scenarios where the unobsreved confounding is strong.
40


Reviews:
[{"review_id": "BktFimnBli", "reviewer": "Reviewer_as5X", "summary": "This paper focuses on the problem setting of classification with selective labeled data, that is, the labeled data at hand can be biased because of decision-making in the past. This paper defines the problem mathematically and solves this problem from the perspective of the instrumental variable (IV) framework. There are two assumption settings: (1) No unmeasured common effect modifiers (NUCEM), which is a strong assumption that leads to a clean solution, and (2) Partial identification, where a reasonable solution can be obtained. Theoretical analyses of two assumption settings are provided. Furthermore, a practical algorithm for both cases is also provided based on weighted empirical risk minimization with calibration guarantee. Synthetic experiments show that the proposed method outperforms baselines.\n\n## update after rebuttal\nAfter the rebuttal, I still think the idea of this paper is novel. It studies the problem setting extensively theoretically and also provides experimental results., Thus, I keep my score (4: accept). The authors clarified in the rebuttal that their work has novelty and also admits some current drawbacks of their methods (e.g., computation time).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your insightful comments and positive feedback for our work. \n\n- Computational Cost: The computational cost of our method is higher than vanilla method which directly learn a classifier from the observed (selectively labeled) data. That is because our method consists of two steps: The first step is estimation of nuisance functions through a cross-fitting technique, which are used to construct the classification weights; The second step is a weighted / cost-sensitive classification procedure, which can be efficiently solved. The nuisance estimation indeed entails some additional computational costs. But this typically only involves a series of standard regression/classification fitting. This is usually manageable and also widely adopted in the causal inference literature (Chernozhukov et al., 2018). Moreover, this can be accelerated by fitting the nuisances on different folds of data in parallel. We will clarify the computational aspect in our revision.\n\n- Weight Estimation Accuracy: The accuracy of weight estimation can directly impact the performance of our method. In fact, our learning guarantee in Appendix E already captures this. Our excess risk bound in that part involves a term capture the weight estimation error.  Notably, the weights to be estimated are different for the point and partial identification settings. Estimating the weight for point identification involves estimating two nuisances and their ratio. In contrast, the weight in the partial identification only involves the sum of a series of nuisance functions and does not involve any ratio. The latter is generally more insensitive to the nuisance estimation error. \nDuring the rebuttal period, we conducted some additional experiments for the simulation setting with confounding strength $\\alpha_Y=0.5$ and $\\alpha_D = 0.7$ (see setting details in Appendix F) to assess the impact of nuisance estimation error. \nWe introduced Gaussian noise into the estimates of nuisance functions to inflate their errors, defined as $\\tilde{\\eta}(X_i) = \\hat{\\eta}(X_i) \\cdot [1 + \\sigma^2 \\mathcal{N}(0,1)]$ with noise levels $ \\sigma = \\{0.0, 1.0, 2.0, 3.0, 4.0 \\}$. The experiment is repeated for 10 times. We then computed weights based on these noisy estimates and analyzed their effect on resulting classification accuracy. Our findings reveal that both partial and point learning remain stable under small perturbations.        \nHowever, beyond a certain noise threshold, performance degrades significantly. Notably, partial learning exhibits higher tolerance ($\\sigma=4.0$) compared to point learning ($\\sigma=2.0$). This demonstrates that the partial learning approach is indeed more resilient to nuisance estimation errors. \nIn our revision, we will clarify the impact of nuisance estimation errors and add the extra numerical results.\n\n- First Work to Use IV for the Selective Labels Problem: Thank you for your suggestion on emphasizing the novelty of our work. Previous literature on the selective labels problem (SLP) also leverages the random assignments of heterogeneous decision-makers but their approaches are largely heuristic, as discussed in Appendix A. Our work uses the IV framework to provide principled point and partial identification analyses and derive rigorous learning algorithms. \nWe remark that a closely related work by Rambachan et al. (2023) also considers IV-based partial identification in the context of selective label problem. However, our work is substantially different from theirs and makes many unique contributions. Please see our detailed responses to reviewer aAyP. While we already mentioned these in our paper, we will further highlight them in our revision.", "claims_and_evidence": "1. Strong theoretical results for a problem setting that is quite complicated and has practical relevance.\n2. Experimental results show effectiveness of the proposed practical algorithm.", "methods_and_evaluation_criteria": "Since the problem setting is quite complicated, I believe there does not exist a benchmark dataset that directly corresponds to this problem. This justifies the use of synthetic datasets that this paper decided to do.", "theoretical_claims": "The proposed method looks reasonable to me. The theoretical claims are sound in my understanding.", "experimental_designs_or_analyses": "Experimental designs and analyses are valid.", "relation_to_broader_scientific_literature": "The paper is related to selective labels problems, where it has been discussed in appendix. It might be also similar to weakly supervised learning or domain adaptation in the sense that the observed labeled dataset has something different from the test distribution and we have to use information at hand somehow to derive a risk minimizer for the test distribution using observed training information.", "essential_references_not_discussed": "No additional requests from me.", "other_strengths_and_weaknesses": "Strengths\n1. Strong theoretical results that improve an understanding of a complicated yet relevant problem setting. It is praiseworthy that this paper not only focuses on a restrictive NUCEM assumption but also considers the partial information assumption.\n2. Practical algorithms with theoretical guarantee are provided, which can be relatively easy to implement. \n3. Experimental results (although synthetic) show that the proposed method is effective compared with reasonable baselines.\n\nWeaknesses\n1. Proposed method's weakness is not much discussed in my understanding. One might be that it could be computationally expensive (I'm not sure). Moreover, the estimation of weight could be incorrect, and we don't see much effect in the experiments, whether this can make the proposed method not work well. I find the comment in the paper, why NUCEM lost to partial under NUCEM assumption quite interesting that NUCEM requires a ratio estimation. I think such discussions could be useful. Or ablation study of the effect of imprecise weight estimation could also be useful. (but I'm also aware that the paper is already dense unfortunately).", "other_comments_or_suggestions": "The paper is quite dense already, but it would be better to explain more about related work in the main body if possible to highlight the novelty of the proposed work as well as reviewing prior work to the reader. \n\nLine 110 (left): if8 -> if\nLine 1523: conseuqnece  -> consequence\nLine 1995: Vairable -> Variable", "questions_for_authors": "1. Could you please comment on the comparison of the computational cost of the proposed unified cost-sensitive learning (point), (partial), and vanilla training?\n2. Since many weights have to be estimated, how important is the accuracy of weight estimation? Is the solution highly sensitive to this?\n3. Is this the first work to use instrumental variable (IV) framework for selective labeled classification?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TvOL6VEPxE", "reviewer": "Reviewer_Ye3n", "summary": "This paper studies multiclass classification with selectively labeled data, where label distribution is biased due to historical decision-making. By leveraging variations in decision rules across multiple decision-makers, the authors apply an instrumental variable (IV) framework to establish necessary and sufficient conditions for exact classification risk identification. When exact identification is infeasible, they derive sharp partial risk bounds. To mitigate label selection bias, the paper proposes a unified cost-sensitive learning (UCL) approach.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable feedback and your references. Our work indeed builds on these previous literature and is therefore closely related to them. However, our work is not “a special case of these prior works”. Instead, our work significantly generalizes these existing literature and makes contributions beyond them. Below we provide detailed explanations, which we will also clarify in our revised version.\n\n- The Exact Identification in Cui and Tchetgen (2021). They study policy learning under unmeasured confounding using IV, focusing on a binary IV and binary treatment. They aim to learn a confounding robust treatment rule that maps features to a binary treatment. This is more like a binary classification problem with causal structure. In contrast, our work considers a multi-valued IV and a multi-class label, aiming to learn a classification rule that maps features to a multi-class label. This setting strictly generalizes their framework.\nNotably, their identifying NUCEM assumption involves the difference of certain conditional expectations given the two different IV values. This heavily relies on the binary nature of IV. Instead, we consider a more general assumption that can tackle general IV $Z$. Moreover, their learning procedure only uses hinge loss but we explore more surrogate losses for both binary and multi-class classification. \n\n- The Partial Identification in Pu and Zhang (2021). They explore policy learning under unmeasured confounding with a binary-valued IV, binary treatment, and binary outcome, again learning a robust treatment rule that maps features to a binary treatment. In contrast, we consider multi-valued IVs and multi-class labels.\nPu and Zhang (2021) directly uses Balke and Pearl’s partial bounds for the binary IV and binary outcome setting. We extend these bound to accommodate multi-valued IVs and any bounded multi-class outcomes (see Assumption 4.1). Moreover, we rigorously prove the tightness of our IV-based partial identification bounds (Appendix C.1), which to our knowledge is new to the literature. Pu and Zhang (2021) also considers minimax learning. Their inner maximization problem can be easily solved in closed-form for the binary outcome and their final minimization is based on hinge surrogate loss. However, we consider multi-class classification where the inner maximization involves much more complex simplex constraints. We managed to give a closed-form solution by carefully analyzing the problem structure. \n\n- Contextual bandits in Bietti et al. (2021). This paper conducts an empirical analysis of several algorithms for online contextual bandits, which studies a fundamentally different problem from ours. We acknowledge that cost-sensitive classification and surrogate losses are not new problem ideas. But we hope to clarify that our contribution lies in in-depth analyses that transform the problems in both point and partial identification settings into a unified cost-sensitive classification form. Under our general framework, we can explore a range of different surrogate losses while Cui and Tchetgen (2021) and Pu and Zhang (2021) focus on only the hinge loss.\n\nWe now further respond to your other comments.\n\n- Efficiency bound under exact identification: We appreciate your suggestion but we think this is beyond the scope of our current paper. The main focus of this paper is to provide a unified learning framework for the selective label problem in both point and partial identification settings. As our work is dense already, we leave the efficiency bound for future study.\n\n- Extension from Discrete to Continuous Outcomes: Thanks for the great question. Extension from discrete to continuous outcomes is indeed an important problem but we think this should be left for a separate future study. \nNotably, all existing selective label literature focuses on binary outcomes (see references in Appendix A). Our study of multi-class outcomes already constitutes an extension. Moreover, as we discuss above, our work also strictly generalizes Cui and Tchetgen (2021) and Pu and Zhang (2021), instead of being their special cases with restricted outcomes. In our extensions of these prior literature, our paper overcomes many new technical challenges, generalizing many assumptions, analyses and results in these literature. \nFinally, we hope to briefly touch on the challenges with continuous outcome. Our partial identification analysis involves specifying some bounds $a_k(X)$ and $b_k(X)$ in Assumption 4.1. For classification problems, these can be naturally set as 0 and 1. But for continuous outcome, we may need to specify the range for $E[Y^* | X, U]$, which may has no natural ranges. Moreover, in solving the inner maximization problem, we heavily rely on the simplex structure of the constraints. But such structure no longer applies to continuous outcomes.", "claims_and_evidence": "Yes, the claims made in the submission supported by evidence.", "methods_and_evaluation_criteria": "Yes, methods and valuation criteria make sense for the problem or application at hand.", "theoretical_claims": "I did not thoroughly check each proof. However, most of the theoretical claims are not novel and have already been well-established in the literature. Additionally, they do not contradict my prior understanding.\n\n**Exact identification under IV**: Cui, Y. and Tchetgen Tchetgen, E., 2021. A semiparametric instrumental variable approach to optimal treatment regimes under endogeneity. Journal of the American Statistical Association, 116(533), pp.162-173.\n\n**Partial identification under IV**: Pu, H. and Zhang, B., 2021. Estimating optimal treatment rules with an instrumental variable: A partial identification learning approach. Journal of the Royal Statistical Society Series B: Statistical Methodology, 83(2), pp.318-345.\n\n**Cost-sensitive classification**: Bietti, A., Agarwal, A., and Langford, J., 2021. A contextual bandit bake-off. Journal of Machine Learning Research, 22.133, pp.1-49.", "experimental_designs_or_analyses": "Yes, it provides a semi-synthetic example.", "relation_to_broader_scientific_literature": "The contributions of this paper build upon existing work in instrumental variable (IV) methods and cost-sensitive classification. The theoretical foundations for exact identification under IV have been established by Cui and Tchetgen Tchetgen (2021), while partial identification under IV has been explored by Pu and Zhang (2021). The results in this paper can be seen as a special case of these prior works when the outcome is discrete. Additionally, cost-sensitive learning approaches, particularly in the context of contextual bandits, have been well studied, as highlighted by Bietti et al. (2021). While the paper applies these concepts to multiclass classification with selectively labeled data, its theoretical contributions largely align with existing literature rather than introducing fundamentally new insights.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "The paper primarily builds on existing theoretical frameworks for instrumental variable (IV) methods and cost-sensitive classification, with its results being a special case of prior work when the outcome is discrete. While it provides a structured application of these ideas to multiclass classification with selectively labeled data, the theoretical contributions do not introduce fundamentally new insights, as they closely align with well-established results in the literature.\n\nTo enhance its novelty, the paper could explore deeper theoretical results, such as deriving the efficiency bound for the risk function under exact identification.", "other_comments_or_suggestions": "No.", "questions_for_authors": "I wonder why the paper focuses only on discrete outcomes. Can the approach be easily extended to continuous variables? If so, why not establish a more general framework for decision-making that encompasses both cases?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n9SwkmJQZq", "reviewer": "Reviewer_aAyP", "summary": "The paper tackles the problem of correctly quantifying classification risk in the selectively labeled data setting. In this setting, true outcomes are only observed for samples that receive a certain classification/decision (e.g., default outcomes are only observed for those who are given the loan). To address this selection bias in observed outcome data, the paper proposes a framework that utilizes decision-maker pool heterogeneity to identify the true classification risk, under the assumption that the decision-maker is selected randomly for each sample.\n\nThe authors first characterize the requirements of the data-generating process that are necessary to exactly identify the classification risk in this setting. They note that these requirements are overly strong for real-world applications and discuss relaxations under which partial identification is possible. With a cost-sensitive learning approach, they train classifiers using the identified (exact or partial) risk and demonstrate the efficacy of a loan application dataset with synthetic decision-makers.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable feedback. We now address each of your comments below. \n\n- Evidence of (Quasi-)randomly Assigned Heterogeneous Decision-Makers: The selective label literature has mainly considered two examples for randomly assigned heterogeneous decision-makers: \n1. Judicial Decision-Making – In US, Judges are often randomly assigned to cases, yet they exhibit heterogeneous decision-making styles and biases (Kleinberg et al., 2018; Marcondes et al., 2019). This example is widely cited in the selective label literature.  \n2. Loan Approval – In fact, loan applications are also randomly assigned to different loan officers in some places. For example, there even exist platforms, such as OppFi (https://ortooapps.com/case-study/oppfi), that implements the random assignment to ensure fairness and equity. Even if the loan applications are not randomly assigned, they may be viewed as quasi-random as long as the loan officers roughly face the same distribution of applications given the observed features. Moreover, Bushman et al. (2021) demonstrate that individual loan officers significantly influence loan contract terms and performance, highlighting the heterogeneity across decision-makers.\n\n- Real-world Data: Kleinberg et al. (2018) indeed uses real-world data on all arrests made in New York City between 2008 and 2013, but the data are not publicly available. Existing selective label literature also considered a few other datasets. But unfortunately these are also not public. This is why we use synthetic or semi-synthetic data in our paper. However, we hope to clarify that synthetic data actually have advantages over real-world selective label data. This is because in the real data, the outcomes of the unlabeled units are unobservable so evaluating the results from a given algorithm is not straightforward. By using synthetic or semi-synthetic data, we do observe the true outcomes for all units so we can more easily assess different algorithms.\n\n- Decision-maker Assignment as IV: we understand your concern about the point identification assumption and your questioning the validity of view decision-maker assignment as IV. \nWe hope to clarify that the key defining characteristics of IV are exogeneity and exclusion restriction. These two are satisfied by the decision-maker assignment under our assumptions, and many existing selective label works also leverage these two properties in their heuristic solutions. In contrast, the homogeneity assumption (NUCEM assumption) is not the defining characteristic of IV. There exist many works on IV that does not require this assumption, such as the local average treatment effect (LATE) analysis in Angrist et al. (1996) and the Balk-Pearl partial identification bounds. \nMoreover, one purpose of our point identification is exactly to reveal that it needs strong assumption, which motivates our IV partial identification. In experiments, we do observe that the partial identification approach tends to perform better.\n\n- Comparison with Rambachan et al. (2023): The focus of Rambachan et al. (2023) differs fundamentally from ours. Their work primarily studies evaluating  various error measures  of a given binary classifier based on IV-based partial bounds, whereas we focus on learning a robust classification rule under both point and partial identification settings. We note that it is not clear how to optimize their error measure estimators to effectively train robust classifiers. In contrast, our work develops a unified cost-sensitive learning (UCL) algorithm for both point and partial identification settings. This requires in-depth analyses of the minimax formulation and cost-sensitive learning problems.  So their approach is not directly comparable to ours. We will further clarify this in our revision.\n\n- Specification of Range $a_k$ and $b_k$: In our experiments, we set $a_k(x) = 0$ and $b_k(x) = 1$ for all cases. The partial bounds $l_k(x)$ and $u_k(x)$ are then computed using the estimated nuisance functions along with the specified values of $a_k(x)$ and $b_k(x)$. These nuisance functions are learned from the observed data using the Gradient Boosting algorithm. We will clarify this point in future revisions.", "claims_and_evidence": "The main contribution of the paper is the framework to identify classification risk using decision-maker assignment as an IV. The authors claim that, in many real-world applications, decision-making usually involves several decision-makers and the choice of decision-maker for any unlabeled sample is often random. While this methodology is creative, I don’t think the paper does a satisfying job of justifying this claim either using prior work or empirical data. I note two concerns below.\n\n1. In terms of prior work, there is very limited discussion in the introduction to support this claim. The authors cite prior works that consider decision-maker heterogeneity in the judicial setting and discuss them in Appendix A. However, there’s no discussion of whether there's prior evidence for random decision-maker assignment and decision-maker heterogeneity in other domains (including the loan application domain that features prominently across the paper).\n\n2. For empirical analysis, the paper chooses to create synthetic decision-makers, which again makes me question the validity of random (or quasi-random) decision-maker assignments in real-world settings or the availability of data on who made which decision.", "methods_and_evaluation_criteria": "1. Regarding the methods employed to address the selectively labeled data problem, I like the broad idea the paper utilizes of employing an IV strategy to address selection bias using external factors that control the decision. However, I am not completely convinced that decision-maker assignment offers the best IV pathway, mainly because the paper shows that exact identification requires overly strict assumptions. In light of this restriction, I am curious about the realistic settings (and not just the simple ones noted on Page 4) where the authors think this method can still provide accurate estimates of classification risk.  \n\n2. For empirical analysis, the paper focuses on a loan-approval dataset, computing classification risk using the proposed framework in both exact and partial identification settings. Overall, it does seem to lead to more accurate classifiers than simple baselines. I am curious as to why the paper doesn’t compare their method to Rambachan et al. (even if limited to comparisons of risk evaluation using different methods) since they note that both papers consider the IV strategy to tackle the selectively labeled data problem. \n\n3. Additionally, considering that the empirical analysis is based on semi-synthetic data, it would be good to acknowledge the limitations of this analysis somewhere in the paper.", "theoretical_claims": "The theoretical claims made in the paper seem correct.", "experimental_designs_or_analyses": "The experimental analysis presented seems mostly sound, although it would be good to provide comparisons against other related works (e.g., Rambachan et al) if possible.\n\nOne point that I think needs more discussion in the empirical analysis is how the $a_k, b_k$ (and correspondingly $l_k, u_k$) are specified/learned in the partial learning experiments. Currently, I don't see any discussion on these parameters in Section 6 (let me know if its there and I am missing something) and considering its relevance to the partial identification setting it will be good to discuss how they are being set for the experiments.", "relation_to_broader_scientific_literature": "Overall, the paper definitely tackles an important problem of identification of prediction risk when the available outcome data is selectively labeled. The IV methodology of harnessing decision-maker heterogeneity is interesting and fits well (theoretically) with the decision-making setup of important real-world applications.\n\nHowever, as I noted above, there are doubts about the feasibility and practicality of the proposed framework which I believe severely limits the impact of the framework.", "essential_references_not_discussed": "The paper notes the main related works in this field. However, it's strange to have the entire related works section in the Appendix. Several citations discussed in the \"Selective Labels Problem\" setting are crucial for motivating the issues associated with selective label problems in real-world applications and would be helpful in contextualizing the problem setting for readers who are unfamiliar with this domain. \n\nI strongly suggest having at least a short related work section in the main body to include a discussion on the primary references.", "other_strengths_and_weaknesses": "The use of decision-maker assignment as an IV is creative and I wonder if it can also be considered as a potential intervention to ensure classification risk identification for future data collection procedures.", "other_comments_or_suggestions": "None", "questions_for_authors": "1. Are there prior works in multiple domains that provide evidence for the fact that decision-maker assignment is mostly random and that the decision-maker pool is heterogeneous?\n\n2. Is there real-world data available in any domain where decision-maker assignments are noted and where the proposed framework can be employed?\n\n3. Is it feasible to empirically compare the proposed framework to prior works (e.g., Rambachan et al) and, if so, does it achieve similar/better performance than prior works?\n\n4. How are parameters $(a_k, b_k)$ and $(l_k, u_k)$ specified/learned in the partial learning experiments?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper uses the instrumental variable framework from causal inference to analyze the problem of selectively having labels from multiple heterogeneous decision-makers. Though it leverages ideas similar to those of prior work, it differs by considering the general multiclass classification setting (multi IV and multi class) and general classification-calibrated losses in the binary setting. The paper analyzes the identifiability of classification risk using strong assumptions (No Unmeasured Common Effect Modifier) and partial identification under weaker assumptions. A cost-sensitive learning approach is then developed for learning in either setting that is then demonstrated on semi-synthetic data.

The theoretical analyses, practical algorithm, and (synthetic) experimental results in generalizations of previously-investigated settings are strengths of the paper.  Real-world feasibility of the approach, the limitations of semi-synthetic experiments, and the lack of comparative baselines are all weaknesses. Additionally, the reviewers suggest improvements for better organizing the paper (including moving related work discussion from the appendix to the body of the paper).

I concur with the averaged assessment of the reviewers and (weakly) recommend for acceptance.
Decision: Accept (poster)