A Unifying Post-Processing Framework for Multi-Objective Learn-to-Defer Problems
Authors: Mohammad-Amin Charusaie
Samira Samadi
Venue: NeurIPS 2024 poster (2024)
Keywords: Learn-to-Defer
Human-AI Teaming
Neyman-Pearson Lemma
Hypothesis Testing
Bayes Optimal
PAC Generalization
Primary area: learning_theory
TL;DR: Here, we obtain an optimal solution to multi-objective learn-to-defer problem by generalizing Neyman-Pearson lemma to multi-hypothesis setting

Abstract: Learn-to-Defer is a paradigm that enables learning algorithms to work not in isolation but as a team with human experts. In this paradigm, we permit the system to defer a subset of its tasks to the expert. Although there are currently systems that follow this paradigm and are designed to optimize the accuracy of the final human-AI team, the general methodology for developing such systems under a set of constraints (e.g., algorithmic fairness, expert intervention budget, defer of anomaly, etc.) remains largely unexplored. In this paper, using a d-dimensional generalization to the fundamental lemma of Neyman and Pearson (d-GNP), we obtain the Bayes optimal solution for learn-to-defer systems under various constraints. Furthermore, we design a generalizable algorithm to estimate that solution and apply this algorithm to the COMPAS, Hatespeech, and ACSIncome datasets. Our algorithm shows improvements in terms of constraint violation over a set of learn-to-defer baselines and can control multiple constraint violations at once. The use of d-GNP is beyond learn-to-defer applications and can potentially obtain a solution to decision-making problems with a set of controlled expected performance measures.

A Unifying Post-Processing Framework for Multi-Objective Learn-to-Defer Problems
Mohammad-Amin Charusaie
Samira Samadi
Max Planck Institute for Intelligent Systems
Max Planck Institute for Intelligent Systems Tuebingen, Germany
Tuebingen, Germany mcharusaie@tuubbngen..o
samira.. samadi @tuebingen mpg. de
Abstract
Learn-to-Dele is a paradigm that enables learning algorithms to work not in iso- lation but team with human experts. In this paradigm, we permit the system to defer subset of its tasks to the expert. Although there are currently systems that follow this paradigm and are designed optimize the accuracy of the final Al team, the general methodology for developing such systems under a set of constraints (e.g., algorithmic fairness, expert intervention budget, defer anomaly, etc.) remains largely unexplored. In this paper, using d-dimensional generalization to the fundamental lemma of Neyman and Pearson (d-GNP), we obtain the Bayes optimal solution for learn-to-defer systems under various con- straints. Furthermore, we design generalizable algorithm to estimate that solution and apply this algorithm to the COMPAS, Hatespeech, and ACSIncome datasets. Our algorithm shows improvements in terms of constraint violation over a set learn-to-dee to-neer- baselines and can control multiple constraint violations at once. The use d-GNP is beyond learn-to-defer applications and can potentially obtain a so- lution decision-making problems with set of controlled expected performance measures.
Introduction
Machine learning algorithms are increasingly used diverse fields, including critical applications. such as medical diagnostics [72) and predicting optimal prognostics [63]. To address the sensitivity of such tasks, existing approaches suggest keeping the human expert in the loop and using the machine learning prediction as advice [35 or playing supportive role by taking over the tasks on which
machine learning is uncertain (39 4). The abstention of the classifier making decisions, and letting the human expert do so, is where the paradigm of rearn-to-defer (L2D) started to exist.
The development of L.2D algorithms has mainly revolved around optimizing the accuracy of the final system under such paradigm [60 [50]. Although they achieve better accuracy than either the machine learning algorithm the human expert in isolation, these works provide inherently single-objective solutions to the L2D problem. In the critical tasks that are mentioned earlier, more often than not, face challenging multi-objective problem of ensuring the safety, algorithmic fairness, and practicality of the final solution. In such settings, we seek to limit the cost of incorrect decisions 46]. algorithmic biases [13. or human expert intervention [57], while optimizing the accuracy of the system. Although the seminal paper that introduced the first L2D algorithm targeted an instance of such multi-objective problem [44). general solution to such class of problems, besides specific examples (26] 57 51 (22, has remained unknown to date. Multi-objective machine learning extends
beyond the realm of L2D problems. prime example that is extensively studied in various settings ensuring algorithmic faimess [18] while optimizing accuracy. Recent advances in the algorithmic fairness literature have suggested the superiority of post-processing methodology for tackling this
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

suPAr ElL (h(x),
*
S.1. FIY, b(X), (()i 6
Munio
corshirm
(x)
(x)
V (x)
Evter
vy(x)
Velo)
Linear Comb notoon
Loiing +
Fine-tune
Prokid
=
true labels and expert decisions
Untzeddinng
Angmax
(ideer, honse), (roog Imig (dlog, bend).
(deer deer))
Figure I: Diagram of applying d-GNP to solve objetivb L2D problem. The role of randomness is neglected due to simplicity of presentation.
multi-objective problem 773 [4 20 76). Post-processing algorithms operate in two steps: first, they find a calibrated estimation of set of probability scores for each input via learning algorithms, and then they obtain the optimal predictor works, optimal algorithms to reject the decision decision-making under a variety of secondary objectives are determined via post-processing algorithms [ST [2]. which is in line with classical results such as Chow's rule [16] that is the simplest form of a post-processing method, thresholding the likelihood.
function of these scores. Similarly, in recent set of
Inspired by the above works, in this paper, we fully characterize the solution to multi-objective L,D problems using a processocns framework. In particular, we consider deferral system together with a set of conditional performance measures O o..... mn } that are functions of the system outcome Y. the target label Y, and the input X. The goal is to optimize the average value of Vo over data distribution while keeping the average value of the rest of performance measures V V,,..., Vm for all inputs under control. As an example, in binary classification, Vo be the 0 deferral loss function, while 1 can be the difference between positive prediction rates of Y for all instances of X that belong to demographic group A = 0 or A = 1. The solution for which we aim optimizes the accuracy while assuring that the demographic parity measure between the two groups bounded by a tolerance value 51 E [0, 1].
To provide the optimal solution, move beyond staged learning [12 methodology, in which the classifier h(x)) is trained in the absence of human decision-makers. and then the optimal rejection function r(x:) is obtained for that classifier to decide when the human expert should intervene (r(x) 1). Instead, we jointly obtain the classifier and rejection function. The reason that we avoid this methodology that firstly, objectives such algorithmic fairness are not compositional, i.c.. even if the classifier and the human are fair, due to the emergence of Yule's effect [62] the obtained deferral system not necessarily fair (see Appendix A). and in fact abstention systems can deter the algorithmic biases [36.. Secondly, the feasibility of constraints is not guaranteed under staged
learning methodology 74, e.g., there can be cases which achieving purely fair solution is impossible, while this occurs neither in vanilla classification 20 nor in our solution.
This paper shows that the joint learning of classifier and rejection function for finding the optimal multi-objective I 1.2D solution boils down to a generalization the fundamental Neyman-Peane Pearson lemma (55). This lemma is initially introduced in studying hypothesis testing problems and char- acterizes the most powerful test (i.c., the test with the highest true positive rate) while keeping the significance level (true negative rate) under control. As natural extension this paradigm, we con- sider a multi-hy multi-hyyothesiss setting where for each true positive prediction and false negative prediction, we receive a reward and loss, respectively. Then, we show that the extension of Seyymn--Peasooe lemma to this setting provides us with a solution for our multi-objective L2D problem.
In summary, the contribution of this paper below:
Section 3 we show that obtaining the optimal deterministic classifier and rejection function under a constraint is, in general, an NP-Hard problem, then

---

by introducing randomness, we rephrase the multi-objective L2D problem into a functional linear
programming.
In Section 4 we show that such linear programming problem is an instance of d-dimensional generalized Jeyman--Person (d-GNP) problem, then
we characterize the solution to d-GNP problem, and we particularly derive the corresponding parameters of the solution when the optimization is restricted by a single constraint.
In Section [S] we show that post-processing algorithm that is based on d-GNP solution generalizes in constraints and objective with the rate ((llogn/ n/n)1/2x, (log(1/c)nn)///p, ,'), respectively, with probability at least is the size of the set using which we fine-tune the algorithm, e' measures the accuracy of learned post-processing scores, and y is parameter that measures the sensitivity of the constraint the change of the predictor. Then,
n/n, Vlog(1/e)/n,, e²) and where
we show that the use of in in-processing methods in L2D problem does not necessarily generalize to the unobserved data, and finally
we experiment our post-processing algorithm on two tabular datasets and text dataset, and observe its performance compared to the baselines for ensuring demographic parity and equality of opportunity on final predictions.
Lastly, the d-GNP theorem has potential use cases beyond the L.D problem, particularly in vanilla classification problems under constraints. However, such applications are beyond the scope of this paper, and except for a brief explanation of the use of d-GNP in algorithmic fairness for multiclass classification, we leave them future works.
2 Related Works
Human and ML's collaboration in decision-making has been demonstrated to enhance the accuracy of final decisions compared to predictions that are made solely by humans or MI. [37 68 This overperformance is due to the ability estimate the accuracy and confidence of each agent on different regions of data and subsequently allocate instances between human and ML to optimize the overall accuracy (2). Since the introduction of the L2D problem. the implementation of its optimal rule has been the focus of interest in this field [8] [0 12
51
9 43 48 45). The multi-
objective classification with abstention problems is studied for specific objectives in 57 48
via in- propecesssing methods. The application of Neyman Neyman-Pearson lemma for learning problems with fairness criteria is recently introduced in (75).
We refer the reader to Appendix B for further discussion on related works.
3 Problem Setting
cecision-maaing Assume that we are given input features 2; E X' corresponding labels E E = [l...., the human expert decision m, for such input, and assume that these are i.i.d. realizations of random variables X, Y, M ~ f PXY M- Since there exists randomness in the human process, for the sake of generality, we treat M as a random variable similar to Y and do not assume that m; = m(::) for some function m. Further, assume that for the true label y and certain feature vector æ, the cost of incorrect predictions measured by a loss function l Arr h((=)) for the classifier prediction (xx)), and a loss function é Eu(y, m) for human's 's prediction m. The question that we tackle in this paper is the following: What is an optimal classifier and otherwise an optimal way of deferring The constraints
= ..l....,,...... and
the decision to the human when there are constraints that limit the above can be algorithmic fairness constraints (c.g., demographic parity, equality of opportunity, equalized odds), expert intervention constraints (e.g., when the human expert can classify up to b proportion of the data), or spatial constraints to enforce deferral on certain inputs, or any combination thereof.
Let us put the above question in a formal optimization form. To that end, let r(x) E {0, 1} be the rejection functior[] i.e., when r(z) = 0 the classifier makes the decision for input and otherwise is deferred to the expert. We obtain the deferral loss on x and given a label and the expert decision m
Las (y. m, ((())))))) + (1-r(=))(Ark) h(x)).
'The rejection here differs from hypothesis rejection and indicates that the classifier rejects making decision and defers the decision to the human expert.
3

---

Table 1: list of embedding functions corresponding to the constraints that are discussed in This list is version of the results in Appendix D when we assume that the input feature contains demographic group identifier A. To simplify the notations, we define ((A,y) v) =
Section 3
1a
Pr(Y=v.E=)) Pr(Y=v,A=0)
Name
Embedding Function (/)(2))
Accuracy
[Pr(Y = 0/z). ..... Pr(Y Pr(Y = M[x)
Expert Intervention Budget |57
00..... 0,1]
10....,0, 0, (x (2)
OOD Detection 53
(x)
PrYYALEG,,,X P.EEE))
ΣE
P a,Pr(EEG))
i= and Pr(YEG.|X=3 Pr(YEG.)
Long-Tail Classification 52
1,0
Bound on Type-K Error 69
Pr(Y=kla) Pr(Y k)
1, Pr + k,z)
Demographic Parity
28
Pr[A=1] Pr(A=D) 10, 1, PrMM 1 [x)]
TAst
Equality of Opportunity
34
((A, Pr(Y = 1 (x), Pr(M 1 1, = 1(x))
6(A, 1) Pr(Y = 1/r), Pr(M = 1, 1xx)
Equalized Odds 34
and
((A, ()prr( = 0)2), 0, Pr(M 0, Y 0/²)]
Therefore, we can find the average deferral loss on distribution μ as
L'der (h, r) Ex,Y [Caet (Y, M,X),
We aim find a randomized algorithm A that defines a probability distribution μ4 on H x R that solves the optimization problem
MAA E argmin A Li r)],
PA
s.t. Bxy. [ (X, M. (XM S
(2)
where V is a performance measure that induces the desired constraint in our optimization problem. We assume that V,, similar to Edet, is an outcome-dependent function, i.e., if the deferral occurs, the outcome of the classifier does not change V,, and otherwise, if deferral does not occur, the human decision does not change V, In other words, the value of the constraints can only be function of input feature x and of the deferral system prediction y = r(x) + (1 (())) Here, Ý is the expert decision when deferral occurs, and is the classifier decision otherwise.
Types of constraints. Before we discuss our methodology to solve (2). it is beneficial to review the types of constraints with which we are concerned: (1) expert intervention budget that can be written in form of Pr (r(X)= =1) S 8, limits the rejection function to defer up to N proportion of the instance,
(2) demographic parity that formulated as PPY 1/A 0) P(Ý 1|A 0)| < 8, ensures that the proportion of positive predictions for the first demographic group (A = 0) is comparable to that for the second demographic group (A 1). (3) equality of opportunity that is defined as
IPr(ý = 1|A 1,Y = 1) - Pr(Y A = 0, = 1)] S 8 limits the differences between correct positive predictions among two demographic groups, (4) equalized odds that is similar to equality of opportunity but targets the differences of correct positive and negative predictions among two
groups, i.c., max PPr(Y 1|A = 1, = 1) Pr(Ý = 1 = O, = y) < 8, (5) out-of- distribution (OOD) detection that is written as Proue (r(X) = 0) S å limits the prediction of the classifier on points that are outside its training distribution and incentivizes deferral in such cases, (6) long-tail classification deals with high class imbalances. This method aims to minimize balanced error of classifier prediction instances where deferral does not occur. Achieving this objective as

---

= 0jY E G,) when mentioned in [53] is equivalent to minimizing Ex= 1 Pr(Y * r(x),
the feasible set is Pr(r(X)=
Y E G;) K. and where {G: is partition of classes, and finally (7) type-k error bounds that is generalization of Type-I and Type-Il errors, limits errors of specific class k using Pr(Y * k|Y = k) < 6.
All above constraints are expected values of outcome-dependen functions (see Appendix D for proof). To put it informally, if we change the classifier outcome after the rejection, such constraints do not vary.
Linear Programming Equivalent to (2)
The outcome-dependence property helps to show that (see Appendix C obtaining the optimal classifier and rejection function is equivalent to obtaining the solution of
.f....., ..]. E arrmaax TE (X(()), th (X))), s.t. ([(()),, (.())) < &, E [1: m] (3)
SEAJ
where Ad is simplex of dimensions, d = L ++1 and th X' - Rd is defined as Y,,,,, W, Y, M, W. Y,M,
tb(())= = Ey,MIX= [
(4)
that we name the embedding functionn corresponding to the performance measure Vr for E [0 m]. where for simplifying the notation we define Vo Leet- Furthermore, the optimal algorithm obtained by predicting h(x) = i with normalized probability of of ( (z), where
E fj (z) * O, and rejecting r(z) = 1 with probability (z)). case of E ff()) the
classifier is defined arbitrarily. A list of embedding functions for the mentioned constraints and objectives is provided in Table (See Appendix for derivations).
Hardness. We first derive the following negative result for the optimal deterministic predictor in (
We use the similarity between (3) and 0-1 Knapsack problem (see [58 pp. 374]) to show that there are cases in which solving the former is equivalent to solving an NP-Hard problem. More particularly,
we assume that the distribution of X contains finite atoms 21. ................................ ................................
each of which have probability
of Pr(X- = æ;) = pi. and we set ei (z;) = [0, wi and voo (z:) = [0, pr
_i for 04, w; E IR+, then (
p. reduces in argmax E; (3;) )e; subjected to f X - {0, 1} and Σ, f (x;) S ,1, which is the main form of the Knapsack problem. In the following theorem, we show that a similar result can be obtained if we choose vho and e to be embedding functions corresponding to accuracy and expert intervention budget. All proofs of theorems can be found in the appendix.
Theorem 3.1 (NP-Hardness of (2). Let the human expert and the classifier induce 0 - losses and assume X' to be finite. Finding an optimal deterministic classifier and rejection function for bounded expert intervention budget is an NP-Haar problem.
Note that the above finding is different from the complexity results for deferral problems in [49 Theorem I] and [23 Theorem I]. NP-hardness results in these settings are consequences of restricting the search to specific space of models, i.e., the intersection of half-spaces and linear models on a subset of the data. However, in our theorem, the hardness arises due to a possibly complex data distribution and not because of the complex model space.
The above hardness theorem for deterministic predictors justifies our choice of using randomized algorithms to solve multi-objective I.2D. In the next section, by finding closed-form solution for the randomized algorithm, we show that such relaxation indeed simplifies the problem.
4 d-dimensional Generalization of Neyman-Pearson Lemma
The idea behind minimizing an expected error while keeping another expected error bounded is naturally related to the problem that is designed by Neyman and Pearson (55). They consider two hypotheses Ho, Hi as two distributions with density functions (z) and gı (x) for which given point can be drawn. Then, they maximize the probability of correctly rejecting Ho, while bounding
the probability of incorrectly rejecting Hg, i.c., for test T'xx E [0, 1] that rejects the null hypothesis when ((x) = 1, they solved the problem
Ex~g1 [[()]. s.t. Ex~g0 [T(X)] S a. TE(O,1
max
(5)
We named this an embedding function because it embeds the constraint or loss of the optimization problem into vector function.
5

---

They concluded that thresholding the likelihood ratio is a solution to the above problem. Formally.
they show that all optimal hypothesis tests take the value T(x) when (z)) > k and take the value T(x)= = 0 when 9n (r) (x()) < k. where & is a scalar and dependent on
Multi-hypotthsis testing with rewards. In this section, we aim to solve ( as a generalization of Neyman-Peane Peaasson lemma for binary testing to the case of multi-hypothhsis testing, in which correctly and incorrectly rejecting each hypothesis has a certain reward and loss. To clarify how the extension of this setting and the problem (3) are equivalent, assume the general case of d hypotheses Ho...., Ha-1, each of which corresponding to X being drawn from the density function gi (r) for receive i E fo..... d 1}. Further, assume that for each hypothesis H3, in case of true positive, the reward rz()), and in case of false negative, we receive the loss (z).. Assume that we aim to X' rejects d hypotheses, each hypothesis H;
find test f : X + Ad that for each input with probability - I (x) and maximizes a sum of true positive rewards, and that keeps the sum of false negative losses under control. Then, this is equivalent to argmax EiE Ex-s,
[ (z)))(
SEa
subjected to En= Ex
s 61 which in turns is equivalent to (a- ((()))((z))
(i(a))
(x(2)) 95(22)
argmax Ex go
Σ (x))(())) 1=0
go(z) s.t. E Xo
Σ 1=0
f (x)
Σ
S81. (6)
90 g0(z))
FEAT
iti
This problem can be seen as instance of (3) when we set vo(z) [ro(x),.... .............................. ra- 92-1 (w)
mn(m)
and t/1 (x) = [Σjyn (x) go(z) E Ej (xx) (()) Similarly, we can show that for all ()(r), 1/a (xx) in B there exists set of densities 91 (z), ..... (z)) and rewards and losses such that (6) and 33) are equivalent. This can be done by setting g, = go and noting that the mapping from 4s and r;8 into 4/n and t/2 is invertible.
(x(2)
The formulation of (3) can be seen as an extension of the setting in 669 when we move beyond type-k error bounds to general set of constraints. That work achieves the optimal test by applying strong duality on the Lagrangian form of the constrained optimization problem. However, we avoided using this approach in proving our solution, since finding f", and not the optimal objective, is possible via strong duality only when we know apriori that the Lagrangian has a single saddle point (for more details and fallacy of such approach, see Section E). As another improvement to the duality method, we not only find a solution to (3) but also show that there is no other solution that works as well as ours.
Before we express our solution in the following theorem, we define an import notation as an extension of the argmax function that helps us articulate the optimal predictor. In fact, we define
Ta = (T: x Rd + Ad
Σ
(r(x4 )) 1]
that is a set of functions that result in one-hot encoded argmax when there is a clear maximum, and otherwise, based on its second argument, results in a probability distribution on all components that achieved the maximum value.
Theorem 4.1 (d- (d-GNP). For a set of functions v. where i E [0, m). assume that (81....,8m) is an interior poin of the set F == (B((r(z), shi (x)),.. Bxr((x), the (x)I)) I E A Then, there is a set of fixed values ki,.... kim and r E Ta such that the predictor
- Σ ka))(t),
(8)
obtains the optimal solution of supreag B (()(()), (x)))))) subjected to the constraints being achieved tightly, i.e., when for i E [1 m] we have E (f(x),, v.()))] = 8, If ki.....,k. km are further non-negative, then (x) is the optimal solution to (3) Moreover, all optimal solutions of that tightly achieve the constraints are in form of (8) almost everywhere on X.
Example (I.21) with Demographic Parity). In the setting that we have deferral system and we aim for controlling demographic disparity under the tolerance 8, we can set v/((x) = [Pr(Y =
A point is an interior point of a set, if the contains open neighborhood of that point.

---

0, Pr(Y = Pr(Y = M|r] and <)(z) s (,,, = 1|=]], using Table | where s(A) = ( Pr(A=ī) | Pr(A-oj)- ). Therefore, d-GNP, together with the discussion after 4 shows that the optimal classifier and rejection function are obtained as
- { M(x) - 0 Pr(Y = 1/x) <
Pr(Y 1|x)
I+ks(A)
1+Ra(1)
2
and
{ 1 Pr(Y = -Mp) - ks) Pr(M = 1/x) > ((A,2)
(() (00=10 Pr(Y = M|z) - ks(A) Pr(M 111) < x(A,z)
for a fixed value & E I. and where x(A, :- max (Pr(Y =Olz), Pr(Y 1|x) kis (A)}. The above identities imply that the optimal fair classifier for the deferral system thresholds the scores for different demographic groups using two thresholds (0) and (1). This similar in form to the optimal fair classifier in vanilla classification problem [4 20). However, the rejection function does not merely threshold the scores for different groups, but adds an input-dependent threshold (s)A) Pr(M ((x) to the unconstrained deferral system scores.
is important to note that although we have a thresholding rule for the classifier, the thresholds are not necessarily the same as of isolated classifier under faimess criteria. Furthermore, the deferral rule is dependent on the thresholds that we use for the classifier. Therefore, we cannot train the classifier for a certain demographic parity and rejection function in two independent stages. This further affirms the lack of compositionality of algorithmic fairness that we discussed earlier in the introduction of this paper.
Example 2 (L2D with Equality of Opportunity). Here, similar to the previous example, we can obtain the embedding function for accuracy and equality of opportunity constraint elo(x) [p- pb Pa and 1 (1:) t(A, 1) [0,, Pr(M = 1,Y = 1|>)], respectively, where ph Pr(Y a|x) for i {1.2] and similarly P Pr(Y [zr. Therefore, the characterization of optimal classifier
and rejection function using d-GNP results in
1
(2- kt 1)) >
h(z)
0
(2 kt, 1)) <
and
{
1 D.d (1 1) 1|Y = M,x)) > v(A,z) 1|
r(x)
0 M (1 ( = =
<v(A, x))
for l: E R. and where v(A, == max (1 (t, 1))p²} Assuming 2 2 (t, 1) takes positive values for all choices of A, we conclude that the optimal classifier is to threshold positive scores differently for different demographic groups. However, the optimal deferral is a function of probability of positive prediction by human expert.
Example 3 (Algorithmic Fairness for Multiclass Classification). In addition to addressing the L2D problem, the formulation of d-GNP in Theorem 4.1 allows for finding the optimal solution in vanilla classification. In fact, for an L-class classifier, if we aim to set constraints on demographic parity
Pr(Y 0 = 0) Pr 0 = 1) < 5 equality of opportunity Pr(ř 0 0, A 0) Pr(Y = o = 0, = 1)| < 8 on Class 0, then we can follow similar steps as in Appendix D to find the embedding functions as VDP = ((A) [1.0...... 0] and ehzo = t(A, 0) [p. .......) 0]. where p'_ = Pr(Y = i|ær) for i [L]. As result, since the accuracy embedding function is (x( = [p....,, .r]] then, by neglecting the effect of randomness, the optimal classifier under such constraints are as
hpp(x) = argmax {pe kss(A), P2 ...1
and
hgo(z) argmax {p - kt p!... pP.)
Equivalently, for demographic parity, the optimal classifier includes shift on the score of Class 0 as a function of demographic group, and for equality of opportunity, the optimal classifier includes a multiplication of the score of Class 0 with a value that is a function of demographic group. It is easy to show that under condition of positivity of the multiplied value, these classifiers both reduce to thresholding rules in binary setting.
7

---

Note that although Theorem 4.1 characterizes the optimal solution of (3). it leaves us uninformed regarding parameters ....... km and further does not give us the form of the optimal solution when (o(r)) Li=1 (1)) has more than one maximizer. In the following theorem, we address these issues for the case that we have a single constraint.
Theorem 4.2 (d-GNP with a single constraint), The optimal solution (8) of the optimization problem (3) with one constraint is equal to (x) = (wob(z) - k (I), x) where is a member of Ta such that if there is non-singleton set I of maximizers of a vector y E RR,, then we have (f(y, - p and (r(y,+))(1) 1-p, where i and j are the first indices in I that minimizes 4/1 (x), and maximizes
vo(x)), respectively. In this case, k is a member of the set KC = {t: 5 [lim,te C(T), C(t), where C(t) = ( [o(x))] is the expected constraint of the predictor fi.. Moreover, p C(k) C(k)-lim,pe- C(T)) if C(-) is lowcr-discon at k, and otherwise p p= 0.
This theorem reduces the complexity of finding kys from the complexity of an exhaustive search to the complexity of finding the root of the monotone function C(t) ō (see Lemma 1.2 for the proof of monotonicity), and further finds the randomized response for the cases that Theorem leaves undetermined.
Before we proceed to the designed algorithm based on d-GNP, we should address two issues. Firstly, during the course of optimization, it can occur that the solution of Theorem 4.1 does not compute non-negative values k; for an i E [1 m]. This means that the constraints are not achieved tightly in the final solution of (3). Therefore, we are able to achieve the optimal solution with the constraint 8% < 54. Now, if we can assure that the constraint tuples are still inner points of F when we substitute 5, by 6%, then Theorem 4.1 shows that (8) still an optimal solution to 3
Secondly, for tackling various objectives that are defined in Section 3 we usually need to upper- and lower-bound performance measure by d and -5. However, since both bounds cannot hold tightly and simultaneously unless the tolerance is d = 0, then we can use only one of the constraints in turn and apply the result of Theorem 4.2 and check whether the constraint is active in the final solution. In the next section, we design an algorithm based on these results and show its generalization to the unseen data.
5 Empirical d-GNP and its Statistical Generalization
In previous sections, we obtained the optimal solution to the constrained optimization problem using d-GNP. Based on this optimal solution, we can design plug-in method (see Algorithm [ Appendix F to solve the constrained learning problem using empirical data. This algorithm varies from many Lagrangian-base based algorithms for solving constrained learning problem (c.g.. Primal- method (10) in which the optimal predictor parameter and constraint penalties
in
dependent to each other, and therefore we should learn them iterativaly. However, as we saw in Theorem [5.] (respectively in Algorithm[], []. the solution of d-GNP is mere thresholding on the corresponding embedding functions, where the threshold is obtained in a post-hoc manner and from validation dataset. Therefore, although Lagrangian-base a large computational cost, the d-GNP can potentially reduce such complexity costs and improve convergence conditions. To show such convergence, we bound the generalization error of the objective and constraints based on this solution. These results are extensions of the generalization results for Nayyma--PPasane 71] and further hold when multiple constraints should be controlled at once. The first result is the following theorem that shows if the solution to our plug-in method meets constraints of the optimization problem on training data, this generalizes to the unseen data.
algorithms can lead to oscillations converge with
Theorem 5.1 (Generalization of the Constraints). For the approximation of the Neyman-Pearson solution (x) in Algorithm 1 such that Es- ( (x), (b(())) S dn o i E [1: m), if we assume that embedding functions are bounded, then for dc(c)) = O TTgg n Tog 1/c and Sth ~ μ we have t
E2 (f,,)()), (x))) S 6 + do ( for all i E [1: : m] and with probability at least 1-
In the above theorem, we show that the optimal empirical solution for the constraint, probably and approximately satisfies the constraint on true distribution. Therefore, if we assume that we have an approximation (x)x) in hand where (z)) vx(2))le I e' with high probability, this theorem together with Hölder's inequality shows that we need to assure Es. (fr,p(x), (x(x))) s 8 - dn ( ( - e' to achieve the corresponding generalization with high probability.
8

---

Cundrnin Vielelun
Demaograpen
0.30
a
6:16
Det
0
600
005
063
00.0
8.31
0.1
0225 add. n00 kil 1155
0005 r0te. ort cas.
602 63X
Test Anouncy
Cuultzant Tolesanne
Coustraint Takrance
Figure 2: Performance of d-GNP on COMPAS dataset (left), and ACSIncome (center and right)
Next, we ask whether the objectives of the empirical optimal solution and the true optimal solution are close. We answer to this question positively in the following theorem. First, however, let us define the notions of (y, A)-sensitivity condition the following. This is extension detection condition in [7]] and assumes that changing the parameter in predictor leads to a detectable change in constraints.
Definition 5.2. For an embedding function thi, and distribution μa on X, we refer to a function (1)) as prediction with (7, A)-sensitivity around k, if there exists C' E IR+ such that for all E (0, A] we have
Ex ((rx())) - (x)))()), sh (2:)}] 2 C87.
Now, express the following generalization theorem for predictors that address the above conditions: Theorem 5.3 (Generalization of Objective). Assume that (8 6t, 8 + 6x) is a subset of of all achievable constraints EE| [[f(x), th (x))), and that |/4 (x) I ffrrr i 1, Further, let the size of validation data be large enough such that dn (6/3) I &L Now, if the optimal predictor fi,o(a) (%, A)-sensitive around optimal k. for A (dd (8/3), 6 ,,, and y S then for log 3. and with probability at least 1 has an objective that is at most Odd ((d3)((//)),))))))) /// / / 6,/2, C-1/,, -far from the true optimal objective.
n 2 27
the optimal empirical classifier, as of Algorithm
Now that we have proven generalization of our post-processing method, we should briefly compare this to other possible algorithms to learn an approximation the optimal classifier and rejection function pair. A possible method is to find the appropriate 'defer' 'no defer' value for each instance in the training dataset, and for a given set of constraints. Although these types of in-processing algorithms can perform computationally efficient (e.g., O(n log n) complexity for =-suboptimal solution for human intervention budget as shown in Theorem G.I), they do not necessarily generalize to unseen data. In particular, empirical data, there exist two underlying distributions on the data on which the algorithm results in similar deferral labels, while the optimal rejection functions for these two distributions interchangeable. This argument is further formalized the following proposition:
show that for all algorithms that estimate deferral labels from
Proposition 5.4 (Impossibility of generalization of deferral labels). For every deterministic deferral rule for empirical distributions and based on the two losses m and Ix(x) there exist two probability measures μr and μ12 on X y M such that the corresponding (f, X) for both measures is distributed equally. However, the optimal deferral rj. and r'y for these measures are not interchangeable that is L (h. ( 3 while (trr(h,r - for 1,2 and j f
In nutshell, this proposition implies that, every algorithm that reduces the two-bit data of human accuracy and Al accuracy for an input into single-bit data of 'defer' or 'no defer' looses the information that is important for obtaining the optimal rejection function that generalizes to the unseen data. This is a drawback of in processssin algorithms that are used in multi-objectivve L2D problems. We refer the reader to Appendix M for more details and proof of aforementioned proposition.
6 Experiments
COMPAS dataset. We implemented c Algorithm first for COMPAS dataset 2 in which the recidivism rate of 7214 criminal defendants is predicted. The human assessment done in this
*The code is available in htt.pp::///gghhb.....aaaaalctttt

---

1.0
dialect, mixture of human and classifier involvement to Goand Fun Pec
Oreana Baits Freet Claniifer ins
Trtts Pone Pruriidee
He Frceaies
Seer strve)
6-CM (25-15)
05
38
66-
00
Hele
Vetrer
Figure 3: Prediction of d-GNP on Hatespeech dataset [2 and for tweets with predicted African-
American (left), and Non-African--Amerian (center) dialect and the disparity between groups (right).
dataset on 1000 cases by giving humans a description of the case and asking them whether the defendant would recidivate within two years of their most recent crime The demographic parity is assessed for two racial groups of white and non-white defendants. Figure 2 shows the average performance of d-GNP over 10 random seeds compared to two baselines: (1) Madras et al. [44] in which a demographic parity regularizer is added to the surrogate loss, and over a variation of 100 regularizer coefficient, and (2) Mozannar al. [50] in which after training the classifier and rejector pair, we shift the corresponding scores to find a new thresholding rule. All scores, classifiers, and rejection functions are trained on a 1-layer feed-forward neural network. The figure shows that achieving better fairness criteria is possible using d-GNP, while this might not lead to better accuracy when the constraint violation is not of interest.
Hatespeech dataset. The next experiment is on flagging offensive tweets in Hatespeech dataset 22.. This dataset contains 24,802 tweets that are labeled by least three crowd workers as hate speech, offensive but not hate speech, or neither hate speech nor offensive. We used pre-trained model [5] to detect whether the tweet contains an African-Ameries
dialect. Next, we used dl-GNP method to control the demographic disparity of predicting tweet hate speech or offensive bounded by 0HS = 0.1 and 60 = 0.01, In the result of this experiment that displayed in Figure we can observe the following points: (i) in test-time the resulting demographic disparity for both classes bounded as expected, (ii) the accuracy of d-GNP method bounded by the vanilla deferral method, while stricter constraint control (in here offensive prediction parity) keeps the accuracy lower, and (iii) interestingly, the performance of d-GNP for controlled offensive prediction parity copies that of human. Therefore, a good strategy for obtaining such constrained learn-to-defer system seems to be to defer the offensive tweet prediction to human, when the tweet contains and otherwise either bias the classifier scores achieve the final controlled disparity.
ACS dataset. We further tested our method on folktables dataset 25 that contains income prediction task based on 1.6M rows of American Community Survey data. Since we had no access to human expert data, we simulated human expert that has different accuracy on two racial groups of white and non-white individuals (85% and 60%, respectively). We considered the L2D problem with bounded equalized odds violation. Figure shows our method's accuracy and constraint violation, coupled with a confidence bound that is obtained using ten iterations of bootstrapping. This figure shows that violation bounds are accurately met for the test data, and the performance increases when these bounds are loosened.
7 Conclusion
The d-GNP is a general framework that obtains the optimal solution to various constrained learning problems, including but not limited to multi-objective L2D problems. Using this post-processing framework, we can first estimate the scores related to our problem and then find linear rule of these scores by fine-tuning for specific violation tolerances. This method reduces the computational complexity of in-processing methods while guaranteeing achieving a near-optimal solution in large data regime.
'This is opposed to the experiment in 44 where the human decision is simulated.
10

---

8 Acknowledgment
M.A. Charusaie thanks the International Max Planck Research School for Intelligent Systems (IMPRS- IS) and Tübingen AI Center for the support and funding of this project. He is further grateful to Matthaus Kleindessner for his significant intellectual contributions to the first draft of this paper. The idea of obtaining an extension to the Neyman- Neyman-Pearson lemma emerged from discussions with André Cruz and Florian Dorner. The very initial draft of this paper was written during an hours-long train delay in Germany, and thus, M.A. Charusaie thankful Deutsche Bahn in that regard.
References
[1] Jean-Yves Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers. 2007.
[2] Gagan Bansal, Besmira Nushi, Ece Kamar, Eric Horvitz, and Daniel S Weld. Is the most accurate ai the best teammate? optimizing ai for teamwork. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 1 1400-11414, 2021.
[3] Peter L Bartlett and Marten H Wegkamp. Classification with a reject option using hinge loss. Journal of Machine Learning Research, 9(8), 2008
[4] Emma Beede, Elizabeth Baylor, Fred Hersch, Anna Iurchenko, Lauren Wilcox, Paisan Ruamvi- boonsuk, and Laura M Vardoulakis. human-centered evaluation of a deep learning system deployed in clinies for the detection of diabetic retinopathy. In Proceedings of the 2020 CHI conference on human factors in computing systems, pages 1-12, 2020.
[5] Su Lin Blodgett, Lisa Green, and Brendan O'Connor. Demographic dialectal variation in social media: A case study of african-americe english. arXiv preprint arXiv:I608.08880 2016.
[6] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the chpiik-chervoneniis dimension. Journal of the ACM (JACM), 36(4):929-965, 1989.
[7] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, al. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3(1):1-122, 2011.
[8] Yuzhou Cao, Tianchi Cai, Lei Feng Lihong Gu, GU Jinjie, Bo An, Gang Niu, and Masashi Sugiyama. Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses. In Advances in Neural Information Processing Systems.
[9] Yuzhou Cao, Hussein Mozannar, Lei Feng, Hongxin Wei, and Bo An. In defense of softmax parametrization for calibrated and consistent learning to defer. Advances in Neural Information Processing Systems, 36, 2024.
[10] Luiz FO Chamon, Santiago Paternain, Miguel Calvo-Fullana, and Alejandro Ribeiro. Con- strained learning with non-convex losses. IEEE Transactions on Information Theory, 1739- 1760, 2022.
[11] Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama. Classifi- cation with rejection based on cost-sensitive classification. In International Conference on Machine Learning, pages 1507-1517. PMLR, 2021.
[12] Mohammad-Amin Charusaie, Hussein Mozannar, David Sontag, and Samira Samadi. Sample efficient learning of predictors that complement humans. In Proceedings of the 39th Interna- tional Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 2972-3005. PMLR, 2022.
[13] Richard J Chen, Judy J Wang. Drew FK Williamson, Tiffany Y Chen, Jana Lipkova, Ming Y Lu, Sharifa Sahai, and Faisal Mahmood. Algorithmic fairness in artificial intelligence for medicine and healthcare. Nature biomedical engineering, 7(6):719-742, 2023.
[14) Wenlong Chen, Yegor Klochkov, and Yang Liu. Post-hoe bias scoring optimal for fair classification. arXiv preprint arXiv:2310.05725, 2023.

---

[15] Xin Cheng, Yuzhou Cao, Haobo Wang, Hongxin Wei, Bo An, and Lei Feng. Regression with cost-based rejection. Advances Neural Information Processing Systems, 36, 2024.
[16] Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on information theory, 16(1):41-44) 1970.
[17] Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Leveraging labeled and unlabeled data for consistent fair binary classification. Advances in Neural Information Processing Systems, 32, 2019.
[18] Sam Corbett- Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of fairness. In Proceedings of the 23rd acm sigkdd international conference on knowledge discovery and data mining, pages 797-806, 2017.
[19] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning Theory: 27th International Conference, pages 67-82. Springer, 2016.
Learning with rejection. In Algorithmic
[20] André Cruz and Moritz Hardt. Unprocessing seven years of algorithmic fairness. arXiv preprint arXiv:2306.07261, 2023.
[21] George B Dantzig and Abraham Wald. On the fundamental lemma of neyman and pearson. The Annals of Mathematical Statistics, 22( (771))87-33)) 93, 1951.
[22] Thomas Davidson, Dana Warmsley, Michael Macy, and Ingmar Weber. Automated hate speech detection and the problem of offensive language. In Proceedings of the international AAAI conference on web and social media, volume 11, pages 512-515, 2017.
[23] Abir De, Paramita Koley, Niloy Ganguly, and Manuel Gomez-Rodriguez, Regression under human assistance. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2611-2620, 2020.
[24] Abir De, Nastaran Okati, Ali Zarezade, and Manuel Gomez Rodriguez. Classification under human assistance. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5905-5913, 2021.
[25] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34:6478-6499
2021.
[26] Kate Donahue, Alexandra Chouldechova, and Krishnaram Kenthapadi. Human-algoritha collaboration: Achieving complementarity and avoiding unfairness. In Proceedings the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1639-1656, 2022.
[27] Julia Dressel and Hany Farid. The accuracy, fairness, and limits of predicting recidivism. Science advances, 4(8)eeaa05580, 2018
[28] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012.
[29] Cynthia Dwork and Christina Ilvento. 1rXiv:1806.06122. 2018.
Fairness under composition. arXiv preprint
[30] Ran Yaniv al. On the foundations noise-free selective classification. Journal of Machine Leurning Research, 11(5). 2010.
[31] David Heaver Fremlin. Measure theory, volume 4. Torres Fremlin, 2000.
[32] Aditya Gangrade, Anil Kag, and Venkatesh Saligrama. Selective classification via one-sided prediction. In International Conference on Artificial Intelligence and Statistics, pages 2 2179- 2187. PMLR, 2021.
[33] Yonatan Geifman and Ran El-Yaniv, Selective classification for deep neural networks. Advances in neural information processing systems, 30, 2017.
12

---

[34] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances neural information processing systems, 29, 2016.
[35] Xiaoqian Jiang, Melanie Osl, Jihoon Kim, and Lucila model estimates to support personalized medicine. Journal of the American Medical Informatics Association, 19(2):263- 274, 2012.
Calibrating predictive
[36] Erik Jones, Shiori Sagawa, Pang Wei Koh, Ananya Kumar, and Percy Liang. Selective classifi- cation can magnify disparities across groups. arXiv preprint arXiv:2010. 14134, 2020.
[37] Ece Kamar, Severin Hacker, and Eric Horvitz. Combining human and machine intelligence in large-scale crowdsourcing. AAMAS, volume 12, pages 467-474, 2012.
[38] Achim Klenke. Probability theory: comprehensive course. Springer Science Business Media, 2013.
[39] Benjamin Kompa, Jasper Snoek, and Andrew L. Beam. Second opinion needed: communicating uncertainty in medical machine learning. NPJ Digital Medicine, 4(1):166, 2021.
[40] Thomas Landgrebe and Duin. On neyman-pearson optimisation for multiclass classifiers, In Proceedings 16th Annual Symposium of the Pattern Recognition Association of South Africa. PRASA, pages 165-170, 2005.
[41] Joshua K Lee, Yuheng Bu, Deepta Rajan, Prasanna Sattigeri, Rameswar Panda, Subhro Das, and Gregory W Wornell. Fair selective classification via sufficiency. In International conference on machine learning, pages 6086. PMLR, 2021.
[42] Erich Leo Lehmann, Joseph Romano, and George Casella. Testing statistical hypotheses, volume 3. Springer, 1986.
[43] Shuqi Liu, Yuzhou Cao, Qiaozhen Zhang, Lei Feng, and Bo An. Mitigating underfitting in learning to defer with consistent losses. In International Conference on Artificial Intelligence and Statistics, pages 1816-4824 PMLR, 2024.
[44] David Madras, Toni Pitassi, and Richard Zemel. Predict responsibly: improving faireess and accuracy by learning to defer. Advances in Neural Information Processing Systems, 31, 2018.
[45] Anqi Mao, Mehryar Mohri, and Yutao Zhong. Predictor- multi-class abstention: Theo- retical analysis and algorithms. In International Conference Algorithmic Learning Theory, pages 822-867. PMLR, 2024.
[46] Charles E Metz. Basic principles of roc analysis. Seminars in nuclear medicine, volume pages 283-298. Elsevier, 1978.
[47] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[48] Hussein Mozannar, Hunter Lang, Dennis Wei, Prasanna Sattigeri, Subhro Das, and David Sontag. Who should predict? exact algorithms for learning to defer to humans. In International conference on artificial intelligence and statistics, pages 10520-10545. PMLR, 2023.
[49] Hussein Mozannar, Hunter Lang, Dennis Wei, Prasanna Sattigeri, Subhro Das, and David Sontag. Who should predict? exact algorithms for learning to defer to humans. arXiv preprint arXiv:2301.06197 2023.
[50] Hussein Mozannar and David Sontag. Consistent estimators for learning to defer to an expert. In International Conference Machine Learning, pages 7076-7087. PMLR, 2020.
[51] Harikrishna Narasimhan, Wittawat Jitkrittum, Aditya K Menon, Ankit Rawat, and Sanjiv Kumar. Post-hoe estimators for learning to defer an expert. Advances Neural Information Processing Systems, 35:29292-29304 2022.
[52] Harikrishna Narasimhan, Aditya Krishna Menon, Wittawat Jitkrittum, Neha Gupta, and Sanjiv Kumar. Learning to reject meets long-tail learning. The Twelfih International Conference on Learning Representations.
13

---

[53] Harikrishna Narasimhan, Aditya Krishna Menon, Wittawat Jitkrittum, and Sanjiv Kumar. Plugin estimators for selective classification with -uttof--distibutionn detection. arXiv preprint arXiv:2301. /2323000..236,, 2023.
[54] Harikrishna Narasimhan, Harish G Ramaswamy, Shiv Kumar Tavker, Drona Khurana, Praneeth Netrapalli, and Shivani Agarwal. Consistent multiclass algorithms for complex metries and constraints. arXiv preprini 2rXiv:2220.09000 2022.
[55] Jerzy Neyman and Egon Sharpe Pearson. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of Mathematical or Physical Character, 131664477662228--3333
1933.
[56] Jerzy Neyman and Egon Sharpe Pearson. Contributions to the theory of testing statistical hypotheses. Statistical research memoirs, 1936.
[57] Nastaran Okati, Abir De, and Manuel Rodriguez. Differentiable learning under triage. Advances in Neural Information Processing Systems, 34:9140-9151, 2021.
[58] Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998.
[59] Charles Chapman Pugh and CC Pugh. Real mathematical analysis, volume 2011. Springer, 2002.
[60] Maithra Raghu, Katy Blumer, Greg Corrado, Jon Kleinberg, Ziad Obermeyer, and Sendhil Mullainathan. The algorithmic automation problem: Prediction, triage, and human effort. arXiv preprint arXiv:/9033 12220, 2019.
[61] Philippe Rigollet and Xin Tong. Neyman-pearson classification, convexity and stochastic constraints. Journal of machine learning research, 2011.
[62] Salvatore Ruggieri, Jose M Alvarez, Andrea Pugnana, Franco Turini, et al. Can we trust fair-ai? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 15421-15430, 2023.
[63] Stephen-John Sammut, Mireia Crispin-Ortuzar, Suet-Feung Chin, Elena Provenzano, He- len A Bardwell, Wenxin Ma, Wei Cope, Ali Dariush, Sarah-Jane Dawson, Jean E Abraham, et al. Multi-omic machine learning predictor of breast cancer therapy response. Nature, 601(7894)6223-62,,22 2022.
[64] Clayton Scott. Performance measures for neyman classification. IEFE Transactions on Information Theory, 53(8):2852-2865 2007.
[65] Clayton Scott and Robert Nowak. A neyman-pearson approach to statistical learning. IEEE Transuctions Information Theory, 51(11):380--311, 2005.
[66] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
[67] Dharmesh Tailor, Aditya Patra, Rajeev Verma, Putra Manggala, and Eric Nalisnick. Learning to defer to population: A meta-learning approach. In International Conference on Artificial Intelligence and Statistics, pages 3475-3483. PMLR, 2024.
[68] Sarah Tan, Julius Adebayo, Kori Inkpen, and Ece Kamar. Investigating human+ machine complementarity for recidivism predictions. arXiv preprint arXiv: 1eXiv:1808.00 09133, 2018.
[69] Ye Tian and Yang Feng. Neyman-pearson multi-class classification via cost-sensitive learning. arXiv preprint arXiv:2111.04597, 2021.
[70] Alexandru Tifrea, Preethi Lahoti, Ben Packer, Yoni Halpern Ahmad Beirami, and Flavien Prost. Frappé: A group fairness framework for post-processing everything. In Forty-first International Conference on Machine Learning.
[71] Xin Tong. A plug-in approach to neyman-pearee classification. The Journal of Machine Learning Research, 14(1):00113340,, 2013.
14

---

[72] C Vermeulen, M de Witt Hamer. EJ Kooi, L Dankmeijer, J van der Lugt, Ultra-fast deep-learned cns tumour classification during surgery. Nature, 622(79844)842-884) 849-849, 2023.
L Kester, MEG Kranendonk, P Wesseling, N Verburg.
[73] Ruicheng Xian, Lang Yin, and Han Zhao. Fair and optimal classification via post-processing. In International Conference on Machine Learning, pages 11977-38012.. PMLR, 2023.
[74] Tongxin Yin, -ean-François Ton, Ruocheng Guo, Yuanshun Yao, Mingyan Liu, and Yang Liu. Fair classifiers that abstain without harm. arXiv preprint arXiv:23/0.06205, 2023.
[75] Xianli Zeng, Guang Cheng, and Edgar Dobriban. Bayes-optimal fair classification with linear disparity constraints via pre-, in- and post-processing. arXiv preprint arXiv:2402.02817, 2024.
[76] Xianli Zeng, Edgar Dobriban, and Guang Cheng. Bayes-optimal classifiers under group fairness. arXiv preprint arXiv:2202.0977 2022.
15

---

Content of Appendices
Lack Compositionality of Fairness Criteria
17
Extended Related Works
17
Rephrasing (2) into Linear Functional Programming
18
D
Derivation of Embedding Functions
19
Limitations of Cost-Sentilive Methods
22
d-GNP Learning Algorithm
24
On Failure of In- In-Processing Methods
24
Proof of Theorem 3.1
27
Proof of Theorem 4.1
28
Proof of Theorem 4.2
33
K
Proof of Theorem 5.1
40
Proof of Theorem 5.3
43
Proof of Theorem G.1
48
16

---

A Lack of Compositionality of Fairness Criteria
Here, we show an example lack of compositionality fairness criteria for learn-to-dffer problems. This falls in line with [29), where the authors studied the effect of the operators such 'OR' or 'AND'. Here, we show that a similar non-compositionaliy holds for the operator 'DEPER'. The following example is found based the insight that a fair predictor is fair over all the space X, and it could take a decision over only a subset of will not necessarily be fair predictor. This can be seen particular application of Yule's effect (62) which explains that vanishing correlation in a mixture of distributions does not necessarily concludes vanishing correlation on each of such distributions.
and 24, and that the input takes these values with probability Pr(X z1) Pr(X = x2) Pr(X xz) Pr(( x4) The first two points 11, 22 are corresponded to the demographic group A = 0 and the last two points are corresponded
Let us assume that the space X' contains only four points 21,
the demographic group A 1. Further, assume that the conditional target probability is Pr(Y = [ Pr(Y - (r2) = Pr(Y = 1 1 Pr(Y 1 1. Moreover, we consider the equality of opportunity as the measure of fairness. Now, assume that the classifier h(-) X' + {0, } is taking values h(z1) = 1, h(x2) = 0. h(rz) = 1, and h(x*a) = 0 and the human decision maker predicts M = 0 conditioned on 31, M 1 conditioned on 22, and M = conditioned on 23, and M 0 conditioned on 4/4 Therefore, both classifier and human expert have accuracy of 2 on the data.
Following the above assumptions, can find the fairness measure for classifier as
Pr(M(X) = 1|Y = A = 0) Pr(M(X) = 1|Y = 1, =) =Pr(h(X) 1| = -;
= = 1, 0) +Pr(h(X)= = =1 = =1,A= 22) Pr(X = =2/Y = 1,
-Pr(h(X) 1|Y =1,A= = 23) Pr(X = xg/Y== -1,A-1)
-Pr(h(X) = 1|Y = =,A-= 1,X = xA) Pr(X = x,/Y-= -,A=-= 1) +
0 0,
2
(10)
which means that the classifier is fully fair. We can derive a similar result for the human expert, i.c.,
Pr(M 1|Y -) Pr(M 1 1, A 1) = 0.
(11)
Now that we established a fair classifier and fair expert, we take the step to find an optimal deferral solution, i.e., a deferral system that minimizes the overall loss. We can observe that for xı the classifier is accurate, while for 22 the human expert is accurate. Furthermore, for 23 and 24 they both are equally inaccurate. Therefore, an optimal solution is not to defer for #1, and defer for 22, and take an arbitrary decision for 23 and f4. Now, if we find the faimess measure of the resulting deferral predictor, we have
Pr(h= = 1|y = 1, 0) - Pr(r = 1 1=,
=Pr(h(X) 1|Y = 1, = =xx) Pr(X = =1,
+Pr(M = 1/Y = 11,4-0,X
Pr(X =2/Y 1, -))
-Pr(h(X)= = 1 11A==,,==1,-
23) Pr(X = =
1,, =1)
1
-Pr(M(X)= = 1 1,4 = x= x4) Pr(X x 1,4 1 =
1)
0
2
2
2
2
(12)
or equivalently the resulting predictor is unfair for the demographic group A 1. This means the 'DEFER' composition of the predictors does preserve fairness. One can further easily show that no deferral system from the above classifier and human expert that has the accuracy better than is fair.
B Extended Related Works
The deferral problem has been studied under a variety of conditions. Rejection learning 19
15
or selective classification 30 33 32), assumes that a fixed cost is incurred to the overall loss, when MI. decides not to make a prediction on an input. The first Bayes optimal rule for rejection learning was derived in [16]. Assuming that the accuracy of human, and consequently the cost of deferring to
17

---

the human, can vary for different inputs, [50] obtained the Bayes optimal deferral rule. The deferral problem is further studied assuming that the number of available instances for deferral are bounded and near-optimal classifier and deferral rule is required as solution of empirical risk minimization
[3 24]. . Most recently, the implementation of deferral rules using neural networks and surrogate losses is studied for binary and multi-class classification 88 50 12
45 A possible shift in human expert for L2D methods recently studied in 667 The problem multi-objective L2D and rejection learning is mainly studied in an in-processing approach. A few instances of tackling such problems can be found in (57 52 53 and [14 for L2D and rejection learning, respectively.
51
9 43
48
Nyyman-Pearson 's fundamental lemma is introduced in [55 originally for binary hypothesis testing and later was generalized in [56] to give a close-form formulation for a variety of binary constrained optimization problems. Later, 21 found conditions for which Neyman and Pearson solution exists and is unique. The generalization error of the empirical solution to Neyman- problem is studied in two lines of works: (i) the generalization of direct (in-processing) solutions to the optimization problem 665 64 [1], and (ii) the generalization of plug-in methods [71 that first approximate the score functions and then use Ssyman-PPerson lemma to approximate the predictor. The generalization of Neyman-Pearson lemma to multiclass setting is first empirically studied in 40 and under strong duality assumption is proved in [69] Our lemma d-GNP extends these works in order to (i) be able to control a general set of constraints instead of Type-K K errors, and (ii) be valid in absence of strong duality assumption. Further, the idea of using Neyman-Peann Peaasson lemma for controlling faimess criteria originally dates back to [76] (later as (75). More recently, a similar post- post-processing method introduced in [14 using cost-sensitive learning and strong duality technique. Although these works cover binary classification problem, in this paper we focus on solving multi-class classification problem, and particularly in a deferral system.
Moreover, his work differs from multi-class classification with complex performance metrics [54] in the sense that they consider constraints that are non-linear functions of confusion matrix, while ignoring the dependence on input x. In our setting, the constraints are linear in terms of confusion matrix when conditioned on the input, but the linear coefficients vary with the input.
Finally, the work (70) has recently studied an extension of post-processing method to other constrained learning problems. The difference of that work with our method is threefold: (i) while we prove that the optimal prst-proesssing method is a linear combination of scores, they have such claim, (ii) we have no assumption on the format of the loss function, while they assume a particular set of strictly convex loss functions, (iii) we have no bound on our hypothesis class while they assume the representation of the predictor with a multidimensional vector and a fixed dimension.
C Rephrasing (2) into Linear Functional Programming
Here, we first characterize functions that are outcome-dependent. To that end, we define x(x) as
[ ( (=))=a))
(13)
This function can retrieve the value of r(z) and can retrieve the value of f((z) only if r(x) = 0. In fact, we can obtain r(x) = (I(=)) + 1) and h(x) = if r(z) = 0 and (1(=)) = 1. Therefore. for a function & (xx h(z),r(x) = Ey, xy (1, Y, M, (az)), rx))] and laer(1, ((x),r(x) = Ey.Mix== (z, [faor(r Y, M(x),, r [=]) to be outcome dependent, it must only be function of x and a(r). In fact, we must have
(.,,,))))r(()))) = (x)),
(14)
and
(x, ((e,, = Eaee (z))))
(15)
for a choice of V and Easts where faor Now, we can check that x(x) can take L + different values, in each of which one of its components takes the value 1 and others take the value O. Therefore, by conditioning on each of these I, + values we have
= Ey. [y.Mix= Y, M, (M,((2))(x)))
L+1
Vi(2, x(x)) = Σ v'cx 10..... 1 .......)) o)) (1(()))()) =
(16)
18

---

where (x) is defined as
(/)())) (2, [1. O................. ................................ 0)) ...., (2 10.0. 11)
(,,,,, (,(),,,,,,,,,,,,,,.,..., L, 0), (z, 0)]
(17)
Similarly, we can show that where (x) is defined as
(x, (u(x), (x))
(18)
(xet(x) Rdet( (zx,
(x, L, 0), Eeet (at, 0, 0.]]
(19)
Next, we know that due to the randomization of A, the vector r(x) can take various values on each instance x. This, however, is not the case for (h)( and (x)r since they are defined independent of (x)) and (xx) Therefore, the average of constraints and loss can be rewritten as
B( ((),),)) r(z)) = (1)
(x())
(20)
and
(ass)ma(edeele (())
(
(f(z), Ede((z))
(21)
where fax is defined as
f(x) = [[((=)] = [Pr(r(=)= (xx) Pr(r)))
L), L), =)]- (22)
Therefore, the optimization problem in (2) is effectively reduced to the linear programming problem in (3) Moreover, if (x) is the solution to that linear program, then the corresponding r(x)
should be distributed Pr(r(x) 1) (z) + 1), where h(z) should be distributed
(1(z))
as Pr(h(x) i) Pr(h(x)) ilr(z) 0)
Note that the assumption of
Di (fe)) ())
independence of h(x) and r(x) comes with no loss of generality, since the value of h(x)) does not variate the loss or constraints in the system when we have r(x) =
D Derivation of Embedding Functions
In this appendix we derive the embedding functions in Table that are corresponded to the constraints of choice, as named Section 3 The trick that we use for all these constraints is that we first rewrite the constraint in terms of the expected value of function over the randomness of the algorithm A and the input variable X, and then we use (17) to transform that function into the embedding function.
Overall Loss: To find the embedding function that is corresponded to the overall loss of the system, we should first note that by loss we mean the probability of incorrectness of Ý Therefore, the corresponding lde (I, h(x), r(x)) in this case, as defined in ( is obtained
(l,((x,())),rl -Ey,MIX= ( + [())
=I(())=1 Pr(M Y|X x) + T Pr(Y # M(x)X s:)-
Therefore, using 19 we find Eaet as
Eest Pr(Y =
Pr(Y + #n| Pr(Y MMX =)].
Expert intervention budget: In this case, similar the case before, we first derive
(x, M(x), r(x)). To that end, we first note that the expert intervention constraint in Section
3 equivalent with
Pr(r(X) 1) Eespx (Tro)= 5,
which in turn suggests that
V( (x),)xx))(x))) II(=)=1-
Next, we find (x) using 11 as
v(() J0....,.... 0,
19

---

OOD Detection: To obtain the corresponding embedding function to the OOD detection constraint in Section
we can rewrite Prout (r(X) 1) as
Pr (r(X) =
(rr.) [ fx (X)
TP(X)
where the last equation holds when and Xout are absolutely continuous distributions, and therefore have probability density functions. A similar assumption is made by [53] This results in (x. ((x),r(2)) being obtained as
(x, ((xx)(( = = (""
(X)
Therefore, we conclude that the embedding function can be calculated using 17 as
(bxx) = [0,.... O, 13 (x0) pipias
(X)
In the simple case that fx (a:) = TS (m)) (1)) da
the embedding function is equal to
(x) = [o..... O, Prim (F)
Long-Tail Classification: This methodology aims to minimize the balanced loss
K
1
Σ
Pr(Y + h(X))r(X) 0,Y E G.).
K
1=1
However, mentioned in
52 this optimization problem be rewritten as
K + (XX, ojY E G.)
s.t. Pr(r(X) = -|Y e G.) a;
K
Therefore, the objective can rewritten as
B(rA)aA.xs Pr(Y # (XX), = 0, G = X')
0g Pr(Y G.)
which together with shows that
vo(z))
Σ a; Pr E
K
Pr(Y #1,EE
=
Σ
Pr(Y FLY =
Pr(Y E G.)
1=1
The reason that negative sign is because in the definition of 3 aim maximize the objective.
Similarly, we can rewrite the objectives as
((r.A)-A..''pp [P((((X) 0,Y E = X') R Pr(Y E G.)
Pr(Y E Gt)
Therefore, using 17 we can obtain 1/((z) as
(((x) Pr(Y E G = Pr(Y E G.)
a
1,0
(23)
K
Type-k Error Bound: We first rewrite Type-k constraint in
3 as
Pr(V # k)
Pr(ý + 41l = k)
Pr(V
= k)
Ex Ex<ax
Pr(ý # k, = k|x = =x) x)
Pr(Y =
Ex
Pr(f # k/Y = k. x|
(24)
Pr(Y k)
20

---

where (a) is followed by chain rule.
Next, we condition Pr(Y + k/Y = k. X = x) on r(x) being and 0, which concludes that
Pr(Y + k/Y = k, X = σ) = Pr(y k, = 1|Y = k, X x)
+ +Pr(Y * #k,((1) = 0|Y = = =z)
Pr(M + k,) = = =
+ Pr(h(()) * k()()) =0))= = x)
-M X=a. [T (x)== + [(()))
B(.M)-All= Pr + k| = x, Y 1b (()==
+ +=(=)=
Therefore, using (4 we conclude that
Pr(y # k|Y k) xxx (x)== Pr(M + k. Y = k|X = xX)
Pr(Y = k)
Xx (wtp://nnaaaaax))aaaaAaT<Ta Pr(Y=k)
Pr(Y =|-== X
which together with 17) shows that the embedding function obtained as
Pr(Y
k x)
1,, Pr(M + k|X = x, x,Y = k))
((x)=
....,,
Pr( = k)
Note that here we used the assumption that (Y, .M) and A are independent for each choice of X, i.e., the value noise that is introduced in A for each X is generated independent of the value of and M, which is the true assumption, since the algorithm only has access to X and not true label or the human label.
Demographic Parity:
We know that the demographic parity constraint in Section 3 can be
written as
-8 = = 1|4 - Pr(r 1)
(25)
Here, we find the corresponding embedding function (z) for the upper-bound in the above inequality. For the lower-bound, we can use -xxx) and follow the steps that are proposed in the main text of the manuscript.
To find the embedding function that corresponds to the upper-bound of (25) we first rewrite Pr(r 1|A 0) Pr(ý = 1|A 1)
Pr(r 1| = 0) - Pr(g = 1|4 1) Pr(ý = =1,A=0) Pr(K -1,A=1)
Pr(A=
Pr(A=1)
(26)
Now, similar to what we did in previous section, we condition Pr(y = 1,A = a) for a E (0, 1) on the value of /ax)) and r(x), and we conclude
Pr(ř = 1, = a) = Pr(ý = 1, A a, = 1) 1) Pr 1, r(X) = 0)
= = 1, (.),, 1) -1 1,A a, r(X) 0)
-EX.A.M.A +u
+ Pr(A =|
Txx)=
(27)
Here, we used the assumption of independence of X and (M, given a choice of X. As a result of (66).
27 and (17) we can find the embedding function as
(b())= = 0, Pr(A = 1|X - x) Pr(A = 0 = x)
Pr(1=1]
Pr(A= =0 0)
Pr(M =1, 1|A==|x== Pr(M = 1, A 1 x)
Pr(A= =)
Pr(A= = 0)
21

---

(n-)Eqqalitty of Opportunity: Similar to the previous items, we rewrite equality of opportunity constraint Section B
as
- 8 Pr(Y = = 1, (aaA=))-r((---000
1 6
Again, We only consider the upper-bound and rewrite 1, -
1|Y = 1, A 0) as
Pr(Y 1|Y 1, -
Pr(Y = P, -1, -
(28)
Pr(Y = -1,-1111]
Pr(Y=1,4 1,A==,AA0))
Next, by conditioning on r(X) and r(X) = rewrite Pr(Y Y, 1, a)
for E {0, 1 as
Pr(Y 1,Y = = 1, 1,:: a,
= = 1, ,.
+Pr(f = 1,
-EX.MMAAA (
+ +
= 1
+ (x))= Pr(Y 1, a = x)] (29)
where the last identity is followed by the assumption of independence of A and (Y, M, A) given an instance x. As a result of 28
29 and 17
we can obtain the embedding function as
Pr(Y 1, 1 1|X =) Pr(Y 1, 0|X = x)
(x)x = 0.
Pr(Y = 1,4 = 1)
Pr(Y= = A- 0) 0)
Pr(M 1,
1( 1|X= =x) Pr(M 1,Y = 1 x)
Pr(Y = 11,
(In-) of Odds: This induces the same constraint as that of equality of opportunity, and further induces an extra constraint that is nature similar to equality of opportunity with the difference that it uses Y 0 instead of Y = 1. Therefore, we have two embedding functions, one is similar to that of equality of opportunity as
v (I:) (o. Pr(Y = 1, 1|X x)
Pr(Y = 1, A= 0| 0|x= x))
Pr(Y = 1,
Pr(Y = 1, A 0)
Pr(M = 1, - 1X= Pr(M = 1,Y = 11,A= =
Pr(Y 11A-
Pr(Y =1
and another similar to that with changing Y = into Y = 0, and therefore as
v2(2x) PrrY = 1 x) Pr(Y = 0, = -
Pr(Y = 0
Pr(V = 0, A = 0)
Pr(M = 1, -1A=1X=00 =x)
Pr(M 1,Y 0, 0|X x)
Pr(Y= 00,
Pr(Y = 0, 0)
E Limitations of Cost-Sentitive Methods
A variety of works have tackled constrained classification problems using cost-sensitive modeling
42 17 (57. other words, they use the expected loss that penalized with the constraints and solve that for certain coefficients for those constraints (a.k.a,, they form Lagrangian from that problem). In the next step, they optimize the coefficients and obtain the optimal predictor. The issue that we discuss further in the following concern is that during this process, the optimal predictor is achieved only
22

---

when the corresponding cost- sestisens Lagrangian has a single saddle point in terms of coefficients and predictors. Such assumption, unless by analyzing the Lagrangian closely, is hard be validated. However, our results in this paper have no such assumption, and instead use statistical hypothesis testing methods to show their optimality.
To further clarify the issue with such methodology, we bring an example of L.2D problem when human intervention budget is controlled. Suppose that the features in X are distributed with an atomless probability measure μ. (e.g.. normal or uniform distribution) [6] Further, assume that the human has perfect information of the label, i... Y = M. while the input features have no information X. Moreover, let the classifier and the human induce the 0 1 loss function. In this case, we can see that the optimal classifier is the maximizer of the scores (see the early discussion of Section H). which in this case, since there is clear maximizer, without loss of generality can be set to ((x)) For such assumptions, if write the Lagrangian in form of
of the label, i.e., Pr(Y x| z) 1/2 for all
1 r(,,r) (he X(E[r(X)] b) 2 B[[r( +(E))(X)()(())) b),
then strong duality shows that
min max ((),r) = max min L(,,r), rE A20
(30)
X20 rE(0,1}
or to put informally, the objective is invariant under the interchange of minimum and maximum over Lagrange multipliers and the variable of interest. However, this does not prove the interchangeability of the saddle points in these settings, i.e., cannot guarantee argmin L(X",r) f where
X E argmax min, rA,, and f E argmin,ejo.u maxx L(A, In fact, this guarantee holds only in particular examples, e.g., when L(2,, r) is strictly convex 7 page 8].
In fact, if we optimize r for all as in RHS of 30). we can show that (x {
0 otherwise
Therefore, X can be obtained as X = argmax
X - 1/2) - Ab where (x:) == (1, 0}. This
A20
can be rewritten as
- 0 0 < 1 1 A
A argmax X
2
ーAb
Hence, the condition À < 1/2 is never satisfied and we have T> (I) = 0, i.e., we should never defer. For the deferral rule r the deferral loss ① is
1
(h, f) Ex,Y, (E,,
2
To show that r-x is not optimal, we provide random and deterministic deferral rules f" and r** that
satisfy the constraint in (2). while having smaller deferral loss:
Let (x) = b, that is random deferral rule that defers with probability b everywhere on X. Therefore, on average b proportion of inquiries are deferred and thus it satisfies the constraint in 2 The deferral loss for (*(x)) is equal to
(h, f*) = [x]( B(CH(Y,
+ E[1 r(X)
EI E(CAr(Y,
1-b
b
2
The second example is a deterministic deferral rule Since the probability measure on X' is
atomless, for all b E [0. 1] there exists a set A such that Pr(X E A) = b [31] Proposition 215DJ. Hence, defining r**(x) (x) = IZEA the constraint in ( is met. Similar to the last example (h, = 1-b < -
The above two examples show that the deferral rule тX- is sub-optimal. The reason is that, for optimality of rx- we should make sure that L(X;,r) has single minimizer of r. However, in our example we had L(},r) r) -Xi has infinite number of minimizers in terms of r(x). Therefore, the equality of the solutions minimax problem and maximin problem is not guaranteed.
'If we have probability measure that contains atoms, one can follow the same steps for the first counterex- ample
23

---

d-GNP Learning Algorithm
Algorithm 1 Finding Optimal Classifier and Rejection Function
Require: The formulation of ( and (V Dmr and the datasets Derain ((x', a', m', y²) Jerr Dval {(x', a', m',, ,y") Femn Timaatt +1 and tolerances {
Ensure: Optimal deferral rule r (xr) and classifier (x)
1: Parameters:
le-
2: procedure WENSTRAINEDDEEEREE
(V.) Drrain vval)
3: Obtain closed-form
(z) using ldel and U,s via (4) and in terms of the scores as in
Table
4: Estimate the scores Table _ using classification//eeressiio methods on Dirain
5:
Find estimate } using estimated scores in previous step and closed-form of Step 3
6:
m then
7:
Define routine fap(()) = - (bo((z) - kuhn ()), for in Theorem 4.2
Define routine Õ(I) = ( (fno(())) di (xx))
8:
9:
Find ic min k over the feasibility set Õ(t) s 61
10:
1 = then
11:
Return 'Not Feasible'
12:
else
13:
if C(k c) C(k') le then
14:
else
p+ 8- 6-O(k) C(k-c)-((k)
17:
end if
18:
end
19:
s(x) = (t,(())
20:
else
Optimize 3 for vall and for f(x) = T(Ho(x) - EE,, (z), " for r as in Theorem
21:
4.1
and via exhaustive search over (ki, km) and randomizations of 7 and find s(x) = f(x)
22:
end
23:
h" h((x)= = argmax (z)
=E[0:L-1]
24:
(z) argmax ())-()) (2), sz())]
iE(0,1)
25:
Return h² h*xx), (())rr())
26:
end procedure
G On Failure of In-Processing Methods
One might think that the need of using post-processing methods does not necessarily appear in some examples multi-objective L2D problem. As an instance, for the expert intervention budget we can rank samples based on the difference between machine and human loss and defer the top b- b-proportion of samples for which the machine loss is higher than the human one. This method is illustrated in Algorithm 2 Indeed, in the following we show that the sub-optimality of such deterministic deferral rule, compared to the optimal deferral rule diminishes as the size of training set increases.
Theorem G.1 (Optimal Deferral for Empirical Distribution). For classifier f(x)) and dataset D = {Z Yi, Jn where assume x; + Kj. + j. the deterministic deferral rule as in Algorithm 2 is (i) the optimal deterministic deferral rule for the empirical distribution on D and bounded expert intervention budget, and (ii) most 1 --suboptimal (in terms of deferral loss) compared to the optimal random deferral rule for the empirical distribution on D.
Next the following, we show that such policy does not provide sufficient information to determine the optimal deferral rule for the true distribution. To that end, we first recall that in classification tasks, the optimal classifier typically thresholds an estimation of conditional probability of the label Y given X that is obtained using the available dataset. As result, if observe enough pairs of (æt, y1), then

---

Algorithm 2
Deterministic Algorithm for Deferring Tasks to Human or Al for the Empirical Distri- bution and Expert Intervention Budget
Input: The dataset D, he human and classifier loss t and Eat and available proportion b of
instances to defer
Output: Labels of "defer" or "no defer" for each instance in D
1: procedure DEFERTASKS(D, L AAI, b)
2: Make the set A {( y, m) E D Lu(y, m) (1,(,)()))) -
3: if [A] 2 b|D] then
4:
Defer all tasks in to human
5: else
6:
Defer the bJD] tasks with the lowest y, ml - (2, y) to human
7:
end if
8: end procedure
improve upon such estimation of conditional probability and increase the accuracy of the obtained classifier. However, we argue that this paradigm is inapplicable the case of deferral rule as follows. Although the output ê of Algorithm 1 for each feature x is deterministic 0 or 1 label, it varies with the choice the dataset D. Hence, if we draw datasets from a distribution μ., the outcome f becomes probabilistic. In the following, we introduce two probability distributions (41 and μl (X,Y, such that for random draws of the dataset from (4i the conditional probability of such optimal deferral label f given X is equal, yet the optimal deferral rule for the true distribution is different.
Although the following discussion bears some resemblance with the No-Free-Lunch theorem [e.g. 66). there exists the following difference between the two. The No-Free-Lunch theorem states that for each learning algorithm, there exists a data distribution on which the algorithm does not generalize well. However, in the following discussion, we assume that we can observe infinite number of datasets and indeed, we can find the underlying probability of the deferral labels. In fact, we show that the limiting factor for finding the optimal deferral for the true distribution is that we only use deferral labels and if we use values of both losses, we can accordingly find the optimal deferral rule as suggested in Theorem 4.1
Assume that we have a dataset D {(x,, Vi, m,))"= that contains i.i.d. samples from the distribution μ.YM. Further, assume that we have no budget constraint, that is b = 1 in 2 Therefore, the optimal randomized deferral rule over the empirical distribution is the solution of the problem
min Σ Umity. P. + u (1 ft). [
is easy to see that the solution to this problem given by A; if 1 k(x)) < 1 and P: = if I Ma,))s m.sey As result, the optimal deferral is obtained as
1
m, = y Mxxx)) + y/
0
m; + ys, h((,)) = yo
(31)
any value in [0.
O.W.
Among all the possible policies, we can choose
n -== { 1 m, = y & h(r,) + yt
0
o.w.
Next, we assume that we have a classifier h and two probability distributions pi and l/ over (X, M). For both distributions X is uniformly distributed over [0, 1]. and we have 14 (1 (Y M,M(M = 2 /Y = M,N(X) # y)= and (Y * -)) served is are fixed for given choice of D. since D is randomly drawn, values are randomly distributed. Furthermore, the distribution of Pr(f]X) is according to Bern(?). since in both cases
Y)
3: PY = (X) * +Y= 3. We can see that although the ob-
we have (Y,YY = M, /(X) Y) J.2 However, the optimal deferral rule for the first distribution is (1) = 1 for all E X, since we have Lare rī) = O, while for the second case the optimal deferral rule is (x) 0 for all æ E X' because we have L (h,rz) J. Furthermore, such deferral
25

---

rules are not interchangeable, because we have (h, r2) (h. As result, Pr(f|X)
3: does not provide sufficient information for obtaining optimal deferral rule on true distribution. For an arbitrary choice of deterministic deferral rule for empirical distribution, we state the following proposition as a proof of insufficiency of deferral labels for obtaining optimal deferral rule over the true distribution.
Proposition G.2 (Ipossiiiility of generalization of deferral labels). For every deterministic deferral rule f for empirical distributions and based on the two losses my and 11 hiz)) there exist two probability measures Pr and (12 X y M such that the corresponding (f,X) for both measures is distributed equally. However, the optimal deferral pp and rps for these measures are not interchangeable, that is Lede (h, r(g)) S while [ (h, r for = 1,2 and j + i.
Proof. As mentioned in 31 there are four possibilities of deterministic deferral rule for empirical distribution based on the events hxX)= + and M + Y. The reason that
h(2) + y, m = y h(x) = m # y h(x) v, y, #g
8
h(z) y, m m
the parameters and b can take binary values. One of the cases in which a b = is analyzed previously in this section. We study the other cases as follows:
1. a = b,b= 0: In this case we have
{
1
h(z)
=
O.W.
If we define a measure μn such that
2
(x(() +Y,
3' m
3'
and a measure #/2 such that
-Y) na (h(X) = Y,M r) -3
then one hand one that f is according to Bern( ()) in both cases. On the other hand, because the probability of classifier accuracy is larger than human accuracy in μ1 and is smaller than human accuracy in u2, we have r (z) 0 while t (x) 1. Therefore, we conclude that
1
L (r h)
3
and
der (rarrriz Aeg h) = O,
while the losses with interchanging deferral policies are equal
Li (T hi) La (riz h) 2
3
2. = 0. 1: In this case, the deferral rule is
0 #
0.W.
Next, if we set two probability measures μn and μl such that
1 3/2
p = V,K(X) #1)))Y)) Y) = (M # YXX(X) = r) -)
3.
3'
and
1
( + YY,((X) = Y) - 3' p2 (M = Y,N(x)= (Y-))) =
3'
26

---

then f is according to Bern( 3) in both cases. However, ris = 1 while rjo 0. Further-
more, the expected deferral losses are equal
(f 3 (Ti h) 0,
while after interchanging the deferral policies we have def (r ht)
2 3
119 (r h1)
3. a = 1, 1: In this case, the deferral rule is as
- 0 h(x) = u.
O.W0
Next, if we set two probability measures μ1 and μ2 such that
((, = y)= 3 3' Ai
3'
and
#2 (,,()) (2 XY,( = X, 3
then see that has the distribution Bern 2.) However, find the optimal deferral policies for the true distributions are rn and r'2 O. Furthermore, we have
1
Li ( h) 3
and
2
Lus (Tipg: h)
3
while
1
1
Lite (r
Litr (r
H Proof of Theorem 3.1
Let X' = {#1...., } and y (1....,n.. We first show that obtaining the optimal classifier of (n) complexity, since in this case equivalent obtaining the Bayes optimal classifier in isolation. The reason is that, the unconstrained Bayes optimal classifier is deterministic classifier that minimizes
h (z) argmin Eprix (Y, =x]
for all x E X. This is regardless of whether the deferral oceurs or not. Therefore, this solution is further the solution to
h" (x)) E argmin Envix x - (X=
argmin E. MY [(1 ((X)))ar x) (XXX) =x],
for every rejection function r. including the optimal rejection function the constrained optimization problem. In the particular case of expert intervention budget, the constraint is further independent of and only function r. Therefore, the unconstrained Bayes classifier is an optimal classifier for the constrained L2D problem with human intervention budget. Next, we consider a specific case which Exy (Y,
x
Exyix (Y, æz] for all E X. and therefore h(x) over all input space.
27

---

Further, we assume the data distribution has the property μXYM pxx Y), i.. M = Y on all the data. In this case, we know that
E (M, = 1 X =x =0
=
and we define
E[eAr X] mm] B Y= x= m. 4.
Now, if we set Pr(X xz) = Pis and r r(x;) ri. then the optimization problem
f = argmin rh, r())
equivalent to
argmin (0,1) 1m1
Σ
Pr x xxxxxx+tpp rz) x la, s.l. E par S b,
that is equivalent to
argmaa (0.1)
pardl s.t. Σ Pite S.
(32)
Next, we show that the above problem spans all instances of the 0 knapsack problem, which is known to be NP-hard (Theorem 15.8 of (58). Let
n
argmax re (0.1)
TrGss s.t. Σ u.r S K,
(33)
be an instance of the 1 knapsack problem with Wi, Cs > 0, i E [n]. and K With K l Eim e./w Ps Σn = wi and Σn w. problem 33 can be written in the form of (32
cifur
Because of Em 4 1==1 = 1 this yields indeed a valid problem.
I Proof of Theorem 4.1
We start this proof by introducing a few useful lemmas:
Lemma L.1. The set = A of all functions that map to an n-dimensional probability is weakly compact, ie., for each sequence {In ) there is sub-sequence (fri} and function f E F such that for measurable embedding functions vb, we have
lim [((fme) E[(f" (((f".")) R)].
Proof. We know that all components of each element of the function sequence is bounded by 1. We define {Sim J as the sequence of the ith component of the function sequence. Therefore, using 42 Theorem A.5.1] we know that there is sub-sequence (fm 100 and non-negative 1-bounded
function fi, such that for each p- p-integrable function (z(z) we have
lim E, [ (z) A0000
(f)))
Next, we can repeat the same process for {f J where i [2 nı], and we can find a sub-sequence m+1 of mi and non-negative 1 bounddd function fū+ for which
(z))++1 = E, [fi+ (1)) lim E2 [ mi k
Now, since all sub-sequences of a converging sequence converges to the same limit, we can use my that is the intersection of all sequences and show that
lim E, f (x) E, [T))
"Note that in case that w; = 0 the Knapsack problem has a degenerate solution of r: = 1. Hence, we could drop that point and without loss of generality assume that w;
28

---

I. for all i E [1 nl and integrable functions v), As a result, due to interchangeabillty of limit and summation, when the sum is over a finite set of elements, it easy to show that
lim E (fmg, 80000
lim
E
(x)())(()))
Σ lim Blsgg(a)sst
Σ E. (ft( = Ex (z)) (x)))
Next, we need to show that f E F. We already know that all components of f is 1-bounded and non-negative. Therefore, we only need to prove that all elements of f sum up to 1 almost everywhere. If not, then assume that there a non-zero set A where μ(A) and there exists / > 1 for all E A. We know that there is either a subset B C A with μ [)) > 0 such that Er such that for x E B we have Ji 2 1 + I, or similarly a subset for which E; [x) - The reason is that otherwise non-7ero measure set A is union of two zero-measure set, which is contradiction. Without loss of generality we assume the first, which means E: (z) 2 1+ for
E B. Now, if we define (z) = [l..... 1] for r E B and otherwise (xx) = [0,... OJ. then we have
[f (x). (())) 2 (1 + l))(B),
while
Ep (f[g [+) 1,
for all & E N. This is contradction, because the limit of a constant sequence is not different from that constant value. Hence, f sums up to 1 almost everywhere, and that completes the proof. Proof of Theorem 4.1 We prove the theorem using the following steps: (i) for the class C' of prediction functions for which (f (x))] = 6; for E [1 : m]. we show that the supremum of the objective function (((((,, the (x))] is maximum, (ii) we show that it is sufficient for a predictor C to be in form of ( to achieve the maximum objective E (f tho (z))] in C and also for all predictors with E [f((), ehss (z:)) s 6; (iii) show that the space of all possible constraints for any prediction function in A is convex and compact, and (iv) we show that the tuple of constraints is an interior point of all possible tuples of constraints, then a point in C achieves its maximum if and only if follows the thresholding rule (8) almost everywhere
Step (i): Due to the definition of supremum, we know that for each 0, there exists function fe in C such that [[(fe, (x))) 2 sup E (f. (x())) - c. Equivalently, there is sequence of functions fn for which lim,- E B (>(x))) = sup rec E (ff, (=))) Using weakly-compant
of the function class A 1 in Lemma [.1 know that for the sequence fn. there exists subsequence fn, and function f" E h+1 such that
lim E [(ffa Um+ (+)) E [f (x), (m))(())]]
k00
Furthermore, we know that each subsequence Ong of a converging sequence a, has the same limit as the limit of the mother sequence o, [59] Chapter 2, Theorem 1]. Therefore, we have
[ (x), Wm+1 (x)) = sup E (J.
fEc
which means that the supremum of the objective is achievable by f" Moreover, for (x) where i E m). we have E((n, (x)) 5, for all n, which concludes
8, = lim IE ([ (2 = =E EE (x)))
k-o
This means that the equality constraints holds for f", i.e., f E C, if it holds for each predictor fa-
Step (ii): Assume that there is predictor f such that E[ + < 8,. In this step, we show that if exists a predictor f in form of (8) and in C, then of always has smaller objective than f. To that end, consider the following expression:
A = [(f((x) - f(x), vo(x))
Σ (x)]
29

---

Now, we know that
m
m
F[((()) - D
bxb(()))]] = Σ k (B((f()) ([
kg -6:- [[f(()) 20.
where (a) holds because ʃ E As a result, A 2 0, then we could show that E [([(()) f(x), tho (1))) 0,
(34)
and complete the proof.
To that end, first note that both f and f are in Ax and therefore (L. 1}} (f(z), [I...... .]) 1.
As a result, for any fixed scalar c, we have
(f(x) - f(x) - Σ -
(0(()) - Σ k(d)(()) - c). (35)
Next, we fix to be the maximum component of the vector v/o(x)) E (x)s(z), i..,
m
c :: max (x)(())
Σ (,))())}
=E[1:d]
Now, rewrite A using 35
A = E (f(x) - (o()) - -kvs())) - ot)
Σ - Σ (x)))()) ct)
Now, we consider two cases for which (x) fixx) > f(x)), and Ex(x): : f(() S f(x)).
If fa(x) > fa(z). then we have fz() > O, because 1 > fí(x) 2 0 for all i E [1 dj. Therefore, using the definition of Sa and because f E Sa we have
(x) kx))(()) = max {vb(2) - Σ ko))((a) =c
(36)
se[Lid]
Consequently, we have
E8 (()l))) - Σ (y0 c))
A
E [((((t)) - f(()))(v((()) - Σ ( (((x))-c))]4
Pr (+(())
m
E [((((=) - -(()))(
Σ [neo(()) Pr (E)())
1E (
Σ - Pr (E)())
where (a) holds due to (36 and (6) holds because f((x) S fi(z)) and (a) Σm (x) < maxie[1an+ 1) (x) ky)) As result, we have A > that concludes 34 and completes the proof of this step.
30

---

M
1
Figure 4: If an interior point of N has one corresponding point at M, then so are all interior points of N
Step (iii): In this step, we show that the space of joint set of expected inner-products
g { (E(((()) (I (z))). ".ff))),,,,,,(()),,,, (m))) AT
is compact under Euclidean metric, and convex.
To show the compactness of that space, assume that there is a sequence {g 1 such that lim,-+o 9n = 9. or accordingly there is sequence of fn E A for which limn-+oc (B](f( 4/1 (z))),.... E[f (x). then (x))) = (0......90 9m). Since the metric is Euclidean, this is equivalent to lim Bl(((()) (b)))baaaa))) (x))) = for all E [1 m]. The weak compactness of A as proved in Lemma L1 shows that there exists f* and sub- sequence Sn, such that lim BKfm, (I)), (x)) EK vx(()) for all E [1 d].
Therefore, because of the choice of Euclidean metric, we have
lim [B((nn th1 (+)) -... [B[ (x)) (.m(())))) 1-+00
(EI( (1()))))))))))))) EII"",,,"",,, (n)())))
which equivalent to compactness G.
To show the convexity of G, is enough prove the convexity of A The reason is that g(f) (E((f(z), th (x)),,.. ... (x), vm (z)]) is linear functional of f. and linear functional images convex set to another convex set.
To prove the convexity of A let f, E A. This means that f((x) [0. 1] for all
E [1: :d] and Ei=1 f((x) Ei=i ((x) = Consequently, af((x) + a1) 2
since a, 1
0. Moreover,
+ (1 a)f((z) a E /(xx) + (1
a) >² fx(x) a++1 =
result of these two facts, af + a) Az. and
the proof of this step is completed.
Step (iv): In this step show that if the tuple of constraints is interior points of all possible achievable tuples of constraints using different prediction functions, then a point in C achieves its supremum in terms objective E {f)),, (x) ] if and only if it is in form of (8) almost everywhere. This is an extension to [21] Theorem 3.1] and its proof resembles to the proof that is provided there. The sufficiency is already shown in Step (ii). Therefore, we
only need to show that if a prediction function in C maximizes the objective, then it is in form of (8).
Firstly, using Step (iii). we know that the space N of all points [K) 2h (z)) Eff(x), aim (=))) and the space M of all points (EK)(r), 41 (x)) Eff(x), (x))) are compact and convex. Now, assume that V (d)...., )m)) an interior point of N. Then, the corresponding set in M, i.e., B, ((6 ..... dm) EM åp E R has supremum and an infimum of the first compo- nent that we name 8** and 8*. Now, since M is compact, then v** (8** S1,..., 8m) and v' 88",81..... .i....., 6m)) are contained in M. Next, assume the following two cases:
31

---

1. 8t = = In this case for all other points T = (ō1..... 3m) of NN the corresponding set B in M is single point. The reason is that, if is not so, then we have two points J" = =6" 81....,8y 8m) and ग- = (o .i..... 5m) where 8² > 8". Now, since o is an interior point of N. then any direction in a small neighborhood around v there exists a point v' within N.. Let that direction be opposite the connecting line of and E, ie., let be points v'. v"*, and '² which are all in M. Because of the convexity of M, the convex hull is also subset of M. Since u is an interior point of the convex hull, this means that a neighborhood of v along any direction is inside M. Now, if we set (m + 1)th axis to be that direction, we contradict with the fact that 8 8 (See Figure ! Now, we know that in such case all points within .V have in M.. Because of the convexity of M this is equivalent to M being a subset of
connecting line of o' and 8. Now, make convex hull using the three
corresponding point
hyperplane with the generating formula Zo = Σ -i=1 k5z; + ho- Therefore,
have E [[[ [b))
[ >m Axddba] + Ko for all A Therefore, for d 2 2, p(a) - p(z), pla)
if we set fi 2-2
p(z)
p p(a) and f2 =
p(2)
p(z)
p(z)
p(a) pla),
for p(x) E 10, 1j then we d=2 d=2
p(a)
8-2
2
2
have
B[f,, + - -E((,, >
kabiil = B[(2 vo)l - -E [E((2, kwbi)
or cquivalently
E - (1-p(())(e6(oo) - Σ kev)(() - (x) +
Σ keb)( = 0, 1=1
for all function p(x)= A A similar result can be achieved for d = 2 and by setting fi = (p(x),1- - p(x)) and f2 = (1 - p())p(()))))))))) p(x)). As a result, we have
m
(x) Σ kv v((2))
Σ (o)
for all #jj E [1 d]. and consequently
m
m Σ Baol
vx(()) Σ (x) max (1)
jE[1:d]
for all i E [1 + 1]. As a result, there is a set of ki...., km such that (x(x)) Er (x) has equal components almost everywhere. As result, due to the freedom of choice for T(Wo(z)) Σm (x)) x)) where т E Sa and when we have more than one maximizer component, then, without loss of generality we can assume that every prediction function f almost everywhere is in form of r (fm+1(x)
ETh keb) x.).
2. 8t > 8": In such case, for all ôn E [8*. (8*), we can show that = (Sp...... 8m) is an interior point of M. To show that, we first find m points uf,...., uy E N that are linearly independent and such that their convex hull include (01,..., 6m). Using the definition of M, for each of these points o/ (8 ..... 8yn"" ") there exists hy R such that e/" = (h/, 87 ...., 8 ') is within M. Now, we add the two points 2** and v² to these sets of points. is easy to see that u/'s are linearly independent. Furthermore, we know that (01....
5m)) is a convex combination of o/s, i.e., Σ; a,,9 (8), .i....... )m)) As a result, if Σ, baul 8 = (O....,O) 0), then we have b, = a, for i E [1 m]. Furthermore, we have Σ Eahh = Eb = gr Similarly, if >, cul"
(0.... 0) we have e; = a; and Σ an = Ea 5". As a result, since 8* * 8** at least one of these cases would not occur, or equivalently, the dimension of the convex hull of r'!.... on u** v" is of dimension m + 1. As result, is interior point of
32

---

this convex hull, and because the convex hull is (m + 1) dimmensiin it is an interior point of M.
Now, since n** is border point in M and due the convexity of M there is hyperplane P such that passes "** and it lays above all points of M.. Since u is an interior point of M, a neighborhood of laid under the hyperplane P, hence v cannot be laid on the hyperplane. Therefore, if the generating formula of such hyperplane is Σ -==0 kg - Ei= Kjō + kyō" since not laid the hyperplane assure that _i=1 i== kşØ; + koōn * Σ h5ō; + knd or equivalently ko O. Hence, without loss of generality assume that ko = -1. This shows that for all points in
(uo.-... Um) M we have
M
UAO
kju S 80
Σ kj
equivalently, by the definition of M, for all prediction function f, we have
[[(((r), Σ ((/s(())))] S 8
Assuming that f E maximizes the objective, we have
((((z)))o(()) Σ (x)) s [[(f(t)) - Σ k()(())))
(37)
This shows that almost everywhere when there is unique maximizing component The reason is that otherwise and if there is a set A such that ((A) > 0 and for x E A and a choice of E [0, 1), E R, and m (2) >i (xx while -i=1 k (x) 2 + 1ir
in (z) Ei= krps (z). then fy (z)
all / + we have vin (xr)
f, f(x) [0,
I, then we can make a function f fx) that is f(x) = f(x) for x E X A and
0J for E A. Such function leads to
m
m
E [ff(z), vo(=) Σ
(x)()))))
Σ (x)))
that is in contradiction with 37 This completes the proof of this step.
J Proof of Theorem 4.2
In the following, we introduce a few lemmas that are useful in our proofs.
Lemma J.1. For every random variable X T2 have
lim Pr(r - X
< t) lim x
-----
Proof. For each increasing sequence [ we show that the first limit is zero, which proves the claim that the function of 7 has zero limit. We define
S, = [T)tt))
and notice that
S 2 8g ....
Further, note that
0 S = 0.
1=1
As result
S C 85 ....
33

---

and
-
i=1
Next, because probability measure is a-additive, we conclude its lower-semicontimiity 38 13.6], and therefore we have
Theorem
lim Pr(X E))) = Pr(X E S = 1-000
which proves lim;-sso Pr(x S.) = 0.
We could take similar steps to show that since Ni=1 T/) 0 for decreasing T/ we have
lim Pr(X (t, 0.
Lemma J.2. Let 1h : X + Re be a bounded functionnn Further, we define two functions C(k) (z) th (x)) ((k) = (x). and F(k) = E [[f2, (I), vo(x))] where fk.p is
defined Theorem 4.2 Then,
1. (lk) is monotonically non-increasing,
2. (1k) is upper semi-continuous.
3. F(k) is monotonically non-decreasing,
4. D(k) is lower semi-continuous, and we have
5. limmrr C(k) = limgres D(k)
Proof.
1. Firstly, let define (x(2) v/o(x) (z)( For the setting where p 0, the prediction function (x) is defined as
{
1 min argmin jeargmax (<))
(z)(
Skol:, 1)
(38)
0
otherwise
Further, for k1, k2 such that 1ı S k2, let us define ji and je as the only non-zero index of (z, p) and (2, p). respectively. To show that C(k) is monotonically non non-increasing we only need to show that (x)) (ii) = (Jk, ((,, thi (x)) 2 ((x), th (x)) =
(Wa (z)) Assume that this does not occur, equivalently (i) < (1). In such case we have
max EA (x) (a)
(Ek, (I:) (12)
(lk, (x) (k2 (112-ha k1) (z)
S (K) - (2) max (4,, (x))
@ (k1
(z)
2 (ki - -2) (f,
(z))
(39)
where (a) and (b) holds due to the definition of j and jz, and (c) holds due to the assumption (i)) < (vh (i)) The last inequality is clearly a contradiction, and shows that (o) 2 o th (z)), and therefore C(ki) 2 C(k2).
2. Let divide the space X into two subsets
{ x x: (rgmmx((((z))(() = d).
A
By x E x:
(rg))a((((()))0)) [1:
34

---

For each x E Aş we know
(Fio(z)) {
1 i min (argmin (11(
0
otherwise
Using previous part, know that by increasing k we have no increase in (z), thi (a)). and in this case since (fū,(()), the (a)) = miny (1) then this value cannot reduce with the change of k. Therefore, (fE (x), wh (x)) is a constant function for all k' 2 k. and consequently [[ff (0(), th (x)) a As] Pr(x A&) is constant function for k' 2 k. If Be. then for j & argmax (1) and I E argmax (4x( we have (4x))) < (4) Define the set Co for 2 as
Cs = f E B (cx(z))() S (cx(z)) 87.
Using Lemma J.1 we know that
lim Pr(Bg \ Ca)
6-0
or equivalently for all 2 there exists d such that
Pr(Bx Ca) S
Therefore, without loss of generality, we assume that t/1 (x) is bounded by 1, then there exists 8 2 0 such that we have
E (f (z)) (x)))
B& C3. Pr(x EBx \ C3)
s [1)() Pr(x B& Cs) s c/2,
where (a) holds due to Hölder's inequality. If x E Cg. and because assumed || (x))lb S then we know that by increasing k to K E [k- 5/2, k + 8/2), we have
I argmax (x) C argmax (x(x)= J.
(40)
This means that
(i = min (1h (z)) < min (z) = (5x (0 thi (x)).
jEJ
jEZ
This, together with the previous part in which we showed (fr,o(z), vo(x)) > ( (x)))) concludes that (fā,( vo(x)) = (f²) (>)()))) This means that E [(ft o (z), vb(x))) C³) Pr(x Cs) is a constant function for all k' 2 k. Finally, since we have
C(k) = B(( (x)) [E(( (x)))) E Aa] Pr(x E A+)
+ (() + E (x), (1())) E C3] Pr(x C.),
e B& Co Pr(x E B& \ Cs)
and because the first term and the third term in RHS are constant in terms of k and for k' 2 k, and the second term is diminishing, then we have
[C(K) - C(+) = [B[ ( dh (x)) B& \ Cr)Pr(r B& \ C8)
((f bI) E B& \ AC& Pr(x Ba A.)) < e/2 c/2.
which equivalent to say that lim C(k') = C(k).
3. For p = 1, we know that the prediction function fi.p (x) is obtained as
i min argmax jEargmax & (1)
(vo(z)))))
(x)
otherwise
35

---

If we define (x) == (2)( then we have
== min
argmin
(v1(
(2)
jEargmax (a)
otherwise
Since the above is equal 38 then using the first part of this lemma, we know that IE [[],,()), (x()))] = E T (z)), (x)) is monotonically non-increasing, which is
equivalent to F(k) E ( ()()))) being monotonically non-decreasing.
4. This part is similar to the second part of the proof. In fact, if a E Ag, then we have
1 i min mirgaaxax (e)
(f)(())
(41)
otherwise
For k' < k and because of the third part of this lemma, we know that (fiz, (x), th vo()))) >
(2),, (z())). Furthermore, because of 4 we know that (2), max (2(2)) and therefore by reducing k', the prediction function f stays constant.
(2), vo(x))
As a result, IE| [(ft (z), th (x))x E As] Pr(x E As) is a constant function for k' S k. Furthermore, similar to the second part of this lemma, we can show that for each e > 0, there exists 8' 2 0 such that for all 0 S 8 S 8' we have
[ v (x)) E B& C3} Pr(x B \C)
11 (x) Pr(æ E By CB) S e/4, (42)
Moreover, for the case of x E Cs. since in this case I C I, then we know that (fR,(()), vb(()) = max (Vo(z)) & max (vo(z)) = ( (x), JEI
(43)
JEJ
Next, using the third part of this lemma, we know that for ky' I k we have (ftr) vo(x)) S (ff, (u())), which together with (43) concludes that (ft,(1)) vo(2)) = (fi (z), (o(())) Next, because (v/((z) - kv (x)) = (v)
ka/ (1) for i,j E J. then know that (4) (+)
(k:
#) ((1) (Wh (x))) < 2 k/ Therefore, if for i, I we know that (1)( = (No(z)) (1), then the difference between t/1 for those indices is bounded as (x)) - (v)( = | (v)(=))) - (vu()))
+ (4((()))()) - (4x(=))()
s 2/k K').
(44)
Now, we know that because æ E Cs, then (x), wh (x)) (vi(z)) for e argmax (I), and (x), (x())) = (z) for j E argmax (V)( JEJ
kee
Hence, we can see that i E J S and j E I, and because (v)( = (ft,)))), vo(z)) = (1), vo())) = (I) and due to (44) we have th (2)) (1),
(J sh (x)) S 2/k: - kk',
as long as K' E [k k/2,k). Therefore, if we set 8 = max(5'.e .e/2 we have
(z). (fe (z) </2,
and therefore
L (1 C³] -E]-E(((i (z),
< I ( (x), vo( (i) vo(x)))] Se/2
(45)
36

---

Finally, we can rewrite D(k') as
D(k') = BB vb(4))]]]]] - =I[ (4), (o())) E As] Pr(x E A&)
BB (o) vo(x))) BN Ca) Pr(rE Be \ CB) E [ vo( E Cs) Pr(xr
and because of (42) and (45). and since the first term is constant function in terms of k
and for all k k 8/2, kj. then we have
[Dk') D(K) e/4+
(46)
This shows that D(k)) is lower semi-continuous around k' = k. 5. To prove this part, we first divide X' into two subsets
GE
fxr E X'
(rgmax((x= =1}.
(47)
and Hy = X') Gg., We know that for E Ge we have
firo(z) (2) {
1 min E argmax CN (x))
(48)
otherwise
This concludes that
[[(fk 11 (x)))) E Gr] (1). GR].
(49)
Moreover, let define the set V argmax (x),, (x) = cJ We show that sum of the probabilities of Hy \ T is always bounded by 2d for a set of choices for k', or equivalently
for x Ee
R, Vj
Σ Pr(e Hy \ w 2
(50)
for all finite or countably infinite choice K. S Rt In fact, we know that for each instance argmax (f) can take up to 2d cases of all subsets of {i....,cl d]. Therefore,
je(l.d]
need to show that there cannot exist two values of k, K such that for x (H& \ v/t) n
(Hwr \ w we have
argmax (L)( = argmax (z))
(51)
If we prove such identity, then due pigeonhole principle, we have
Σ ILEEH 2d
(52)
MEK
which by integration over all values of x concludes in (50). We prove this claim by contradiction. If we assume k. E K. such that for x E (Me \ wh n (Hl \ w(') the identity (T) holds, then because E Hg O Ha, then the size of argmnxx (f) and argmax (z)) is at least 2. This concludes that
(Vo(x) knhn (a)) (i) (1bo(x) kw/h (x))
as well as
(vo(x) - k (x)) (i) = (voll)) k (z) for all choices of i.j argmax Es (x). As result, we have
(k k') ( (w) (z)) tn ()) 0.
37

---

and because k' * k. we have
= (1)))))))))))))
for all j.j E argmax E (1r). Therefore, x E 'Vf' and that is contradiction.
Now that know that the sum of the probabilities of Pr(æ HE \ w is bounded, can renormalize that and make a probability measure as
Pr g(4) WheA Pr(x E HA \ w1))
(53)
ExPr(eEM (4))20 Pr(x E H₂ \ (P()
Due to Lemma J.1 for all E 2 0 we can find small enough 8 2 such that g( - 8, k)) v c/20+1, and therefore for all k' E []: 6, k) we have
Pr(x E HE (44)s
Pr(x E H. \ V1)
NE (k - P.I, (
g((:: 8, k))
Σ
Pr(x H& \ w/
k:Pr(eEH, (4))00
S 2d+1 2d =12
where the last inequality holds because of (50). Now, using this and due to (49), and by defining g. can bound the difference of (ik) and ((k) as
for = 1, 2, we
D(k) - C(+) = [[g go(x)) x E HE] Pr(xr E He))
S Pr(x E HE v x H ((9n()) - go(x)]
Hy \ w + Prrl e Hy n w |a Hz) (() go(l) E Hy Hy ]
2 2(c/2) + [[g((x) -o(x)) He He n
(6)
e,
where (a) holds because |15t, - skalla S 11//,ol1 + 155 11 = 2 and because of Hölder inequality we have (ffo(=)) - fi.1 (x))) s 11fã - fh. laallall s 2. Moreover, show that (b) holds know that for V have (v)(
(z)()))
for all i,j argmax (z). Therefore, because we know 90(x) (x) for argmin (z)( S argmax (x)) and gi (x) = (v) for j e jEargmax (4))
argmax (vo(z)) (j) C argmax (4x (I), we have go(2) g1 (z). The above
jEargmax (1)(())
inequality proves that the limit of C(k)) and D(K') for k' h are equal and that completes the proof.
To prove this theorem, we take the following steps: (i) We show that the set IC has non-negative member, (ii) we show that the prediction function fū (x) achieves the inequality constraint tightly, and by Theorem 4.1 we can conclude that (2) (x) is the optimal solution.
step (i): It is easy to see that the Bayes optimal solution of the prediction function in without any constraint
(r()) {
(vo(z)) (v)( for all j + i (v)( < max, ()) otherwise
(x(x)
38

---

where pi(x)) E Da is an arbitrary vector. We can see that by setting
{ 1 j min argmin
(1/2 (z)
(p)(
tEargmax fo(x)
0
otherwise
then the two prediction functions f (a) and fo,o(2) are equal (See statement of Theorem 4.2)
Now, in the first and second part of Lemma J.2 we have shown that [[( t (2)) is upper semi-continuous and monotonically non-increasing. Therefore, for all l E RR+ we have
B B[( di (x)) & ((),,, si (x))] - (1)
Similarly, we can show that for k xc, the solution is equivalent to the Bayes minimizer of (x) argmin B (f(z), (x)))
SEA
Therefore, since 8 is an interior point of all possible values, lays on the inter- val (E((f**xx) the (Ir) (h),) ). due to the montonicity and upper semi- continuity of B[(JE 4/1 (1))) E [[[[,o(F) (z), wh (x)) < 6 < lim [ th (+))]
find / such that
(54)
rtt
Moreover, this t should be positive scalar, since otherwise have
E (f) u/ 2 E (z), = El( > 8,
which is contradiction to (54). step (ii): In this step, we consider the following two cases:
C(t) is continuous at In this case, (44 equivalent to C(I)
which means that the prediction function fz achieves the constraint tightly, and therefore using Theorem 4.1 fz is the optimal solution.
E [[
C(t) is discontinuous at t: To show that we can achieve the highest constraint in this case, we first condition the constraint into two events x E Gk and x E X') Gk. where G is defined in (47). We know that in the latter case x E X' \ GR. the prediction function fk.p can be decomposed into two components
(x) (x) + (1 - -)))oo()))
(55)
while for æ E Gy the prediction function fkip (x) = fk,((x) = (x) for all E [0, 1]. Therefore, in both cases (55) holds, and we have
E [[ (w), th (z))]
E[ [(pftt (2) (1 p) (z), tb (x))
Pl (c) (x))) +1 p) (1)
= pD(k)+++ (1-))
(56)
where C(.) and D(-) are defined in Lemma J.2 Using this lemma, we know that D(.) lower semi-continuous, and limp C(k) iim (kk). Therefore, together with 56 and the definition of p in the statement of theorem, we have
E [[[Kk,p(a) vb(())) =p
lim C(k') + (1 p)ckk) WTt
C(k) -
lim O(k) FYR
C(k) - lim C(K)
limp'a C(k))
C(k)
(57)
C(k) litne C(k)
Equivalently, the prediction function achieves the constraint inequality tightly, and therefore by Theorem I. this is sufficient to be the optimal solution to the constrained optimization problem.
39

---

K Proof of Theorem 5.1
Through the proof of this theorem, we use [6 Lemma 3.2.3] that implies that the class of multi- plications of binary functions fz(x) for i E [1: kj within a hypothesis class with VC dimension (fff) = d itself has VC dimension that is bounded as
vC II Sa J. H. VC(H)) dd) S 2dk log 3k.
(58)
In fact, we use simple extension to this lemma for which the VC dimension of the functions is not itself but is bounded above by d. In such case we claim that (58) still holds. The starting point for
the proof this lemma is bounding the size of the restriction (Ix (4 n S h H) for the hypothesis class H by
(x())) & (em) d )
(59)
where VC(H) and m S). However, this inequality holds for the hypothesis classes that have VC dimensions that are bounded by d. The reason increasingly monotonicity of RHS of (59). In fact, by obtaining the gradient of (ar)) in terms of d we have
0(
a(ellog log om/id) (log em/d / - 1)( em
Od
Od
which is nonnegative as long as m 2 d. If we particularly set m 2dk log 3k, then m² 2 d and therefore (59) holds. Next, similar to the proof of (6, Lemma 3.2.3], we can show that for the set S with size m we have
He (S) - II (S) S
em
dk
2
which means that S cannot be shattered by H'', and therefore the VC dimension of this hypothesis class must be bounded by m². We further use the following lemma:
Lemma K.1. For arbitrary sets of functions { and {d)(=)} R and for given E IR the hypothesis class
H II (g) k0)(2) - d) R),
has the VC dimension of at most 4.
Proof. To prove this lemma, we show that the form of the product in the definition of H. reduces to the form of an interval on R. which is known have VC dimension of 2. In fact, each term sgn( (x) - (a)((a) (a: d) can be rewritten as
sgn( (z) - (x) d) ssgn( (f())d - ())gn(((()))) + sgn(k: (1(0)
(x) ((o))")sgn(( *5(x)
)sgn( (oggn-00(000 (x)(
sgn ( d)) 6))(=)=
As result, by multiplying all terms have
sgu sgn( (xf - (x) d) = sgn min (x)-d k)sgn(k: h max (x)-d
sgn( (x) d),
YEA. (2(*)
(EB
2z(x)
sEC=
(60)
where Ag. B., and C2 are defined as A, {ie [] (1(x) > 0}, B, (i [1 n| (z
0}. and C₂ = fi E [1 [1:n]] (z))) = 0}. Now, we see that the first two terms define an interval
for l E (f)(), J2(x)) where (1 = maxies, [5))
(x)-d and f2(x) = minge., ((())-d Next,
40

---

we prove that the VC dimension of the hypothesis class of all such functions is less than the VC
dimension of G = {f IR x R - {0, 1} f(z. y) = sgn(x kj k1)ssn((2 y), ky, kn E RJ. The reason is that if the aforementioned interval can shatter set S, then we can find the corresponding
values of (x()) and [2(x) for each x S, and then form the pair (1). where 2; = fi (2) and
y: (x),, and by setting K1 = l2 = k, we can shatter the set {1i,, v:) [S] with G. Note that here all pairs are identical. The reason that if not, i.e., if (1r)
Ji fi and f2(2)) - f2(x')
for ar, x E S and x * x', then, for all possible k we have sgn(k: fi (s)))) (2(x) k)
sg fi (sn'))))((((( (((==)=B, k). and therefore we cannot shatter S by sgn(k - fz(z) )sgu (f)()) - k). Therefore, the set ((x,, De) ) has the same cardinality of S, which in consequence proves that the VC dimension of all sgn(k: - S1 )sg(((222)
k) is bounded by VC(G). Moreover, VC(g)= < 4, since for each 5 points in two-dimensional space, one is in the convex hull of the others, and in case that all others are labeled as 1, the one in the convex hull also must be labeled as 1. As a result, g cannot shatter 5 points, and therefore VC(G)= I 4.
Up to now, we have shown that the class of functions equal to the first two terms of (6)) has a VC dimension that is bounded by 4. Next, show that multiplying a hypothesis class H with binary function (xx) does not increase the VC dimension of that class. More formally, if we define
H = {((x))(x)) : f }.)).
then VC(H) S VC(H). The reason is that if we can shatter a set S using H. then for each member x E S there exists two members f2 of H'' such that (x) = 1 and (2(z) = 0. This means that would not be achievable. Therefore, Φ(x) = 1 for all x E S,
Φ(z) of 0, because otherwise fi (z)
and as a result similarly Ht' can shatter S, which proves that VC(H) I VC((").
Finally, since we know that the class of all functions in H is in form of sgn(k: f1())) (f((z) k) multiplied with binary function, then we conclude that VC(H) S 4.
To prove the rest of the theorem, need to show that for all choices of is and ò the difference of the empirical and the true loss is bounded. In fact, we should find bound in form of
Pr sup k.p
Esn (fE <))())))] E1 [f (x), vo S dn 21-c.
Here, we divide the class X' into two subsets G2 and H3 X \ Gg, where G₁ is defined in (47) Now, using the definition of (x)), we know that within G2, the inner-product (f can be rewritten as
(r), v1 (1))
(5), = (v) (argmax (I)
(bi())) II sgm (lx(=)) - (i) ifj
(1) II sgu sggg ((Vo(=))() (vo())) < (())))))))))
Now, we can condition on being a member of Gg, and therefore the maximum difference between the two empirical and true expectation is as
Bs [(FE (2), d (x)) x Ga] - E (x) I Ga]
sup k.p
d Esn (vI( (x) |x E Gi - (v)((()))) (0000))2,600 (x)
<
Σ sup J=1 k.
(61)
Now, we bound the inner term of (61 in a high probability setting. To that end, we use Rademacher's inequality in 66 Theorem 26.5], which shows that maximum difference between the expected value
of function h E H over empirical distribution and the true distribution is 2R(7() + 44y In 4/c where R(H) is the Rademacher's complexity of the class of function H. and e is maximum value that h can take. By defining
h(xx) = (v1( 07(xx),
41

---

we have (I())(=))()lll= S 1. Therefore, we have for all h,
In Ad/e
sup gn [h(x)] R, [M(c]] S 2R(H) + 4V he7
(62)
n
with probability at least 2. Now, we can use contraction Lemma [66 Lemma 26.9] to show that since [1(121 ()ll> < 1, then R(H) R(F), where F = { (z), e R). Moreover, F 1 binary functions all of
contains functions that are all multiplication
sgn (z)) (th (z) (<(vo()))()) (v)(=))
Lemma K.1 shows that the hypothesis class that contains products of all such function has VC- dimension that is bounded by 4. As a result, the Rademacher's complexity of F is bounded using 47 Corollary 3.8, Corollary3.18)
4log en/4
R(F) S
n
and therefore together with 622 for all h E H we have
4 log en/4
In 4d/e
- [x(x) E [h(x)] 2
+ 4V
with probability at least J. Hence, using 61 we have
Esn [(FE, |x x [x E, [x]( (/)))((())))) x G+]
sup k.p
4 llogel/4 S \
4d/e
+ 4dv I
(63)
with probability least In the last inequality, we used Bonferroni's 's inequality on c/d bad events that each summand of (61) is not within the concentration bound.
Next, we consider the region H& which there are at least two maximizer components of (x(x). In this case, by definition (x)) among these maximizers, we choose the first maximizer of tho (æ) with probability p and the first minimizer of v (x) with probability p. Therefore, by condition on these cases, and if we define
E(k, p) = Es (ffxp()), (x)) I H&] Ep (1) 1 E Hs}
(64)
then we have
sup E(k,p) S sup pu 1) (1- < sup E(k, 1) + sup E(k, 0). k.p
(65)
k.p
ky
Now, to bound Ekk, 1), we first rewrite the closed-fon solution of (z) as
(z))( sgn (e)) max (ce(z)) d) II
10 (x) II Tuy(s),
(66)
is1
where (z)(x) and uny (x) are defined
(5(x)) =
(( (e)ta)) (()()))
and
(x)) = 1 (o) (s.()) (1)
respectively. Note that the only difference between the definition of uny (r) and (z)(x) is that uny (x)
permits the equality of (vo((z) (i) with other components, while that is not the case for (x)) This difference lets us find the first component with the largest value of vl)(x).
Now, we can rewrite sgn (z)) Z max; (E& (z)) as the product
sgn (e)(=))) max (L)( - a)
II le(L:d]
sgn ((L((=)))) (la(=))(1))
42

---

As shown in Lemma K.I. the class of such function has VC dimension of at most 4. Further- more, multiplying a hypothesis class with a function such as sgn (() 2 (V)(z)) and
sgn (()) ())())))))) does not increase the VC dimension (See proof of Lemma K. and neither does negation. Therefore, in RHS of (66)
count d number of functions, each with hypothesis class with the VC dimension of at most 4, and therefore using the early discussions in this proof (58). (fe, (zr) (i) is within a function class with the VC dimension of at most 8d log(3d).
Therefore, similar to 63 in previous part, we can bound suPk.p Elc, 1) as
Sd Bolog(3d) log(en/ (8d log
sup B(k, 1) / k,
n
In 4d/E
+ 4dy
(67)
n
for / 2 Sd log(3)) with probability at least 1 - We can similarly, show that supk.p (Ae, 0) is bounded
8d 8dlog(3d) log(en/ ((8n + 8) log log(3d)
sup 0) s k.P
n
In 4d/e
+ 4d
(68)
Therefore, using
63
64
and the application Bonferonni's inequality we have (ff (Ir), vo
65
67
(68)
sup k
Egn
E
el 8dlog(3d) log (8n+8) log + 12d
In 12d
s 6dl
(69)
dn(c),
(70)
with probability at least c. Therefore, by assuming Es- [(fE,(()) 2b (x))) S (c) we
assure that E, [[fR, (x), wh1 (z)) S a, with probability at least 1 e, and this completes the proof.
L Proof of Theorem 5.3
We first introduce three lemmas that are useful in proving this theorem.
Lemma L.1. If 5 is an c-interior point of the set C = {E (f(x), (x())) f A }. then ó is
(e/2) -interiit point of D {EEs= [(fx), sh (x)) If } with probability 1 - 2e 422
Proof. The proof of this lemma is direct application of Hoeffding's inequality. In fact, for || 1// z C' that inequality together with Hölder's incquality imply that
Pr [1 th dh (x)) - Es- [[]((((())) thn (=))] 2 2</2) S 20
Therefore, if there exists fi such that E,, (x), si (z)) e, then with probability least 1-e we have Es= (x), vh (ar) E /e/23e/22 Similarly, if f2 exists such that E, ((]((())), 4 (x))
n.? we have Es- [(2(2x), (x))] E 12, -c/2]. As result
-6, then with probability
of Bonferroni's inequality, with probability at least 2e 1ez both these events happen, and because of the convexity of the set 'D we can say that with such probability all values between
ag E [-33e/2 3e/2, -/2 and a E [e/2,3e/ 3e/2] are D too. This, of course at least contains the interval [
Lemma L.2. Assume that we have an approximation ii (x) of (1(x)) with the error bounded as [| - th (x)lloe S e. Further let é' E .R such that e' 2 e. Now, for a E (--',e') there exists a rule f E A such that [. [ff()), (z),)) 1/ (x)) + o, then there exists as well as p E (0. 1]
such that E,, ((f,, (1 = 8 S..
43

---

Proof.
Firstly, because of Hölder's inequality we know that
Bn [(f(2), [x())) - [y(((()), (1x))) <ellfE = E,
for all f E AT. Therefore, by setting o é' and σ =E', we can show that for E A such that
Ex (1 = = d
then
E (f 20+6 -,
and where for f2 E A
(/2(()) = 6-6's
then
Ey ((f((t) @ (x)))] c6c
know that the set of constraints for all rules within A is convex. Therefore, since we can achieve two points J2 such that the constraint Epp [f](())) vi (a:)} can achieve two points above ó + e' - and below 5 - é' - e. then for each c E 16
Now, because of step (iii) of the proof of Theorem
+ e, 8 + é' - E] there exists f E A such that [E, 3 (x)) = c. Now, 2. In the following, we show that there exists & R and p [0, 1] such that further E [[kk,pa)) 1i (x))) c.
let c= 5 d'=c
To that end, we first remind that Lemma J.2 shows that E (f & (z))3] is monotonically non- increasing in terms of k. We show that for E R we have max (x) - (f), (x)) - - The reason is that if E argmax (vo((:) ka (x:) (1) and j' E argmax (z)) (I) then we have
(No(2)) (z)) 2 (vo(z)) - (*)()))
which concludes that
-+((((())) - -(5(())))) (oo(z)) - (vo(z)) 2 -2
Therefore, since
E [argmax (x), (x)) = max Ex [f(x), (1))) 28+6-6 -
where the last inequality holds due to the existence of fi, then for k 5 -8/(6'' - E) we have
2
2 8 = cc
En (ff..o())), & 28 - -8/(e' -c)
Similarly, if we let & 2 8/(e' - E) we can prove that
(ff,o,,())) (x))) S - é' + 21 8- c -c
c'
8 As result, the set C = (k: E,, [R (xx), & (x)) 2 cf is non-empty and bounded below by - Therefore, its infimum exists and is also bounded below by -
& - Let us name that infimum k. Now, (x),,(
if E, [ff,,,,(z))) &n (z))] is continuous at k = k, then we can show that E., (f) (x)) = c. not, then as shown in step (ii) of the proof of Theorem 4.1 and in particular (57). there exists p such that Ey [f (z), V1 (z))] = This completes the proof.
Lemma L.3. If I1 volloo S ôn and 11 villo S 6n and for k E [-K, K}. and k' < 2(80 + RC8:) for T E TR+,, then we have
k
=[(f f2r -
((())) ST.
44

---

Proof. The proof of this lemma bears similarity to that of Lemma J.2 <b(x)) (z))()) Next, we have
Here too, we define (x(z)
{
i = min!
argmin xEargaX (fx())
(1())
fko(T)
(71)
otherwise
Next, we need show that (i) (rw,o(z), (1 2 (60))) (#o(z)) - T. Assume otherwise, meaning that (#) (51) < case, have
(z) (J2) - T. In this
max (x) @0) (i)
(4a(z)) - (do(2) (o()) (({((z) t (2)) (fz)
(4x((z)) (i2) - (h ())((())) + (Vo(x) - vo(x)) ((b1(x) - (z))
(2)) (k (b) (6o Kσ1)
2 (ex())) (K ()(((())) (k k' T' (ōo + K
2 (cx()))(() - (I: - (+)) (h: K'T + (ō0 + K(1)
(2)
50 + Kō
S (ex())) (A: (1))
T + (60 + K(1)
T
(4x(x))(1) (k: (+) (6. + K(τ)
((x(z))(11) (6o + Kσ1)
(4(()))(11) - (6o + Kō1) - -(o(x) vol())) (fi) - (t))
2 (b(()))(1)) (ōo + Kō1) + (ōo + Kτ.) (f),
which a contradiction. Note that (a) holds because of definition of ja and (11. (b) holds due to approximation assumptions I/vo volloo < 60 and || t1 ll S 61. (c) holds because of the assumption (z) < (1I - TT (d) is followed by the definition of j1 on
maximizing 4 (x)), and (e) holds because k 2 k' 2(6)+ and (f) followed by approximation
assumptions.
We first formally express Theorem 5.3 as following:
Theorem L.4. Assume that (8 el, 8 + ex) a subset of of all achievable constraints ((f()), th (=))], and that [1)x I for i 1.2. Further, let the size n of validation data be large enough such that do/3)/) & g. Now, if the optimal predictor (F)(a)) is (%, A)-
1/7
and 7 S 1, then for n 2 16 log 3, and with probability at least 6, the optimal empirical classifier, as of Algorithm has objective that is at most Do-far from the true optimal objective where Do is defined
sensitive around optimal K- for A
7
2 max (d, 50) (6.16/3).00)""
1/7 + +4V
2(5 + Ko₁)
[[ (z). [o(]))]]]]]]]]]]]]]]] - (B:0))__[([[aaa (1), 52
C
70
2 K8$) 2K dr, (8/3).
(72)
where is an upper- the absolute value of k.
In order to prove this theorem, first define measure of distance between two rules f1, / E A
as
D&(f1, f2) = ((((()) f2(x), vo(x) - loyh (x))
(73)
45

---

Using this measure of distance, the difference of objectives between two rules fi and fz can be written
(ho))) [[(2(()) =D (2) + k2 (EI - (1((()) (74)
Therefore, if two rules achieve similar constraints, and if (fi, f2) is small enough, we can prove that the two rules achieve similar objectives too, since is bounded above by K.
In fact, if we let fi)) = (2) and fz(z) := fe.P> where is and p are optimal solutions as in Theorem 4.2 then due to this optimality, and because E[S
p. the (+)) S with probability at least 1 - 6 as shown in Theorem 5.T then LHS of (74) is positive with at least the same probability. In this proof, we show that how large is that term, and therefore, we show that how sub-optimal is ft.p in
terms of the objective.
To that end, we first bound the difference between constraints. This bound can be achieved similar to the proof of Theorem 5.I In fact, there we showed that if the empirical con- straint Ess [f the (x))] S 8 - dT)),, then using (69) the true expectation is bounded as Eg (FR 1h I 8 with probability at least 1 --T- T. However, (69) is symmetric in empir- ical and true constraint, i.e., if we show that Es
th (x))] M 8 - (T), then we have Ey [fE.: (x 2 8 -2d, with probability at least π.
To show Es- [(f 11 (x))] 2 8 dn(T). we follow three steps, (i) because ô (Et, fy) innterioo point of the set of constraints, i.e., (6 - é1, 5 + e.,) is a subset of all plausible constraints, then point. Now, using Lemma L.I and by setting (ei - do (T), cu + dd ( we can show that 8 - (T, is e'/2-interior point of the empirical é' e'=min
5 (x)(() is (a - dn (T), En + dz((())-interii
constraints with probability at least - 2e -22 (ii) using the first step and assuming d, dz) S 61/2 we conclude that 8 - dn (I) is dz) 22-inerrrr point of the empirical constraints with the aforementioned probability, (iii) because of Lemma L.2 we conclude that for E = d, (x)/2, and with probability at
least 1 2e- "² there exists &s E I and p E [0, 1] such that Es- [s=[(pp)))) o (z)) 5 (x)
d.(r)/2-e = 8 - 2ddd((n (T). As a result of the above discussion we conclude that with probability at
least 1 2e- n²" there exists i and p such that 5 > [[( (x)) v (x))) 2 8 (T). Now,
since we know that E (z), 2n (x)) E (fr (1)), 2) (x)) 5, then we have
0 > E (fi (z), 2 (x)) E (fe(2)) s (x))} s (d)
(75)
with probability at least 1- 2e
The above discussion together with (74) and the assumption of boundedness of shows that the difference of objectives is bounded with high probability, if we bound Du(fi, However, before we proceed with bounding that term, we should derive a relationship between i and k* for the reasons that we see in proving boundedness of (x(fi,J2)
We have already shown that there exists á E [0, 1] such that 8 2 E [ 1 (x))) 2 8 - 2d, (T).
Here, Lemma L.3 shows that for k' = k K(5)+K61) we have E E o 1 (x)) 2 8 (m) T
T
with probability at least π 2e _02 Moreover, using symmetry in Lemma L.3 and for KK6. we have [[[ (x)) - fa(x), & (z))) < T. Now, since || (x) 4/1 (<)) =o S
k" = + T
5o. using Hölder's inequality we conclude that E [[[irro(>) - (i S T + 26, and
consequently B[J ((x), (z))) < 8 7 T + 25,
Now that have found lower-bound on constraint of the rule (z- for q K9)) then we find an upper bound on the constraint of the rule fü +e (x) for an e E R then we can use monotonicity of the constraint of ft in terms of k and prove a relationship between A and k² To that end, we use detection assumption with which we can show that
+1 (1()))] S 5 -2d, - T, E [ +++ (2d,
46

---

where we assume that (T) v (CA)--I'
Now, using previous discussions conclude that kt ( (2d, (T)4 1 (z)) - B .o- e (1())))
2
E [
with probability at least 1 - π - 2e
This together with the first part of Lemma J.2 shows that k' S k- + (2d, (T) + 7) or equivalently k S k* + T
K(6)+K61) C (2d, (T) + 7)
2e """ Since we know that y is clamped above by 1, and using the inequality (1 + x) S 1 + ar for a 2 we can substitute the above inequality with (2)
with probability at least
k < k" + 2(6++K6))
C (1 a(d, (+))1))) Now optimizing over T leads in T =
T
C(0 kT which concludes that &s S k + A,k with the aforementioned probability, where A,k (z))( "
R())+ if we have d. (CA) 27
+ v
70
2
Similarly, using sensitivity assumption, we have
E [s
+ + (26, (x), th (x)) 2 8 + 26 + T
where (26,+T) A. Next, using previous discussions conclude that
B[( 122 +2/1/ (1), 1 (x)) > [(([rrro(')) t (x))),
with the aforementioned probability. This, again, together with the first part of Lemma J.2 shows that k" 2 k- 5 (26 +77)//7, or equivalently & 2 k- (26 2(6 Kk))) Therefore, by setting
T
T / 220 kτ we conclude that k 2 k- A where A (26
+ 22
2 K6,)
70
(26 + (21++
and assuming
< A.
C
Next, we turn into bounding Da- J2). To that end, we first note that
(kk) == (fk (z)) vz)(z) k* 2/2 (x)) = max (vo(2)) - k2 و/ (1)
(76)
for all p E [0, 1]. This is followed by the definition of f p (-). Similarly, we can show that E (k) = (Fr, (o(x) 1s (x)) = max (No(x)
for all p [0, Now, can rewrite D (f1, f2) as
Dx- (f1, f2) (1( - jk.p (2)), 1h k² wh (x)))
[k') - E {((Fk,p()) 3/0 - k² (())(())
= [b*)] - -B((fE, 50 - (x))
E (I) (Vu(x) - vo(x)) - 1² (w) (z)))
(0)
S [kt) 18 EE (z), do 1 & (x)) + 8 + KK²
[k*)] ((). + (k* L)E[( k.p (z), (1(+)) 80 K8,
k + 50 + K8,, 2 Blt, - (x)) + -
(77)
where (a) and (b) hold due Hölder's inequality.
Next, we show Lipschitzness of t(k) using its structure. In fact, due to its definition, t(k) is the maximum of a set of lines with {t, = (i) - *(
(i) in terms of k with
slope my = - (w) (x:)) (i) and y-intercept of 4; (vn())) (f). Therefore, such piecewise-linear function has a Lipschitz factor equal to the maximum slope of the lines, which in here is equal to
max; m, max; (z)()) (i) 1. Therefore, t(k) is a 1-Lipschitz function. Therefore, using
we can bound DE- (/1, f2) as
Da- (J1, f2) < [L, (k) i, (f)] 2/k* - kl + do + Ko,
m|max (vo(z) ke (x)) max (vo(z) - Ke (1) 2/k* k 21+00 80 K8,
2 k + 2(80 + K81),
47

---

where (a) holds because each component of (v)(2) ke)(()) and (Do(x) k (x)) is bounded
by 6g K and because the maximum operator norm, and therefore satisfies sub-ad uub-additivity.
Finally, since we have bounded A < k' we have
A with probability at least 1 π 2e ne" //4 then -
f2) S 2 max A 2(6 + K
(2 max fdn (1), 1/7
2(00 + Kō1)
4
+ 2(00 + K81),
C
7C
with such probability. This, together with
74 and
75
shows that
max (maxx(n (1), 1/7
2( + Kδi)
(ff(())) - ([)f(())
<2
+1
C
7C
+ 2(00 + K81) + (Kd
which completes the proof.
M Proof of Theorem
To prove this theorem, we first prove the following auxiliary lemma Lemma M.1. For a, 2 0, the following holds
Σ rid 220
Σ r:d Se. max dd]
min Is
min
/E[1m]
Proof of lemma. We know that for every positive vector with Ei= P3 S a a e, we could rewrite that sum of two vectors r r' r" for which
Σ Ensa,
and
p S
f=1
As result, we can rewrite min,,20 Saat Ei= T;d as
min r2 220 Sarte
rid, 2
min
1SSr""2 P (r/++ di
min
min
rdd +
min
dd...
20, It M/sa
r. 2"20,200
Di
Sl mm1
Hence, we have that
min Satt
rid,
min 120 Moa
r/ 2
min
~20
200 Eis
rr i=1
(a)
max
[d 2 -
max [de]; =E(1:n]
where (a) holds using Hölder's inequality.
Next, we know that the optimal deterministic deferral policy should satisfy
min 2
Σ
(x U.. m.) + (1 r(xx)) (ar(m))))
Σ (Ar(T.)))++ ((..)(0.1), EL. (z))
min 1
Σ
r(x;) (En (1, - ear v:)
(a) Σ (ar( +
min ((x))e(0.1) Eis ((a))((nn n
1
r(x))) (axs) Wr mi) ear(sr,
8
48

---

where (a) holds because r(z;)) E {0, }} and therefore Er(zs) I bn if and only if r((ss) I [bn]. Now, we turn to examining B. To that end, we first consider the following optimization problem:
min r(..)E (a.)s(bn bn
E t=1
((ss)((n(s) Us m.) (ar(s;,
(78)
For minimizer I' of the above problem, we could form i as
8 = r. (1:) lu (x Us, ma) las (3 U1) - 0
Ef (Zi, Do, m,) Las (Zi, V/) > 0
One can see that f(x) also a minimizer the above problem. Hence, without loss of generality, we
assume that there is an optimal deferral policy that has only non-zero value when (x, y, m) A
{(x, y, m) E DD :}. Furthermore, we know that since f(z;) < 1, then > f(xx) S min [nb] [Al
We argue that this inequality does not hold in strict form, i.e., have 2 (xx)) min [mb]] [
The reason is that otherwise one can find r'(x) E [0, 1] such that E(s (.....m fzz) + (x;) = (nb, |A[} and because of negativity of frr m.) - L Ar Mi), we can strictly reduce the objective function that is contradiction.
Next, we order f (Zi, Dt, m,) LAt (#i, y:) increasingly and we name them dj. In fact, we define k such that dj- E (Kkys Dky, ma,) EAT (#ky; Mke,) and that dj - d2... .. I di S For the sake of simplicity. we further define r, == r(rk,)) ). As result, the optimization problem (78 can be rewritten as
min n. Ei min [LbbjiAl
r.dy
1=1
Here, we show that the optimizer of the above problem is r; = g ([mb).1A[)) To show that, we consider r, E [0, 1] such that Ei= = min [[nb),,]|]]} Then, we have
Σ
Σ
(1, [igiin[( ([ni([[nbb]111 - -rr)
1=1
s: 1 minn [nd) | -r/<0
+
Σ
(Iismin([nn)]AA) r1)) dz. (79)
8: E:iimmii ([nb).IA)) -r/>0
Now, since we know that E3 1 Lggmnn [bb11A|] = Ee r/ we can define parameter Q as
Σ
1 Ligmin (Lmbin( -
Σ
of Lig [igmin(.nb].AApp
1: 1:1ismiu (Int(( -
è: ((ne.((() -1
(80)
Next, by defining Ps := Ledmin((ud/lA))- for is in which Ligmin([ab),IAl - and q: := and otherwise, we conclude that (p:):
(AAssuin(ind).a for in which [ismin( Al) - r/
Q
and } hi are probability mass functions. Hence, using (79) and (80). we have minf(Indl.ll Σ P:d,
n
n
Σ
[egmio([n6]JJA)) d Σ rid, - Q(
gedz).
i=min [1bb] .AAH+1
The above identity contains the difference of two expected value over random variables that one is always smaller than the other. As a result, we show that
simin [1bb) Σ dd. S 0.
which completes the proof.
49

---

Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: Yes
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: Yes
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: Yes
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: Yes
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: Yes
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: Yes
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
Yes
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Answer: Yes
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp///harrrss.cooooo////ltlts
Answer: NA
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: NA
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
50

---

Answer: NA
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: Yes
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: Yes
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: NA
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country or institution) were obtained?
Answer: NA
51


Reviews:
[{"review_id": "P16Pqnha8q", "reviewer": "Reviewer_xkzY", "summary": "This paper aims to provide a provably consistent unified post-processing framework of learning to defer with constraints. The problem of constrained L2D is first reduced to a linear programming problem. Then the linear programming problem is further tackled with a generalized version of Neymar-Pearson lemma, which lead to an efficient solver of this problem. Non-asymptotic analysis is conducted to further provide guarantee for the empirical version of the algorithm. Experimental results validate the efficiency of the proposed solver.", "questions": "1. It is mentioned that solving (2) is NP-hard. While the proof is quite clear, I wonder if such hardness is important. In my opinion, a common practice that can avoid directly solving this problem is using a surrogate loss instead of 0-1 loss and integrating the expert coverage constraint into the loss like that in the Selective-net. Can you further make some discussions on this point?\n\n2. If we have rather accurate class probability estimates and expert accuracy, why not use it as the solver of this problem?", "limitations": "Please see the weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. A unified post-processing framework for constrained L2D is proposed in this paper, which allows training a randomized classifier-rejector tuple with small number of validation data combined with a trained model’s confidence output.\n\n2. The hardness of directly solving the original problems and in-processing methods are thoroughly analyzed in this paper, which provides enough rationale for the proposed method.\n\n3. The introduction of the generalized Neyman-Pearson lemma is novel to the field of L2D, which can provide insights for the future works of this field.", "weaknesses": "1. The related works are moved to the appendices, which can be confusing to readers that are new to this field. I suggest the authors use a more compact type setting in the contribution part of Section 1 and reduce/integrate some of the contributions to make more spaces. The paragraph ‘Type of Constraints’ can also be reduced given the Table 1.\n\n2. The notations in this paper need further proofread, e.g., the realization and random variables are used improperly in line 141, line 188; the quantity $a^{i}$ in the algorithm 1 seems to be unused in this algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first thank the reviewer for their positive feedback to our submission. Here, we respond to their questions\n\n1. **Q: It is mentioned that solving (2) is NP-hard. While the proof is quite clear, I wonder if such hardness is important. In my opinion, a common practice that can avoid directly solving this problem is using a surrogate loss instead of 0-1 loss and integrating the expert coverage constraint into the loss like that in the Selective-net. Can you further make some discussions on this point?** A: The point of the hardness theorem is to justify the use of randomness in multi-objective setting. We should note that the practical solutions to this problem  such as Selective-Net that use surrogates of the loss functions do not enjoy the guarantees for optimality. This is as opposed to the unconstrained case, in which there are continuous surrogate functions that are Fisher consistent, and therefore their minimization is equivalent to the $0-1$ loss minimization.\n\n2. **Q: If we have rather accurate class probability estimates and expert accuracy, why not use it as the solver of this problem?** A: The class probabilities as well the expert accuracy can help us find the optimal solution when we allow for randomness and using $d$-GNP. If, however, we aim to find the optimal deterministic solution that is not the case. In Appendix E we introduce an example that the human has perfect information of the label, while the input feature has no information about the label. In this case, it would be more efficient to defer the decision to the human. However, if we bound the budget of the human to $b$ proportion of samples, the optimal deterministic solution would be to defer on inputs that are arised with sum probability of $b$ and not to defer in the other $1-b$ proportion. Therefore, on the inputs with the same conditional accuracy and the same conditional expert accuracy, we have a different decision. This is the reason to the hardness theorem, i.e., finding that set of inputs that sum up to $b$ can be a complex task.\n\n3. **Q: The related works are moved to the appendices, which can be confusing to readers that are new to this field. I suggest the authors use a more compact type setting in the contribution part of Section 1 and reduce/integrate some of the contributions to make more spaces. The paragraph ‘Type of Constraints’ can also be reduced given the Table 1.** A: This was a decision due to the lack of space. We will make make more space for the related works in the next version of the manuscript, as suggested by the reviewer.\n\n4. **Q: The notations in this paper need further proofread, e.g., the realization and random variables are used improperly in line 141, line 188; the quantity $a_i$ in the algorithm 1 seems to be unused in this algorithm.** As mentioned in our main rebuttal, we have made an extensive effort to proofread the paper. We have addressed the typos mentioned by the reviewer and appreciate their thorough reading of the manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "289FKYMTyI", "reviewer": "Reviewer_7rh1", "summary": "The paper introduces a unifying post-processing framework for multi-objective learn-to-defer problems, allowing the system to defer tasks to an expert under specified constraints. By generalizing the Neyman-Pearson lemma, the paper derives the Bayes optimal solution for this framework and develops an algorithm to estimate it. The proposed algorithm is evaluated using the COMPAS and ACSIncome datasets.", "questions": "1. The multi-class Neyman-Pearson (NP) paradigm has been studied in [66]. Could the authors summarize the key differences between the framework proposed in this paper and the prior work?\n\n2. What is the motivation for imposing specific constraints in learning to defer? Could this compromise the accuracy of the process?\n\n3. How does the proposed algorithm empirically compare with the baselines on the ACSIncome datasets? Do you think the experiments could be expanded further?\n\n4. It seems that the method could potentially be applicable to other constrained objectives beyond the L2D setting. Could the authors further elaborate on this?\n\n5. Could the authors further comment on the challenges of extending the analysis and algorithm to multiple constraint cases?\n\n6. How are the tolerances chosen during the experiments? Can the assumptions in Theorem 5.3 be verified in practice?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a general post-processing framework.\n2. The paper is well-written and has excellent illustrations, for example, Figure 1.\n3. The framework accounts for multiple objectives in L2D.\n4. The method can potentially be extended beyond the L2D setting to apply to other constrained objectives.", "weaknesses": "1. The proposed algorithm requires the estimation of scores and $\\hat \\psi$ (Lines 4 and 5 of Algorithm 1). However, accurately estimating these values can be potentially challenging.\n2. The experiments could potentially be expanded further.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and constructive comments on this paper. In the following, we respond their questions in order\n\n**Q1** A: This work that we have further referenced in our manuscript, as we mentioned after (6), has three main differences with our work. *(i)* This work only considers the Type-$k$ error and is designed to find the solution of the optimal classifier given that specific constraints. In contrary, our work can contain all types of constraints that are in form of loss function (e.g., fairness criteria, human intervention budget, long-tail classification). *(ii)* This work is based on strong duality theorem that as we discussed in Appendix E is not considered in our work, due to its limitations (see the counterexample of Appendix E). *(iii)* In our work, we not only find the optimal solution to the constrained optimization problem (3), but also show that all solutions to this problem are of the form that we have formulated in (8).  \n\n**Q2** A: The L2D systems can be used in many applications, including applications that are sensitive in nature. As an instance, we can design an algorithm that either classifies a disease based on the data of a patient, or defer the decision to the doctor. This system in total can be unfair, meaning that the error that is induced by this system not detecting the disease for different demographic groups can be different. As another example, as we further explained our experiment for Reviwer 4QNG, this can be the case when we want to detect Hatespeech from a tweet automatically or using our agents. This decision could entail different errors for the tweets that are written with an African-American dialect and the ones that are not. Our results helps controlling this algorithmic unfairness. Since we add a constraint to our optimization problem, the corresponding search space reduces, and therefore the accuracy can be compromised, which is the case in many algorithmically fair methods.\n\n**Q3** A:  Our experimental setting now have expanded and include content moderation experiments on Hate Speech Dataset. We refer the reviewer to the rebuttal section of Reviewer 4QNG for the details of these experiments. Note that there is no known basline to ensure a certain equalized odds constraint for an L2D system. Particularly in our setting in which the model is a random forest. However, in the next revision, we will compare our method with best fair classifier and an adapted version of Mozannar et al. 2020 for random forests in which we shift thresholds for different demographic group.\n\n**Q4** A very interesting application of $d$-GNP is its use in fair vanilla multi-class classification. This theorem can show that for controlling demographic parity or equality of opportunity, we need to first learn the scores, and then add or multiply a value to these scores based on the demographic identity.\n In fact, or an $L$-class classifier, if we aim to set constraints on demographic parity  $\\big|\\Pr(\\hat{Y}=0|A=0)-\\Pr(\\hat{Y}=0|A=1)\\big|\\leq \\delta$ or equality of opportunity $\\big|\\Pr(\\hat{Y}=0|Y=0, A=0)-\\Pr(\\hat{Y}=0|Y=0, A=1)\\big|\\leq \\delta$ on Class $0$, then we can follow similar steps as in Appendix D to find the embedding functions as\n    $$\n    \\psi_{\\mathrm{DP}} = s(A)\\big[1, 0, \\ldots, 0\\big],\n    $$\n    and\n    $$\n    \\psi_{\\mathrm{EO}} = t(A, 0)\\big[\\Pr(Y=0|x), 0, \\ldots, 0\\big].\n    $$\n    As a result, since the accuracy embedding function is $\\psi_0(x)=\\big[\\Pr(Y=0|x), \\ldots, \\Pr(Y=L|x)\\big]$, then, by neglecting the effect of randomness, the optimal classifier under such constraints are as\n    $$\n    h_{\\mathrm{DP}}(x)=\\arg\\max\\big\\(\\Pr(Y=0|x)-ks(A), \\Pr(Y=1|x), \\ldots, \\Pr(Y=L|x)\\big\\),\n    $$\n    and\n    $$\n    h_{\\mathrm{EO}}(x)=\\arg\\max\\big\\(\\Pr(Y=0|x)\\big(1-kt(A, 0)\\big), \\Pr(Y=1|x), \\ldots, \\Pr(Y=L|x)\\big\\).\n    $$\n    Equivalently, for demographic parity, the optimal classifier includes a shift on the score of Class $0$ as a function of demographic group, and for equality of opportunity, the optimal classifier includes a multiplication of the score of Class $0$ with a value that is a function of demographic group. It is easy to show that under condition of positivity of the multiplied value, these classifiers both reduce to thresholding rules in binary setting.\n\n**Q5** A: We refer the reviewer to the main rebuttal for the response to this question.\n\n**Q6** A: The tolerances are chosen in a manner that capture the dynamics of the accuracy within that range. If we permit for a very large tolerance, the accuracy saturates to its Bayes optimal value. This is what occurs at the right part of ACSIncome figure. \nThe main assumption of Theorem 5.3 is the sensitivity assumption of Definition 5.2. To test that assumption, we can set $\\gamma=1$, and reduce this assumption to a lower-bound on the derivative of the constraint w.r.t the coefficient $k$. We have plotted this in Fig. (f) and (g) of the submitted PDF and we observe that for the cases that $k$ induce a constraint within the plausible constraints, this derivative is lower-bounded. In fact, Fig. (f) shows the accuracy of the estimator for two coefficients of corresponding constraints of demographic disparities of detecting a tweet Offensive (DP-O) or Hate-Speech (DP-HS). We observe that as long as there is dynamics in the accuracy in terms of this coefficients, then the derivative of the constraints in terms of this coefficient is bounded below. This is particularly observable in right-most part of Fig. (g) for DP-O and the left-most part for DP-HS.\n\n**Q7** We should mention that estimating the value of the scores are equivalent to estimating the value of a set of posterior probabilities that are used in obtaining these scores. This is a task for which machine learning literature has developed corresponding tools such as deep neural networks, random forests, etc. Therefore, we don't believe the estimation of our scores is of particular hardness compared to this literature.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "IwTWpvDj0B", "reviewer": "Reviewer_Zrm7", "summary": "The paper studies multi-objective learn-to-defer problems, where the objectives include minimizing deferral loss and satisfying several constraints. It demonstrates that these problems are generally NP-hard and can be reduced to functional linear programming. Additionally, it shows that the problem can be further reduced to a d-dimensional generalized Neyman-Pearson problem and characterizes its solution when there is only one constraint. The paper also presents a unifying post-processing algorithm with generalization bounds and provides numerical validations.", "questions": "1.Why in Theorem 4.2, $f^*_{k,p}(x)=\\tau(\\psi_1(x)-k\\psi_0(x))$, while in Algorithm 1, its estimation version is $\\hat{f}_{k,p}(x)=\\tau(\\hat{\\psi}_0(x)-k\\hat{\\psi}_1(x))$ (where the positions are swapped)?\n\n\n2.Can Algorithm 1 handle multiple constraints settings? Figure 1 depicts a diagram of multiple constraints settings, but it seems Algorithm 1 is designed for single constraint settings.", "limitations": "See weaknesses.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The paper offers several theoretical insights into multi-objective learn-to-defer problems, enhancing the understanding of these problems. It also introduces a unifying post-processing algorithm with provable performance guarantees.", "weaknesses": "1.Inconsistent Notations and Typos: The paper is difficult to follow due to inconsistent notations and potential typos. For instance, $m$ can mean the expert decision (line 111) or the number of constraints (Equation 3). $r$ can mean the rejection function (line 110) or a distribution vector (Theorem 4.1).  In line 7 of Algorithm 1, should it be $\\hat{C}(k)$ instead of $\\hat{C}(t)$? And line 208 only defines  $\\psi_{i}$ for $i=1,...,m+1$, then in line 209, what is $\\psi_{0}$?\n\n2.Limitations on Multiple Constraints: The paper acknowledges that the provided analyses for the algorithm (and possibly the algorithm itself) only apply to single constraint settings. More discussion on the challenges of extending these analyses (and potentially the algorithm) to multiple constraints settings would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for reading the paper and their comments. We are respectively address the concerns of the reviewer. \n\n1. **1.Why in Theorem 4.2, $f_{k, p}*(x)=\\tau(\\psi_1(x)-k\\psi_0(x))$, while in Algorithm 1, its estimation version is $\\hat{f}_{k,p}(x)=\\tau(\\hat{\\psi}_0(x)-k\\hat{\\psi}_1(x))$ (where the positions are swapped)?** This is a typo that we addressed in the newer version of this manuscript. In this version $\\psi_0$ corresponds to the objective, while $\\psi_1, \\ldots, \\psi_{m+1}$ correspond to the constraints.\n\n2. **Can Algorithm 1 handle multiple constraints settings? Figure 1 depicts a diagram of multiple constraints settings, but it seems Algorithm 1 is designed for single constraint settings.** This algorithm, as mentioned in the main rebuttal can handle many constraints, just by adding the line of finding the empirical solution of $k_1, \\ldots, k_m$ for (3) and based on validation dataset.\n\n3. **Inconsistent Notations and Typos**: We have extensively proofread and resolved the typos that are raised by the reviewer. We refer the reviewer to the main rebuttal section for further details.\n\n4. **Limitations on Multiple Constraints: The paper acknowledges that the provided analyses for the algorithm (and possibly the algorithm itself) only apply to single constraint settings. More discussion on the challenges of extending these analyses (and potentially the algorithm) to multiple constraints settings would be helpful.** As we further explained in the main rebuttal section, the algorithm can handle many constraints. The main result of this paper also hold for many constraints. Further extensions of the sample complexities are obtained in the main rebuttal section.\n\nHere, we would be grateful if the respected reviewer would let us know why they think our paper is not fit to this conference, since we believe there is a disparity between the comments and the scores of the reviewer. The typos and notation issues can be minor issues that will not entail any major concerns in our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "fTozKKFjv7", "reviewer": "Reviewer_4QNG", "summary": "While there has been extensive research on L2D, general methods for designing such systems under various constraints (e.g., algorithmic fairness, expert intervention budget, defer of anomaly, etc.) remain largely unexplored. This paper utilizes $d$-dimensional generalization to the fundamental lemma of Neyman and Pearson ($d$-GNP) to obtain Bayes optimal solutions for L2D under various constraint conditions and designs a generic algorithm to estimate these solutions.", "questions": "1. Post-Processing Framework has many benefits, but it also faces challenges in confidence calibration, which is particularly evident in deep models. Inevitable overfitting makes the model's output probabilities unreliable, indirectly leading to biases in approaching the Bayes optimal solution through post-processing methods. Does the method proposed in this paper include mechanisms to mitigate these issues?\n2. There are many studies similar to L2D, such as the dynamic classifier selection literature (DCS). What is the main difference between L2D and DCS?\n\nCruz R M O, Sabourin R, Cavalcanti G D C. Dynamic classifier selection: Recent advances and perspectives[J]. Information Fusion, 2018, 41: 195-216.", "limitations": "N/A.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper proposes a novel general framework for addressing L2D under various constraint conditions.\n2. Different constraint conditions can be simultaneously addressed.\n3. The proposed method is a post-processing approach that can be easily extended to existing models.", "weaknesses": "1. The general framework provided by the author can address various constraint problems, but it does not seem to be reflected in the experimental section (especially in cases involving multiple constraints), only considering simple single-constraint situations and basic comparisons.\n\nExpert Intervention Budget: \n\nLiu S, Cao Y, Zhang Q, et al. Mitigating Underfitting in Learning to Defer with Consistent Losses. ICML, 2024.\n\nNarasimhan H, Jitkrittum W, Menon A K, et al. Post-hoc estimators for learning to defer to an exper. NeurIPS, 2022.\n\nLong-Tail Classification:\n\nNarasimhan H, Menon A K, Jitkrittum W, et al. Learning to Reject Meets Long-tail Learning. ICLR, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedbacks. We further address their questions in the following.\n## Questions\n\n **Q1** Dealing with overfitting is largely studied in the machine learning literature. In this work, we assume that the scores are estimated using the well-studied methods such as calibrated neural networks and random forests. This is an assumption that a large body of the field, from the first works of L2D (e.g., Mozannar et al. 2020) holds. If the posterior probabilities are not accurate, as the reviewer has mentioned, all the plug-in methods (including Mozannar et al., Verma et al., and Cao et al. for unconstrained L2D problem) would lead to incorrect solutions. Therefore, we believe the study of this issue is beyond the scope of this paper and is of its own interest.\nHowever, we should add that, as the reviewer has mentioned, the calibration of such probabilities would equip us with an interesting set of properties. In fact, if we know that the neural network $g(x)$ is calibrated, i.e., $P(Y=1|g(X)=p)=p$, then if the only information in our hand is that calibrated estimation, then the plug-in methods are reduced to the plug-in methods for $g(x)$, since in this case $\\Pr(Y=1|g(x))=g(x)$, and therefore rules such as $\\Pr(Y=1|g(x))\\geq T$ is equivalent to $g(x)\\geq T$. \n\n**Q2** These two fields are highly interrelated in the sense that in both of these fields, a competent decision-maker is selected for a particular input feature. However, the difference between these fields is that in L2D systems, due to the some reasons such as transparency and responsibility, the decision is made either by human or the classifier, while in DCS systems the solutions of the classifier can be fused with each other. Such extensions to L2D problems are also studied in the literature, e.g., Charusaie et al. 2024, and Steyvers et al. 2022. We make sure to include these references as well as DCS references in our manuscript.\n\nCharusaie, Mohammad-Amin, Amirmehdi Jafari Fesharaki, and Samira Samadi. \"Defer-and-Fusion: Optimal Predictors that Incorporate Human Decisions.\"\t\n\nSteyvers, Mark, et al. \"Bayesian modeling of human–AI complementarity.\" Proceedings of the National Academy of Sciences 119.11 (2022): e2111547119.\n\n\n## Weaknesses \n\n\n**The general framework provided by the author can address various constraint problems, but it does not seem to be reflected in the experimental section (especially in cases involving multiple constraints), only considering simple single-constraint situations and basic comparisons.** We first should note that, as we mention in the main rebuttal section, the ACSIncome experiment controlls two constraints, namely, the disparity of true negative and false negative predictions for two demographic groups. In the following, we further introduce a new set of multi-constraint experiments in the Hate Speech experiment.\n\n\nWe believe that the comments of the reviewer is remained unfinished, or otherwise we are not sure how the references on **Expert Intervention Budget** and **Long-Tail Classification** are related to their comments. We have indeed cited these references in the current version of the manuscript.  \n\n## New Experiment on Hatespeech Dataset\n\nWe further experimented our algorithm on Hatespeech dataset (Davidson et al. 2017) that is a content-moderation task to flag hateful and offensive tweets. The results are plotted in the submitted PDF. We used a pre-trained model (Blodgett et al. 2016) to detect whether a tweet is written in an African-American (AA) or not (NAA). We then used our algorithm to control the (i) parity of predicting a tweet hateful, or (ii) offensive, and (iii) false negative probability difference for group AA and NAA. We can observe in Figure (d) that the disparity in predicting a tweet \"Offensive\" for our algorithm (violet bars) is reduced to the tolerance $0.1$ by deferral to the human for group AA (see Figure (b)), and otherwise randomization of the results for group NAA (Figure (c)). Similarly, the disparity in predicting \"Hate Speech\" is diminishing in our algorithm (brown bars of Fig. 2,3, and 4). Furthermore, we can reduce the disparity of false negative prediction (finding a tweet Hate Speech or Offensive, given it is neither) in Figure (e). Here we note that the high variance in Fig. (e) is due to small size of non-offensive tweets. We furtherran experiments on **multi-constraint** setting in which both demographic disparity and human intervention budget is controlled. The accuracy and the true constraints are plotted in Fig. (h), (i), and (j). Similarly, Type-II error and human budget is controlled together and plotted in Fig. (k), (l), and (m).\n\nDavidson, Thomas, et al. \"Automated hate speech detection and the problem of offensive language.\" Proceedings of the international AAAI conference on web and social media. Vol. 11. No. 1. 2017.\n\n\nBlodgett, Su Lin, Lisa Green, and Brendan O'Connor. \"Demographic dialectal variation in social media: A case study of African-American English.\" arXiv preprint arXiv:1608.08868 (2016).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We first thank all reviewers for the time they have put in writing this set of constructive reviews. In particular, we are glad that the reviewers found our method "well-written", "thoroughly analyzed", "novel to the field of L2D", "enhancing the understanding of these problems", "can be extended beyond the L2D setting", and with results that "validate the efficiency of the proposed solver". In the following, we first reiterate the main results of our paper. Next, we address main issues raised by the reviewers.

## Main Results
* We find a generalization of Neyman-Pearson lemma (Thm. 4.1) using which we can solve a variety of constrained learning problems, including multi-objective L2D problems.
* We formulate the multi-objective L2D problem when the constraints are corresponded to expert intervention budget, OOD detection, long-tail classification, type-$k$ error, demographic parity, equality of opportunity, and equalized odds in terms of this generalization of N-P lemma.
* We find the parameters of this solution in closed-form (Thm. 4.2)
* We closely analyze the sample complexity of the prediction of this solution from empirical data (Thm. 5.1 and 5.3) 
* We find the hardness of constrained L2D problems in lack of randomness (Thm. 3.1)
* We have an impossibility result of in-processing methods (Prop F.2)
* We have experiments on controlling demographic parity and equalized odds for ACS and COMPAS datasets. (in the rebuttal, we introduce a new set of experiments of Hatespeech dataset and for multi-constraint setting)

### Typos and Proofreading 
We have put an extensive time in proofreading the manuscript and we have further considered all the typos that are raised by the esteemed reviewers. In the new version of manuscript, $\psi_0$ corresponds to the objective, and $\psi_1, \ldots, \psi_{m+1}$ corresponds to the constraints, $f$ is the vector prediction function, $L$ is the number of classes, and $n$ is the size of validation dataset. Moreover, the capital letters are reserved for random variables, and the small letters are reserved for the scalar values. Furthermore, Algorithm 1 is modified notation-wise, and to support multiple constraints. 

### Multiple-Constraint (MC) Setting 
1. We first note that the main result of this paper, **Theorem 4.1**, which formulated the **Bayes optimal** solution of the constrained optimization problem (3) is designed to handle **multiple constraints simultaneously**.

2. Theorem 4.2 is merely written to simplify the search for coefficient $k$ into finding the root of a monotone function. Although in MC setting, each constraint is still monotone in terms of each coefficient $k_i$ (constraints are marginally monotone), this does not reduce the complexity, since there might be more than one solution of $k_1, \ldots, k_m$ to achieve $\delta_1, \ldots, \delta_m$. Instead, we should use search methods to find the correct coefficients for our dataset.

3. In the **experiment** section, the ACS dataset is tested for equalized odds constraints, which keeps the differences between the true positive rate of two demographic groups as well as the true negative rate of the two groups controlled. **This experiment is a multi-constraint optimization** with the results reflected in the right-most subfigure in Figure 2 of the manuscript. Further experiments are introduced in Reviewer 4QNG rebuttal.

 4. **The algorithm can support the MC setting**, by just adding one line in which we search to find the values of $k_1, \ldots, k_m$ that are empirical solutions to  (3) for the validation dataset.

 5. The **sample complexity analysis for the constraints in Theorem 5.1** are **easily generalizable** to MC setting. If we have $m$ constraints with the empirical value of them being bounded by $\delta_1, \ldots, \delta_m$, then by $m$ times using Theorem 5.1 and using union bound on probabilities, we can show that the true constraint values are bounded by $\delta_1+d_n(\epsilon/m), \ldots, \delta_m+d_n(\epsilon/m)$, respectively with probability $1-\sum_{i=1}^m \epsilon/m = 1-\epsilon$. 

 6. The MC extension of **sample complexity analysis for the objective of Theorem 5.3** although not readily but **is achievable by modification of the proof** and the assumption that **true scores are available**, and the optimization is done on the empirical dataset. In the proof of this theorem, in (77), we have offered a decomposition of the objective generalization Lagrangian generalization $D_{k}(f_1, f_2)$ and constraint generalization. We can define a similar Lagrangian generalization $D_{k_1, \ldots, k_m}(f_1, f_2)$. Then, following the same steps as in (80), and the equation after, and using Lipschitzness of $t_x(k)$, we can show that this value is bounded above by $2\sum_{i=1}^m |k_i^*-\hat k_i|$ . Furthermore, in case that each constraint achieves $\delta_i$, we can simply repeat the discussion above (78) and show that the constraints generalize. Therefore, it is remained to show that $k_i^*$ and $\hat k_i$ are closed to each other.  This entails that Definition 5.2 must hold for all $m$ constraints, i.e., the condition is $\big|\mathbb{E}\big[\langle f_{k}(x)-f_{k'}(x), \psi_{i}(x)\rangle\big]\big|\geq C\delta^{\gamma}$ where $||k-k'||\geq \delta$.  Next, due to the generalization of the constraints, we have $\mathbb{E}[\langle f_{\hat{k}}(x), \psi_i(x)\rangle]\in [\delta_i-d_n(\epsilon), \delta_i+d_n(\epsilon)]$ with probability at least $1-\epsilon$. Therefore, we can conclude that $d_n(\epsilon)\geq C\delta^{\gamma}$, or equivalently, $D_{\hat{k}_1, \ldots, \hat{k}_m}(f_1, f_2)$ is bounded above by $2m(d_n(\epsilon)/C)^{1/\gamma}$. This completes the proof. 
 In multi-constraint setting and if we don't have the correct scores, we should use other proof techniques. The reason is that our proof is based on closeness of $\hat{k}$ and $k^*$ and in this case, we cannot assure their closeness with each other, although the objectives might still be close to each other.

Meta-review: The submitted paper was reviewed by four reviewers, three of whom recommend its acceptance while one recommends its (borderline) rejection. A (partly intensive) exchange between authors and reviewers took place in the discussion phase. Overall, the reviewers appreciate the papers' proposed post-processing framework and the theoretical contributions. Concerns around notation, discussion of limitations, requirements for the proposed framework ([calibrated] estimation of the scores/probabilities), and parts of the experimental evaluation (multiple constraints, comparison with related works, ...) have been raised. The authors responded well to these concerns and were able to refute most of them - mainly a few concerns regarding the experimental evaluation remain. The paper is quite extensive and already covers a lot of interesting experimental results and even more came up during the discussion phase. Thus I am recommending the acceptance of the paper but strongly encourage the authors to incorporate the reviewers' comments carefully (in particular also discussing limitations in comparison to related works but also including the newly presented experimental results) when preparing the camera-ready version of their paper.
Decision: Accept (poster)