A Unifying Post-Processing Framework for Multi-Objective Learn-to-Defer Problems

Authors: mohammad-amin  charusaie
samira  samadi
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:34:35

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.

Main paper: 
 introduction: 
 Machine learning algorithms are increasingly used in 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 a supportive role by taking over the tasks on which machine learning is uncertain [39, 60, 4] . The abstention of the classifier in making decisions, and letting the human expert do so, is where the paradigm of learn-to-defer (L2D) started to exist.The development of L2D 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 or 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, we face a 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] , a general solution to such class of problems, besides specific examples [26, 57, 51, 52] , has remained unknown to date. Multi-objective machine learning extends beyond the realm of L2D problems. A prime example that is extensively studied in various settings is ensuring algorithmic fairness [18] while optimizing accuracy. Recent advances in the algorithmic fairness literature have suggested the superiority of post-processing methodology for tackling this multi-objective problem [73, 14, 20, 76] . Post-processing algorithms operate in two steps: first, they find a calibrated estimation of a set of probability scores for each input via learning algorithms, and then they obtain the optimal predictor as a function of these scores. Similarly, in a recent set of works, optimal algorithms to reject the decision-making under a variety of secondary objectives are determined via post-processing algorithms [51, 52] , 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.Inspired by the above works, in this paper, we fully characterize the solution to multi-objective L2D problems using a post-processing framework. In particular, we consider a deferral system together with a set of conditional performance measures {Ψ 0 , . . . , Ψ m } that are functions of the system outcome Ŷ , the target label Y , and the input X. The goal is to optimize the average value of Ψ 0 over data distribution while keeping the average value of the rest of performance measures Ψ 1 , . . . , Ψ m for all inputs under control. As an example, in binary classification, Ψ 0 can be the 0 -1 deferral loss function, while Ψ 1 can be the difference between positive prediction rates of Ŷ 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 is bounded by a tolerance value δ 1 ∈ [0, 1].To provide the optimal solution, we 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 is that firstly, objectives such as algorithmic fairness are not compositional, i.e., even if the classifier and the human are fair, due to the emergence of Yule's effect [62] the obtained deferral system is 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 in which achieving a 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 L2D solution boils down to a generalization of the fundamental Neyman-Pearson lemma [55] . This lemma is initially introduced in studying hypothesis testing problems and characterizes the most powerful test (i.e., the test with the highest true positive rate) while keeping the significance level (true negative rate) under control. As a natural extension to this paradigm, we consider a multi-hypothesis 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 Neyman-Pearson lemma to this setting provides us with a solution for our multi-objective L2D problem.In summary, the contribution of this paper is as below:• In 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 Neyman-Pearson (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 5, we show that a post-processing algorithm that is based on d-GNP solution generalizes in constraints and objective with the rate O( log n/n, log(1/ϵ)/n, ϵ ′ ) and O((log n/n)1/2γ , (log(1/ϵ)/n) 1/2γ , ϵ ′ ), respectively, with probability at least 1 -ϵ where n is the size of the set using which we fine-tune the algorithm, ϵ ′ measures the accuracy of learned post-processing scores, and γ is a parameter that measures the sensitivity of the constraint to the change of the predictor. Then, • we show that the use of 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 a 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 L2D 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 to future works. 
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 ML [37, 68] . This overperformance is due to the ability to 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, 50, 12, 51, 9, 43, 48, 45] . The multiobjective classification with abstention problems is studied for specific objectives in [44, 57, 48] via in-processing methods. The application of 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. 
problem setting: 
 Assume that we are given input features x i ∈ X , corresponding labels y i ∈ Y = {1, . . . , L}, and the human expert decision m i for such input, and assume that these are i.i.d. realizations of random variables X, Y, M ∼ µ = µ XY M . Since there exists randomness in the human decision-making process, for the sake of generality, we treat M as a random variable similar to Y and do not assume that m i = m(x i ) for some function m. Further, assume that for the true label y and a certain feature vector x, the cost of incorrect predictions is measured by a loss function ℓ AI (y, h(x)) for the classifier prediction h(x), and a loss function ℓ H (y, m) for human'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 decision to the human when there are constraints that limit the decision-making? The constraints above can be algorithmic fairness constraints (e.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) ∈ {0, 1} be the rejection function 1 , i.e., when r(x) = 0 the classifier makes the decision for input x and otherwise x is deferred to the expert. We obtain the deferral loss on x and given a label y and the expert decision m as ℓ def (y, m, h(x), r(x)) = r(x)ℓ H (y, m) + (1 -r(x))ℓ AI (y, h(x)).Table 1 : A list of embedding functions corresponding to the constraints that are discussed in Section 3. This list is a 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 t(A, y) := Expert Intervention Budget [57] [0, . . . , 0, 1]OOD Detection [53] [0, . . . , 0,f out X (x) f in X (x) ] - K i=1 Pr(Y ̸ =1,Y ∈Gi|X=x)αi Pr(Y ∈Gi), . . . ,Pr(Y ̸ =l,Y ∈Gi|X=x) αi Pr(Y ∈Gi), 0Long-Tail Classification [52] andPr(Y ∈Gi|X=x) Pr(Y ∈Gi)1, . . . , 1, 0 -αi K Bound on Type-K Error [69] Pr(Y =k|x)Pr(Y =k) [1, . . . , 0 k-th , . . . , 1, Pr(M ̸ = k | Y = k, x)]Demographic Parity [28] ( [34] andI A=1 P r(A=1) -I A=0 P r(A=0) )[0, 1, Pr(M = 1|x)] Equality of Opportunity [34] t(A, 1)[0, Pr(Y = 1|x), Pr(M = 1, Y = 1|x)] t(A, 1)[0, Pr(Y = 1|x), Pr(M = 1, Y = 1|x)] Equalized Oddst(A, 0)[Pr(Y = 0|x), 0, Pr(M = 0, Y = 0|x)]Therefore, we can find the average deferral loss on distribution µ asEQUATIONWe aim to find a randomized algorithm A that defines a probability distribution µ A on H × R that solves the optimization problemEQUATIONwhere Ψ i is a performance measure that induces the desired constraint in our optimization problem. We assume that Ψ i , similar to ℓ def , is an outcome-dependent function, i.e., if the deferral occurs, the outcome of the classifier does not change Ψ i , and otherwise, if deferral does not occur, the human decision does not change Ψ i . In other words, the value of the constraints can only be a function of input feature x and of the deferral system prediction Ŷ = r(x)M + 1 -r(x) h(x). 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 ≤ δ, limits the rejection function to defer up to δ proportion of the instance, (2) demographic parity that is formulated as P ( Ŷ = 1|A = 0) -P ( Ŷ = 1|A = 0) ≤ δ, 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 |P r( Ŷ = 1|A = 1, Y = 1) -P r( Ŷ |A = 0, Y = 1)| ≤ δ 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.e., max y=0,1 P r( Ŷ = 1|A = 1, Y = y) -P r( Ŷ = 1|A = 0, Y = y) ≤ δ, (5) out-ofdistribution (OOD) detection that is written as Pr out (r(X) = 0) ≤ δ 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 a balanced error of classifier prediction on instances where deferral does not occur. Achieving this objective as mentioned in [53] is equivalent to minimizingK i=1 1 αi Pr(Y ̸ = h(X), r(X) = 0|Y ∈ G i ) when the feasible set is Pr(r(X) = 0, Y ∈ G i ) = αi K, and where {G i } K i=1 is a partition of classes, and finally (7) type-k error bounds that is a generalization of Type-I and Type-II errors, limits errors of a specific class k using Pr( Ŷ ̸ = k|Y = k) ≤ δ. All above constraints are expected values of outcome-dependent 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 us to show that (see Appendix C) obtaining the optimal classifier and rejection function is equivalent to obtaining the solution off * = [f * 1 , . . . , f * d ] ∈ argmax f ∈∆ X d E ⟨f (X), ψ 0 (X)⟩ , s.t. E ⟨f (x), ψ i (x)⟩ ≤ δ i , i ∈ [1 : m] (3)where ∆ d is a simplex of d dimensions, d = L + 1, and ψ i : X → R d is defined asEQUATIONthat we name the embedding function2 corresponding to the performance measureΨ i for i ∈ [0 : m],where for simplifying the notation we define Ψ 0 ≡ -ℓ def . Furthermore, the optimal algorithm is obtained by predicting h(x) = i with normalized probability off * i (x)/ d-1 j=1 f * j (x), where d-1 j=1 f * j (x) ̸ = 0, and rejecting r(x) = 1 with probability f * d (x). In case of d-1j=1 f * j (x) = 0 the classifier is defined arbitrarily. A list of embedding functions for the mentioned constraints and objectives is provided in Table 1 (See Appendix D for derivations). Hardness. We first derive the following negative result for the optimal deterministic predictor in (3) . 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, if we assume that the distribution of X contains finite atoms x 1 , . . . , x n , each of which have probability of Pr(X = x i ) = p i , and if we setψ 1 (x i ) = [0, wi pi ] and ψ 0 (x i ) = [0, vi pi ] for v i , w i ∈ R + , then (3) reduces in argmax i f 1 (x i )v i subjected to f 1 : X → {0, 1} and i f 1 (x i )w i ≤ δ 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 ψ 0 and ψ 1 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 -1 losses and assume X to be finite. Finding an optimal deterministic classifier and rejection function for a bounded expert intervention budget is an NP-Hard problem. Note that the above finding is different from the complexity results for deferral problems in [49, Theorem 1] and [23, Theorem 1] . NP-hardness results in these settings are consequences of restricting the search to a 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 L2D. In the next section, by finding a closed-form solution for the randomized algorithm, we show that such relaxation indeed simplifies the problem. 
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 H 0 , H 1 as two distributions with density functions g 0 (x) and g 1 (x) for which a given point x can be drawn. Then, they maximize the probability of correctly rejecting H 0 , while bounding the probability of incorrectly rejecting H 0 , i.e., for a test T (x) ∈ [0, 1] that rejects the null hypothesis when T (x) = 1, they solved the problemEQUATIONThey 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) = 1 when g 1 (x)/g 0 (x) > k and take the value T (x) = 0 when g 1 (x)/g 0 (x) < k, where k is a scalar and dependent on α.Multi-hypothesis testing with rewards. In this section, we aim to solve (3) as a generalization of Neyman-Pearson lemma for binary testing to the case of multi-hypothesis 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 H 0 , . . . , H d-1 , each of which corresponding to X being drawn from the density function g i (x) for i ∈ {0, . . . , d -1}. Further, assume that for each hypothesis H i , in case of true positive, we receive the reward r i (x), and in case of false negative, we receive the loss ℓ i (x). Assume that we aim to find a test f : X → ∆ d that for each input x ∈ X rejects d -1 hypotheses, each hypothesis H i with probability 1 -f 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 argmaxEQUATIONThis problem can be seen as instance of (3), when we setψ 0 (x) = [r 0 (x), . . . , r d-1 (x) g d-1 (x) g0(x) ] and ψ 1 (x) = j̸ =0 ℓ j (x) gj (x) g0(x) , . . . , j̸ =d-1 ℓ j (x) gj (x) g0(x). Similarly, we can show that for all ψ 0 (x), ψ 1 (x) in (3) there exists a set of densities g 1 (x), . . . , g d-1 (x) and rewards and losses such that ( 6) and ( 3) are equivalent. This can be done by setting g i ≡ g 0 and noting that the mapping from ℓ i s and r i s into ψ 0 and ψ 2 is invertible. The formulation of (3) can be seen as an extension of the setting in [69] when we move beyond type-k error bounds to a 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 defineEQUATIONthat 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-GNP). For a set of functionsψ i where i ∈ [0, m], assume that (δ 1 , . . . , δ m ) is an interior point 3 of the set F = E[⟨r(x), ψ 1 (x)⟩], . . . , E[⟨r(x), ψ m (x)⟩] : f ∈ ∆ X d .Then, there is a set of fixed values k 1 , . . . , k m and τ ∈ T d such that the predictorEQUATIONobtains the optimal solution of sup f ∈∆ X d E ⟨f (x), ψ 0 (x)⟩ , subjected to the constraints being achieved tightly, i.e., when for i ∈ [1 : m] we have E ⟨f (x), ψ i (x)⟩ = δ i . If k 1 , . . . , k m are further non-negative, then f * (x) is the optimal solution to (3). Moreover, all optimal solutions of (3) that tightly achieve the constraints are in form of (8) almost everywhere on X . Example 1 (L2D with Demographic Parity). In the setting that we have a deferral system and we aim for controlling demographic disparity under the tolerance δ, we can set ψ 0 (x) = Pr(Y = 0|x), Pr(Y = 1|x), Pr(Y = M |x) and ψ 1 (x) = s(A) 0, 1, Pr(M = 1|x) , using Table 1 , where s(A) := I A=1 P r(A=1) -I A=0 P r(A=0) . Therefore, d-GNP, together with the discussion after (4) shows that the optimal classifier and rejection function are obtained ash(x) = 1 Pr(Y = 1|x) > 1+ks(A) 2 0 Pr(Y = 1|x) < 1+ks(A) 2 ,andr(x) = 1 Pr(Y = M |x) -ks(A) Pr(M = 1|x) > λ(A, x) 0 Pr(Y = M |x) -ks(A) Pr(M = 1|x) < λ(A, x) ,for a fixed value k ∈ R, and where λ(A, x) := max{Pr(Y = 0|x), Pr(Y = 1|x) -ks(A)}. The above identities imply that the optimal fair classifier for the deferral system thresholds the scores for different demographic groups using two thresholds ks(0) and ks(1). This is similar in form to the optimal fair classifier in vanilla classification problem [14, 20] . However, the rejection function does not merely threshold the scores for different groups, but adds an input-dependent threshold ks(A) Pr(M = 1|x) to the unconstrained deferral system scores.It 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 fairness 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 a 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 as ψ 0 (x) = p 0 x , p 1 x , p M x and ψ 1 (x) = t(A, 1) 0, p 1 x , Pr(M = 1, Y = 1|x) , respectively, where p i x := Pr(Y = i|x) for i ∈ {1, 2} and similarly p M x = Pr(Y = M |x). Therefore, the characterization of optimal classifier and rejection function using d-GNP results inEQUATIONr(x) = 1 p M x 1 -kt(A, 1) Pr(M = 1|Y = M, x) > ν(A, x) 0 p M x 1 -kt(A, 1) Pr(M = 1|Y = M, x) < ν(A, x), for k ∈ R and where ν(A, x) := max{p 0 x , 1 -kt(A, 1) p 1 x }. Assuming 2 -kt(A, 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( Ŷ = 0|A = 0) -Pr( Ŷ = 0|A = 1) ≤ δ or equality of opportunity Pr( Ŷ = 0|Y = 0, A = 0) -Pr( Ŷ = 0|Y = 0, A = 1) ≤ δ on Class 0, then we can follow similar steps as in Appendix D to find the embedding functions as ψ DP = s(A) 1, 0, . . . , 0 and ψ EO = t(A, 0) p 0x , 0, . . . , 0 , where p i x := Pr(Y = i|x) for i ∈ [L]. As a result, since the accuracy embedding function is ψ 0 (x) = p 0 x , . . . , p L x , then, by neglecting the effect of randomness, the optimal classifier under such constraints are as h DP (x) = argmax p 0x -ks(A), p 1 x , . . . , p L x , and h EO (x) = argmax p 0 x 1 -kt(A, 0) , p 1 x , . . . , p L x . 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.Note that although Theorem 4.1 characterizes the optimal solution of (3), it leaves us uninformed regarding parameters k 1 , . . . , k m , and further does not give us the form of the optimal solution when ψ 0 (x) -m i=1 k i ψ i (x) 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 f * k,p (x) = τ ψ 0 (x) -kψ 1 (x), x where τ is a member of T d such that if there is a non-singleton set I of maximizers of a vector y ∈ R d , then we have τ (y, x) (i) = p and τ (y, x) (j) = 1-p, where i and j are the first indices in I that minimizes ψ 1 (x), and maximizes ψ 0 (x), respectively. In this case, k is a member of the setK = t : δ ∈ lim τ ↑t C(τ ), C(t)where C(t) = E ⟨f * t,0 (x), ψ 0 (x)⟩ is the expected constraint of the predictor f * t,0 . Moreover, p = . 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 δ ′ i < δ i . Now, if we can assure that the constraint tuples are still inner points of F when we substitute δ i by δ ′ i , then Theorem 4.1 shows that ( 8) is 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 a performance measure by δ and -δ. However, since both bounds cannot hold tightly and simultaneously unless the tolerance is δ = 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.C(k)-c C(k)-lim τ ↑t -C(τ ) , if C(•)In the next section, we design an algorithm based on these results and show its generalization to the unseen data. 
empirical d-gnp and its statistical generalization: 
 In previous sections, we obtained the optimal solution to the constrained optimization problem (3) using d-GNP. Based on this optimal solution, we can design a plug-in method (see Algorithm 1 in Appendix F) to solve the constrained learning problem using empirical data. This algorithm varies from many Lagrangian-based algorithms for solving constrained learning problem (e.g., Primal-Dual method [10] ) in which the optimal predictor parameter and constraint penalties are dependent to each other, and therefore we should learn them iterativaly. However, as we saw in Theorem 5.1 (respectively in Algorithm 1), the solution of d-GNP is a mere thresholding on the corresponding embedding functions, where the threshold is obtained in a post-hoc manner and from validation dataset. Therefore, although Lagrangian-based algorithms can lead to oscillations or converge with 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 Neyman-Pearson [1, 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. Theorem 5.1 (Generalization of the Constraints). For the approximation of the Neyman-Pearson solution fk , p(x) in Algorithm 1 such that E S n ⟨ fk , p(x), ψi (x)⟩ ≤ δ i for i ∈ [1 : m], if we assume that embedding functions are bounded, then ford n (ϵ) ≃ O( √ log n+ √ log 1/ϵ √ n) and S n ∼ µ we haveE µ ⟨ fk , p(x), ψ i (x)⟩ ≤ δ i + d n ( ϵ m) for all i ∈ [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 ψi (x) in hand where ∥ ψi (x) -ψ i (x)∥ ∞ ≤ ϵ ′ with high probability, this theorem together with Hölder's inequality shows that we need to assure E S n ⟨ fk , p(x), ψi (x)⟩ ≤ δ -d n ( ϵ m ) -ϵ ′ to achieve the corresponding generalization with high probability. 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 (γ, ∆)-sensitivity condition as the following. This is an extension to detection condition in [71] and assumes that changing the parameter in predictor leads to a detectable change in constraints. Definition 5.2. For an embedding function ψ 1 , and a distribution µ X on X , we refer to a function r k (x) as a prediction with (γ, ∆)-sensitivity around k, if there exists C ∈ R + such that for all δ ∈ (0, ∆] we haveEQUATIONNow, we express the following generalization theorem for predictors that address the above conditions:Theorem 5.3 (Generalization of Objective). Assume that (δ -ϵ l , δ + ϵ u ) is a subset of of all achievable constraints E ⟨f (x), ψ 1 (x)⟩ , and that ∥ψ i (x)∥ ∞ ≤ 1 for i = 1, 2.Further, let the size n of validation data be large enough such thatd n (δ/3) ≤ ϵ l 2 . Now, if the optimal predictor f * k,0 (x) is (γ, ∆)-sensitive around optimal k * for ∆ ≃ Ω d 1/γ n (δ/3), δ 1/2γ 0 , δ 1/2γ 1 and γ ≤ 1, then for n ≥ 16 ϵ 2 l log 3δ , and with probability at least 1 -δ, the optimal empirical classifier, as of Algorithm 1 has an objective that is at most O d1/γ n (δ/3), δ 1/γ 0 , δ 1/2 0 , δ 1/2 1 , C -1/γ , C -1/2 -far from the true optimal objective. Now that we have proven generalization of our post-processing method, we should briefly compare this to other possible algorithms to learn an approximation of the optimal classifier and rejection function pair. A possible method is to find the appropriate 'defer' or '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 1 n -suboptimal solution for human intervention budget as shown in Theorem G.1), they do not necessarily generalize to unseen data. In particular, we can show that for all algorithms that estimate deferral labels from 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 are not interchangeable. This argument is further formalized in the following proposition: Proposition 5.4 (Impossibility of generalization of deferral labels). For every deterministic deferral rule r for empirical distributions and based on the two losses 1 m̸ =y and 1 h(x)̸ =y , there exist two probability measures µ 1 and µ 2 on X × Y × M such that the corresponding (r, X) for both measures is distributed equally. However, the optimal deferral r * µ1 and r * µ2 for these measures are not interchangeable, that isL µi def (h, r * µi ) ≤ 1 3 while L µi def (h, r * µj ) = 2 3 for i = 1, 2 and j ̸ = i.In a nutshell, this proposition implies that, every algorithm that reduces the two-bit data of human accuracy and AI accuracy for an input into a 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-processing algorithms that are used in multi-objective L2D problems. We refer the reader to Appendix M for more details and proof of aforementioned proposition.6 Experiments COMPAS dataset. We implemented 4 Algorithm 1, first for COMPAS dataset [27] in which the recidivism rate of 7214 criminal defendants is predicted. The human assessment is done in this Figure 3 : Prediction of d-GNP on Hatespeech dataset [22] and for tweets with predicted African-American (left), and Non-African-American (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. 5 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 et 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 at least three crowd workers as hate speech, offensive but not hate speech, or neither hate speech nor offensive. We used a pre-trained model [5] to detect whether the tweet contains an African-American dialect. Next, we used d-GNP method to control the demographic disparity of predicting a tweet hate speech or offensive bounded by δ HS = 0.1 and δ O = 0.01. In the result of this experiment that is displayed in Figure 3 we can observe the following points: (i) in test-time the resulting demographic disparity for both classes are bounded as expected, (ii) the accuracy of d-GNP method is 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 African-American dialect, and otherwise either bias the classifier scores or use a mixture of human and classifier involvement to achieve the final controlled disparity. ACS dataset. We further tested our method on folktables dataset [25] that contains an income prediction task based on 1.6M rows of American Community Survey data. Since we had no access to human expert data, we simulated a 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 2 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. 
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 a 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 a large data regime. 
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 Matthäus Kleindessner for his significant intellectual contributions to the first draft of this paper. The idea of obtaining an extension to the 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 is thankful to Deutsche Bahn in that regard.  
 
 Appendix: Here, we show an example of lack of compositionality of fairness criteria for learn-to-defer problems. This falls in line with [29] , where the authors studied the effect of the operators such as 'OR' or 'AND'. Here, we show that a similar non-compositionality holds for the operator 'DEFER'. The following example is found based on the insight that a fair predictor is fair over all the space X , and if it could take a decision over only a subset of X it will not necessarily be a fair predictor. This can be seen as a 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. Let us assume that the space X contains only four points x 1 , x 2 , x 3 , and x 4 , and that the input takes these values with probability Pr(X = x 1 ) = Pr(X = x 2 ) = Pr(X = x 3 ) = Pr(X = x 4 ) = 1 4 . The first two points x 1 , x 2 are corresponded to the demographic group A = 0 and the last two points are corresponded to the demographic group A = 1. Further, assume that the conditional target probability isPr(Y = 1|x 1 ) = Pr(Y = 1|x 2 ) = Pr(Y = 1|x 3 ) = Pr(Y = 1|x 4 ) = 1.Moreover, we consider the equality of opportunity as the measure of fairness. Now, assume that the classifier h(•) : X → {0, 1} is taking values h(x 1 ) = 1, h(x 2 ) = 0, h(x 3 ) = 1, and h(x 4 ) = 0 and the human decision maker predicts M = 0 conditioned on x 1 , M = 1 conditioned on x 2 , and M = 1 conditioned on x 3 , and M = 0 conditioned on x 4 . Therefore, both classifier and human expert have accuracy of 1 2 on the data. Following the above assumptions, we can find the fairness measure for classifier asEQUATIONwhich means that the classifier is fully fair. We can derive a similar result for the human expert, i.e.,EQUATIONNow that we established a fair classifier and a 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 1 the classifier is accurate, while for x 2 the human expert is accurate. Furthermore, for x 3 and x 4 they both are equally inaccurate. Therefore, an optimal solution is not to defer for x 1 , and defer for x 2 , and take an arbitrary decision for x 3 and x 4 . Now, if we find the fairness measure of the resulting deferral predictor, we haveEQUATIONor equivalently the resulting predictor is unfair for the demographic group A = 1. This means the 'DEFER' composition of the predictors does not preserve fairness. One can further easily show that no deferral system from the above classifier and human expert that has the accuracy better than 1 2 is fair.The deferral problem has been studied under a variety of conditions. Rejection learning [19, 3, 11, 15] or selective classification [30, 33, 32] , assumes that a fixed cost is incurred to the overall loss, when ML 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 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 a near-optimal classifier and deferral rule is required as a solution of empirical risk minimization [23, 24] . Most recently, the implementation of deferral rules using neural networks and surrogate losses is studied for binary and multi-class classification [8, 50, 12, 51, 9, 43, 48, 45] . A possible shift in human expert for L2D methods recently studied in [67] . 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 [74, 41] for L2D and rejection learning, respectively. Neyman-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-Pearson problem is studied in two lines of works: (i) the generalization of direct (in-processing) solutions to the optimization problem [65, 64, 61] , and (ii) the generalization of plug-in methods [71] that first approximate the score functions and then use Neyman-Pearson 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 errors, and (ii) be valid in absence of strong duality assumption. Further, the idea of using Neyman-Pearson lemma for controlling fairness criteria originally dates back to [76] (later as [75] ). More recently, a similar post-processing method is 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 post-processing method is a linear combination of scores, they have no 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.Here, we first characterize functions that are outcome-dependent. To that end, we define ı(x) asEQUATIONThis function can retrieve the value of r(x) and can retrieve the value of h(x) only if r(x) = 0. In fact, we can obtain r(x) = ı(x) (L + 1) and h(x) = i if r(x) = 0 and ı(x) (i) = 1. Therefore, for a function Ψ(x, h(x), r(x)) = E Y,M |X=x Ψ(x, Y, M, h(x), r(x)) and ℓ def (x, h(x), r(x)) = E Y,M |X=x ℓ def (x, Y, M, h(x), r(x)) to be outcome dependent, it must only be a function of x and ı(x). In fact, we must haveEQUATIONandEQUATIONfor a choice of Ψ ′ and ℓ ′ def , whereℓ def (x, h(x), r(x)) = E Y,M |X=x ℓ def (x, Y, M, h(x), r(x)) . Now, we can check that ı(x) can take L + 1 different values, in each of which one of its components takes the value 1 and others take the value 0. Therefore, by conditioning on each of these L + 1 values we haveEQUATIONwhere ψ i (x) is defined asEQUATIONSimilarly, we can show thatEQUATIONwhere ⃗ ℓ def (x) is defined asEQUATIONNext, we know that due to the randomization of A, the vector ı(x) can take various values on each instance x. This, however, is not the case for ψ i (x) and ⃗ ℓ def (x), since they are defined independent of r(x) and h(x). Therefore, the average of constraints and loss can be rewritten asEQUATIONandEQUATIONwhere f (x) is defined asEQUATION)Therefore, the optimization problem in ( 2) is effectively reduced to the linear programming problem in (3) . Moreover, if f * (x) is the solution to that linear program, then the corresponding r(x) should be distributed as Pr(r(x) = 1) = f * (x) (L + 1), where h(x) should be distributedas Pr(h(x) = i) = Pr(h(x) = i|r(x) = 0) = f (x) (i) L i=1 f (x) (j). Note that the assumption of 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) = 1.In this appendix we derive the embedding functions in Table 1 that are corresponded to the constraints of choice, as named in 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 a 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 ℓ def (x, h(x), r(x)) in this case, as defined in (1) is obtained asℓ def (x, h(x), r(x)) =E Y,M |X=x I r(x)=1 I M ̸ =Y + I r(x)=0 I h(x)̸ =Y = I r(x)=1 Pr(M = Y |X = x) + I r(x)=0 Pr(Y ̸ = h(x)|X = x).Therefore, using (19) we find ⃗ ℓ def as⃗ ℓ def = Pr(Y ̸ = 1|X = x), . . . , Pr(Y ̸ = n|X = x), Pr(Y ̸ = M |X = x) .• Expert intervention budget: In this case, similar to the case before, we first derive Ψ(x, h(x), r(x)). To that end, we first note that the expert intervention constraint in Section 3 is equivalent withPr(r(X) = 1) = E x∼µ X ,(r,h)∼A I r(x)=1 ≤ δ,which in turn suggests thatΨ(x, h(x), r(x)) = I r(x)=1 .Next, we find ψ(x) using ( 17), asψ(x) = [0, . . . , 0, 1].• OOD Detection: To obtain the corresponding embedding function to the OOD detection constraint in Section 3, we can rewrite Pr out r(X) = 1 asPr out r(X) = 1 = E X∼f out X ,(r,h)∼A I r(X)=1 = E X∼µ X in ,(r,h)∼A I r(X)=1 f out X (X) f in X (X), where the last equation holds when X and X out are absolutely continuous distributions, and therefore have probability density functions. A similar assumption is made by [53] . This results in Ψ(x, h(x), r(x)) being obtained asΨ(x, h(x), r(x)) = I r(x)=1 f out X (X) f in X (X). Therefore, we conclude that the embedding function can be calculated using (17) asψ(x) = 0, . . . , 0, f out X (X) f in X (X) ].In the simple case that f outX (x) = f in X (x)I f in X (x)≤ϵ f in X (x)I f in X (x)≤ϵ dx, the embedding function is equal toψ(x) = 0, . . . , 0, I f in X (x)≤ϵ Pr in (f in X (X) ≤ ϵ)].• Long-Tail Classification: This methodology aims to minimize the balanced loss1 K K i=1 Pr(Y ̸ = h(X)|r(X) = 0, Y ∈ G i ).However, as mentioned in [52] , this optimization problem can be rewritten asK i=1 Pr(Y ̸ = h(X), r(X) = 0|Y ∈ G i ) α i , s.t. Pr(r(X) = 0|Y ∈ G i ) = α i K .Therefore, the objective can rewritten asK i=1 E (r,h)∼A,X ′ ∼µ X Pr(Y ̸ = h(X), r(X) = 0, Y ∈ G i |X = X ′ ) α i Pr(Y ∈ G i ) ,which together with (17) shows thatψ 0 (x) = - K i=1 Pr(Y ̸ = 1, Y ∈ G i |X = x) α i Pr(Y ∈ G i ) , . . . , K i=1 Pr(Y ̸ = L, Y ∈ G i |X = x) α i Pr(Y ∈ G i ) , 0 .The reason that we use negative sign is because in the definition of (3) we aim to maximize the objective. Similarly, we can rewrite the objectives asE (r,h)∼A,X ′ ∼µ X Pr(r(X) = 0, Y ∈ G i |X = X ′ ) -αi K Pr(Y ∈ G i ) Pr(Y ∈ G i ) .Therefore, using (17) we can obtain ψ i (x) asEQUATION• Type-k Error Bound: We first rewrite Type-k constraint in 3 asEQUATIONwhere (a) is followed by chain rule. Next, we condition Pr( Ŷ ̸ = k|Y = k, X = x) on r(X) being 1 and 0, which concludes thatPr( Ŷ ̸ = k|Y = k, X = x) = Pr( Ŷ ̸ = k, r(x) = 1|Y = k, X = x) + Pr( Ŷ ̸ = k, r(x) = 0|Y = k, X = x) = Pr(M ̸ = k, r(x) = 1|Y = k, X = x) + Pr(h(x) ̸ = k, r(x) = 0|Y = k, X = x) = E (r,h)∼A,M |X=x,Y =k I M ̸ =k I r(x)=1 + I h(x)̸ =k I r(x)=0 = E (r,h)∼A|X=x,Y =k Pr(M ̸ = k|X = x, Y = k)I r(x)=1 + I h(x)̸ =k I r(x)=0 .Therefore, using (24) we conclude thatPr( Ŷ ̸ = k|Y = k) = E X ′ ∼µ X ,(r,h)∼A I r(X)=1 Pr(M ̸ = k, Y = k|X = X ′ ) Pr(Y = k) + E X ′ ∼µ X ,(r,h)∼A I h(X ′ )̸ =k I r(X ′ )=0 Pr(Y = k|X = X ′ ) Pr(Y = k) ,which together with (17) shows that the embedding function is obtained asψ(x) = Pr(Y = k|X = x) Pr(Y = k) 1, . . . , 1, 0 k , 1, . . . , 1, Pr(M ̸ = k|X = x, Y = 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 = x is generated independent of the value of Y 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 asEQUATIONHere, we find the corresponding embedding function ψ(x) for the upper-bound in the above inequality. For the lower-bound, we can use -ψ(x) 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( Ŷ = 1|A = 0) -Pr( Ŷ = 1|A = 1) asEQUATIONNow, similar to what we did in previous section, we condition Pr( Ŷ = 1, A = a) for a ∈ {0, 1} on the value of h(x) and r(x), and we concludeEQUATIONHere, we used the assumption of independence of X and (M, Y ) given a choice of X.As a result of ( 26), (27) , and (17) we can find the embedding function asψ(x) = 0, Pr(A = 1|X = x) Pr(A = 1) - Pr(A = 0|X = x) Pr(A = 0) , Pr(M = 1, A = 1|X = x) Pr(A = 1) - Pr(M = 1, A = 0|X = x)Pr(A = 0) .• (In-)Equality of Opportunity: Similar to the previous items, we rewrite equality of opportunity constraint in Section 3 as-δ ≤ Pr( Ŷ = 1|Y = 1, A = 1) -Pr( Ŷ = 1|Y = 1, A = 0) ≤ δ.Again, we only consider the upper-bound and rewrite Pr( Ŷ = 1|Y = 1, A = 1) -Pr( Ŷ = 1|Y = 1, A = 0) asEQUATIONNext, by conditioning on r(X) = 1 and r(X) = 0, we rewriteEQUATIONEQUATIONwhere the last identity is followed by the assumption of independence of A and (Y, M, A) given an instance X = x.As a result of ( 28), (29) , and (17) we can obtain the embedding function asψ(x) = 0, Pr(Y = 1, A = 1|X = x) Pr(Y = 1, A = 1) - Pr(Y = 1, A = 0|X = x) Pr(Y = 1, A = 0) Pr(M = 1, Y = 1, A = 1|X = x) Pr(Y = 1, A = 1) - Pr(M = 1, Y = 1, A = 0|X = x)Pr(Y = 1, A = 0) .• (In-)Equality of Odds: This induces the same constraint as that of equality of opportunity, and further induces an extra constraint that is in 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ψ 1 (x) = 0, Pr(Y = 1, A = 1|X = x) Pr(Y = 1, A = 1) - Pr(Y = 1, A = 0|X = x) Pr(Y = 1, A = 0) Pr(M = 1, Y = 1, A = 1|X = x) Pr(Y = 1, A = 1) - Pr(M = 1, Y = 1, A = 0|X = x) Pr(Y = 1, A = 0) ,and another similar to that with changing Y = 1 into Y = 0, and therefore asEQUATIONPr(M = 1, Y = 0, A = 1|X = x) Pr(Y = 0, A = 1) - Pr(M = 1, Y = 0, A = 0|X = x) Pr(Y = 0, A = 0) .A variety of works have tackled constrained classification problems using cost-sensitive modeling [42, 17, 57] . In other words, they use the expected loss that is 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 we concern is that during this process, the optimal predictor is achieved only when the corresponding cost-sensitive Lagrangian has a single saddle point in terms of coefficients and predictors. Such assumption, unless by analyzing the Lagrangian closely, is hard to 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 L2D problem when human intervention budget is controlled. Suppose that the features in X are distributed with an atomless probability measure µ X (e.g., normal or uniform distribution). 6 Further, assume that the human has perfect information of the label, i.e. Y = M , while the input features have no information of the label, i.e., Pr(Y = 1|X = x) = 1/2 for all x ∈ 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 no clear maximizer, without loss of generality can be set to h(x) ≡ 1.For such assumptions, if we write the Lagrangian in form ofEQUATIONor to put it 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., we cannot guarantee argmin r∈[0,1] L(λ * , r) = f * , where λ * ∈ argmax λ min r∈[0,1] L(λ, r), and f * ∈ argmin r∈[0,1] max λ L(λ, r). In fact, this guarantee holds only in particular examples, e.g., when L(λ * r , r) is strictly convex [7, page 8] . In fact, if we optimize r for all λ as in RHS of (30), we can show that r λ (x) = 1 λ < 1 2 0 otherwise .Therefore, λ * can be obtained as λ * = argmax λ≥0 (λ -1/2) --λb where (x) -:= min{x, 0}. This can be rewritten asλ * = argmax λ≥0 -1 2 -λ(b -1) 0 ≤ λ ≤ 1 2 -λb λ > 1 2 = 1 2 .Hence, the condition λ < 1/2 is never satisfied and we have r λ * (x) = 0, i.e., we should never defer.For the deferral rule r λ * , the deferral loss (1) isL µ def (h, f ) = E X,Y,M ℓ AI (Y, h(X), X) = 1 2 .To show that r λ * is not optimal, we provide random and deterministic deferral rules f * and r * * that satisfy the constraint in (2), while having a smaller deferral loss: ⋄ Let f * (x) = b, that is a 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 f * (x) is equal toL µ def (h, f * ) = E[r(X)] b • E[ℓ H (Y, M )] 0 + E[1 -r(X)] 1-b • E[ℓ AI (Y, h(X))] 1 2 = 1 -b 2 < 1 2 .⋄ The second example is a deterministic deferral rule. Since the probability measure on X is atomless, for all b ∈ [0, 1] there exists a set A such that Pr(X ∈ A) = b [31, Proposition 215D]. Hence, defining r * * (x) = 1 x∈A the constraint in (2) is met. Similar to the last example L µ def (h, r * * ) = 1-b 2 < 1 2 .The above two examples show that the deferral rule r λ * is sub-optimal. The reason is that, for optimality of r λ * we should make sure that L(λ * r , r) has a single minimizer of r. However, in our example we had L( 1 2 , r) = -λb has infinite number of minimizers in terms of r(x). Therefore, the equality of the solutions to minimax problem and maximin problem is not guaranteed. Obtain closed-form of {ψ i (x)} m i=0 using ℓ def and Ψ i s via (4) and in terms of the scores as in Table 1 4:Estimate the scores in Table 1 Find k = min k over the feasibility set Ĉ(t) ≤ δ 1 10:if k = ∅ then 11:Return 'Not Feasible'12:else 13: if Ĉ( k -ϵ) -Ĉ(k * ) ≤ 1e -3 then 14:p ← 0 15: else 16: p ← δ-Ĉ( k) Ĉ( k-ϵ)-Ĉ( k)s i (x) 24: r * (x) := argmax i∈{0,1} s h * (x) (x), s L (x) 25:Return h * (x), r * (x) 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 of 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-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 a classifier h(x) and dataset D = {(x i , y i , m i )} n i=1 , where we assume x i ̸ = x j , i ̸ = 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) at most 1 n -suboptimal (in terms of deferral loss) compared to the optimal random deferral rule for the empirical distribution on D.Next in 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 a result, if we observe enough pairs of (x i , y i ), then Defer the b|D| tasks with the lowest ℓ H (x, y, m) -ℓ AI (x, y) to human 7:end if 8: end procedure we improve upon such estimation of conditional probability and increase the accuracy of the obtained classifier. However, we argue that this paradigm is inapplicable in the case of deferral rule as follows. Although the output r of Algorithm 2 for each feature x is a deterministic 0 or 1 label, it varies with the choice of the dataset D. Hence, if we draw datasets from a distribution µ, the outcome of r becomes probabilistic. In the following, we introduce two probability distributions µ 1 and µ 2 over (X, Y, M ) such that for random draws of the dataset from µ i , the conditional probability of such optimal deferral label r 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 i , y i , m i )} n i=1 that contains i.i.d. samples from the distribution µ XY M . Further, assume that we have no budget constraint, that is b = 1 in Algorithm 2. Therefore, the optimal randomized deferral rule over the empirical distribution is the solution of the problemmin ri∈[0,1] n i=1 1 mi̸ =yi ri + 1 h(xi)̸ =yi 1 -ri .It is easy to see that the solution to this problem is given by ri = 0 if 1 h(xi)̸ =yi < 1 mi̸ =yi and ri = 1 if 1 h(xi)̸ =yi > 1 mi̸ =yi . As a result, the optimal deferral is obtained asEQUATIONAmong all the possible policies, we can chooseri = 1 m i = y i & h(x i ) ̸ = y i 0 o.w. .Next, we assume that we have a classifier h and two probability distributions µ 1 and µ 2 over (X, Y, M ).For both distributions X is uniformly distributed over [0, 1], and we have µ1 (Y = M, h(X) = Y ) = 2 3 , µ 1 (Y = M, h(X) ̸ = Y )= 1 3 and µ 2 (Y ̸ = M, h(X) = Y ) = 2 3 , µ 2 (Y = M, h(X) ̸ = Y )= 1 3 .We can see that although the observed rs are fixed for a given choice of D, since D is randomly drawn, r values are randomly distributed. Furthermore, the distribution of Pr(r|X) is according to Bern( 13 ), since in both cases we have µ i (Y = M, h(X) ̸ = Y ) = 1 3 . However, the optimal deferral rule for the first distribution is r * 1 (x) = 1 for all x ∈ X , since we have L µ1 def (h, r * 1 ) = 0, while for the second case the optimal deferral rule is r * 2 (x) = 0 for all x ∈ X because we have L µ2 def (h, r * 2 ) = 1 3 . Furthermore, such deferral rules are not interchangeable, because we have L µ1 def (h, r * 2 ) = L µ2 def (h, r * 1 ) = 2 3 . As a result, Pr(r|X) 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 (Impossibility of generalization of deferral labels). For every deterministic deferral rule r for empirical distributions and based on the two losses 1 m̸ =y and 1 h(x)̸ =y , there exist two probability measures µ 1 and µ 2 on X × Y × M such that the corresponding (r, X) for both measures is distributed equally. However, the optimal deferral r * µ1 and r * µ2 for these measures are not interchangeable, that is L µi def (h, r * µi ) ≤ 1 3 while L µi def (h, r * µj ) = 2 3 for i = 1, 2 and j ̸ = i. Proof. As mentioned in (31) , there are four possibilities of a deterministic deferral rule for empirical distribution based on the events h(X) ̸ = Y and M ̸ = Y . The reason is thatr =        1 h(x) ̸ = y , m = y 0 h(x) = y , m ̸ = y a h(x) ̸ = y , m ̸ = y b h(x) = y , m = y ,the parameters a and b can take binary values. One of the cases in which a = b = 0 is analyzed previously in this section. We study the other cases as follows:1. a = 1, b = 0: In this case we haver = 1 h(x) ̸ = y 0 o.w. .If we define a measure µ 1 such thatµ 1 h(X) ̸ = Y, M = Y = 1 3 , µ 1 h(X) = Y, M ̸ = Y ) = 2 3 ,and a measure µ 2 such thatµ 2 h(X) ̸ = Y, M = Y = 1 3 , µ 2 h(X) = Y, M = Y = 2 3 ,then on one hand one can see that r is according to Bern( 1 3 ) 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 µ 2 , we have r * µ1 (x) = 0 while r * µ2 (x) = 1. Therefore, we conclude thatL µ1 def (r * µ1 , h) = 1 3 ,and L µ2 def (r * µ2 , h) = 0, while the losses with interchanging deferral policies are equal toL µ1 def (r * µ2 , h) = L µ2 def (r * µ1 , h) = 2 3 .2. a = 0, b = 1: In this case, the deferral rule is asr = 0 m ̸ = y 1 o.w. .Next, if we set two probability measures µ 1 and µ 2 such thatµ 1 M ̸ = Y, h(X) = Y = 1 3 , µ 1 M = Y, h(X) ̸ = Y ) = 2 3 ,andµ 2 M ̸ = Y, h(X) = Y = 1 3 , µ 2 M = Y, h(X) = Y = 2 3 ,then r is according to Bern( 23 ) in both cases. However, r * µ1 = 1 while r * µ2 = 0. Furthermore, the expected deferral losses are equal toL µ1 def (r * µ1 , h) = 1 3 , L µ2 def (r * µ2 , h) = 0,while after interchanging the deferral policies we haveL µ1 def (r * µ2 , h) = L µ2 def (r * µ1 , h) = 2 3 .3. a = 1, b = 1: In this case, the deferral rule is asr = 0 h(x) = y, m ̸ = y 1 o.w. .Next, if we set two probability measures µ 1 and µ 2 such thatµ 1 M ̸ = Y, h(X) = Y = 1 3 , µ 1 M = Y, h(X) ̸ = Y ) = 2 3 ,andµ 2 M ̸ = Y, h(X) = Y = µ 2 M ̸ = Y, h(X) ̸ = Y = µ 2 (M = Y, h(X) = Y ) = 1 3 ,then we can see that r has the distribution Bern( 23 ). However, one can find the optimal deferral policies for the true distributions are r * µ1 = 1 and r * µ2 = 0. Furthermore, we haveEQUATIONL µ2 def (r * µ2 , h) = 2 3 , while L µ1 def (r * µ1 , h) = 1 3 , L µ2 def (r * µ2 , h) = 1 3 .Let X = {x 1 , . . . , x n } and Y = {1, . . . , n}. We first show that obtaining the optimal classifier is of O(n) complexity, since in this case is equivalent to obtaining the Bayes optimal classifier in isolation. The reason is that, the unconstrained Bayes optimal classifier is a deterministic classifier that minimizesh * (x) ∈ argmin ŷ E µ Y |X ℓ AI (Y, ŷ, X)|X = x ,for all x ∈ X . This is regardless of whether the deferral occurs or not. Therefore, this solution is further the solution toh * (x) ∈ argmin ŷ E µ Y |X (1 -r(X))ℓ AI (Y, ŷ, X)|X = x = argmin ŷ E µ Y,M |X (1 -r(X))ℓ AI (Y, ŷ, X) + r(X)ℓ H (Y, M, X)|X = x ,for every rejection function r, including the optimal rejection function of the constrained optimization problem. In the particular case of expert intervention budget, the constraint is further independent of h and is only a function of 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 in whichE µ Y |X ℓ AI (Y, 1, X)|X = x > E µ Y |X ℓ AI (Y, 0, X)|X =x for all x ∈ X , and therefore h(x) = 1 over all input space.Further, we assume the data distribution has the property µ XY M = µ XY δ(M = Y ), i.e. M = Y on all the data. In this case, we know thatE ℓ H (Y, M, X)|X = x i = E 1 M ̸ =Y |X = x i = 0,and we defineE ℓ AI (Y, h(X), X)|X = x i = E 1 Y ̸ =1 |X = x i = ℓ i .Now, if we set Pr(X = x i ) = p i , and r(x i ) = r i , then the optimization problemEQUATIONNext, we show that the above problem spans all instances of the 0 -1 knapsack problem, which is known to be NP-hard (Theorem 15.8 of [58] ). LetEQUATIONbe an instance of the 0 -1 knapsack problem7 with w i , c i > 0, i ∈ [n], and K > 0. With ℓ i = ci/wi n i=1 ci/wi , p i =We start this proof by introducing a few useful lemmas: Lemma I.1. The set F = ∆ X n of all functions that map X to an n-dimensional probability is weakly compact, i.e., for each sequence {f n } ∞ n=1 , there is a sub-sequence {f ni } and a function f * ∈ F such that for all measurable embedding functions ψ, we havelim k→∞ E ⟨f n k , ψ⟩ = E ⟨f * , ψ⟩ .Proof. We know that all components of each element of the function sequence is bounded by 1. We define {f i m } ∞ m=1 as the sequence of the ith component of the function sequence. Therefore, using [42, Theorem A.5.1] we know that there is a sub-sequence {f 1m 1 k } ∞k=1 and a non-negative 1-bounded function f * 1 , such that for each µ-integrable function ψ 1 (x) we have limk→∞ E µ f 1 m k (x)ψ 1 (x) = E µ f * 1 (x)ψ 1 (x) .Next, we can repeat the same process for {f i E µ f i+1 m i+1 k (x)ψ i+1 (x) = E µ f * i+1 (x)ψ i+1 (x) .Now, since all sub-sequences of a converging sequence converges to the same limit, we can use m n k that is the intersection of all sequences and show thatlim k→∞ E µ f i m n k (x)ψ i (x) = E µ f * i (x)ψ i (x) ,for all i ∈ [1 : n] and integrable functions ψ i . As a result, due to interchangeability of limit and summation, when the sum is over a finite set of elements, it is easy to show thatlim k→∞ E ⟨f m n k , ψ⟩ = lim k→∞ E n i=1 f n m n k (x)ψ i (x) = n i=1 lim k→∞ E f n m n k (x)ψ i (x) = n i=1 E µ f * i (x)ψ i (x) = E µ ⟨f * (x), ψ(x)⟩ .Next, we need to show that f * ∈ 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 is a non-zero set A where µ(A) > 0 and there exists l > 0 such that | i f * i -1| ≥ l for all x ∈ A. We know that there is either a subset B ⊆ A with µ(B) > 0 such that for all x ∈ B we have i f * i (x) ≥ 1 + l, or similarly a subset for which i f * i (x) ≤ 1 -l. The reason is that otherwise a non-zero measure set A is a union of two zero-measure set, which is a contradiction. Without loss of generality we assume the first, which means i f * i (x) ≥ 1 + l for x ∈ B. Now, if we define ψ(x) = [1, . . . , 1] for x ∈ B and otherwise ψ(x) = [0, . . . , 0], then we haveE µ ⟨f * (x), ψ(x)⟩ ≥ (1 + l)µ(B), while E µ ⟨f m n k (x), ψ⟩ = 1, for all k ∈ N. This is a 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 E ⟨f (x), ψ i (x)⟩ = δ i for i ∈ [1 : m], we show that the supremum of the objective function E ⟨f (x), ψ 0 (x)⟩ is a maximum, (ii) we show that it is sufficient for a predictor f ∈ C to be in form of (8) to achieve the maximum objective E ⟨f (x), ψ 0 (x)⟩ in C and also for all predictors with E ⟨f (x), ψ i (x)⟩ ≤ δ i , (iii) we show that the space of all possible constraints for any prediction function in ∆ X d is convex and compact, and (iv) we show that if 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 it follows the thresholding rule (8) almost everywhere.• Step (i): Due to the definition of supremum, we know that for each ϵ > 0, there exists a function f ϵ in C such that E ⟨f ϵ , ψ 0 (x)⟩ ≥ sup f ∈C E ⟨f, ψ 0 (x)⟩ -ϵ. Equivalently, there is a sequence of functions f n for which lim n→∞ E ⟨f n , ψ 0 (x)⟩ = sup f ∈C E ⟨f, ψ 0 (x)⟩ . Using weakly-compactness of the function class ∆ X n+1 as in Lemma I.1, we know that for the sequence f n , there exists a subsequence f n k and a functionf * ∈ ∆ X n+1 such that lim k→∞ E ⟨f n k , ψ m+1 (x)⟩ = E ⟨f * (x), ψ m+1 (x)⟩ .Furthermore, we know that each subsequence a n k of a converging sequence a n has the same limit as the limit of the mother sequence a n [59, Chapter 2, Theorem 1]. Therefore, we haveE ⟨f * (x), ψ m+1 (x)⟩ = sup f ∈C E ⟨f, ψ m+1 (x)⟩ ,which means that the supremum of the objective is achievable by f * . Moreover, for ψ i (x) where i ∈ [1 : m], we have E ⟨f n , ψ i (x)⟩ = δ i for all n, which concludesδ i = lim k→∞ E ⟨f n k , ψ i (x)⟩ = E ⟨f * (x), ψ i (x)⟩ .This means that the equality constraints holds for f * , i.e., f * ∈ C, if it holds for each predictor f n . • Step (ii): Assume that there is a predictor f such that E ⟨ f , ψ i ⟩ ≤ δ i . In this step, we show that if exists a predictor f in form of ( 8) and in C, then f always has smaller objective than f . To that end, consider the following expression:A = E ⟨f (x) -f (x), ψ 0 (x) - m i=1 k i ψ i (x)⟩ .Now, we know thatE ⟨f (x) -f (x), m i=1 k i ψ i (x)⟩ = m i=1 k i E ⟨f (x), ψ i (x)⟩ -E ⟨ f (x), ψ i (x)⟩ (a) = m i=1 k i δ i -E ⟨ f (x), ψ i (x)⟩ ≥ 0,where (a) holds because f ∈ C. As a result, if A ≥ 0, then we could show thatEQUATIONand complete the proof.To that end, first note that both f and f are in ∆ X d , and therefore⟨f (x), [1, . . . , 1]⟩ = ⟨ f (x), [1, . . . , 1]⟩ = 1.As a result, for any fixed scalar c, we have⟨f (x) -f (x), ψ 0 (x) - m i=1 k i ψ i (x)⟩ = ⟨f (x) -f (x), ψ 0 (x) - m i=1 k i ψ i (x) -c⟩. (35)Next, we fix c to be the maximum component of the vectorψ 0 (x) - m i=1 k i ψ i (x), i.e., c := max i∈[1:d] {ψ i 0 (x) - m j=1 k j ψ i j (x)}.Now, we rewrite A using (35) asA = E ⟨f (x) -f (x), ψ 0 (x) - m i=1 k i ψ i (x) -c⟩ = d i=1 E (f i (x) -fi (x))(ψ i 0 (x) - m j=1 k j ψ i j (x) -c)⟩Now, we consider two cases for which E i 1 (x) : f i (x) > fi (x), and E i 2 (x) :f i (x) ≤ fi (x). If f i (x) > fi (x), then we have f i (x) > 0, because 1 ≥ fi (x) ≥ 0 for all i ∈ [1 : d].Therefore, using the definition of S d and because f ∈ S d we haveEQUATIONConsequently, we haveA = d i=1 E (f i (x) -fi (x))(ψ i 0 (x) - m j=1 k j ψ i j (x) -c)⟩ = d i=1 E (f i (x) -fi (x))(ψ i 0 (x) - m j=1 k j ψ i j (x) -c)⟩|E i 1 (x) Pr E i 1 (x) + d i=1 E (f i (x) -fi (x))(ψ i 0 (x) - m j=1 k j ψ i j (x) -c)⟩|E i 2 (x) Pr E i 2 (x) (a) = d i=1 E (f i (x) -fi (x))(ψ i 0 (x) - m j=1 k j ψ i j (x) -c)⟩|E i 2 (x) Pr E i 2 (x) (b) ≥ 0,where (a) holds due to (36) and (b) holds because f i (x) ≤ fi (x) andψ i m+1 (x) - m j=1 k j ψ i j (x) ≤ c = max i∈[1:n+1] {ψ i m+1 (x) - m j=1 k j ψ i j (x)}.As a result, we have A ≥ 0 that concludes (34) and completes the proof of this step. v M v * * v * v ′ v * * v * vG = E[⟨f (x), ψ 1 (x)⟩], . . . , E[f (x), ψ m (x)] : f ∈ ∆ X d },is compact under Euclidean metric, and convex.To show the compactness of that space, assume that there is a sequence {g n } ∞ n=1 such that lim n→∞ g n = g, or accordingly there is a sequence off n ∈ ∆ X d for which lim n→∞ E[⟨f n (x), ψ 1 (x)⟩], . . . , E[f n (x), ψ m (x)] = (g 1 , . . . , g m ). Since the metric is Euclidean, this is equivalent to lim n→∞ E[⟨f n (x), ψ i (x)⟩] = g i for all i ∈ [1 : m]. The weak compactness of ∆ Xd , as proved in Lemma I.1, shows that there exists f * and a subsequencef n k such that lim k→∞ E[⟨f n k (x), ψ i (x)⟩] = E[⟨f * , ψ i (x)⟩] for all i ∈ [1 : d].Therefore, because of the choice of Euclidean metric, we havelim k→∞ E[⟨f n k (x), ψ 1 (x)⟩], . . . , E[⟨f n k (x), ψ m (x)⟩] = E[⟨f * , ψ 1 (x)⟩], . . . , E[⟨f * , ψ m (x)⟩] ,which is equivalent to compactness of G.To show the convexity of G, it is enough to prove the convexity of ∆ X d . The reason is thatg(f ) = E[⟨f (x), ψ 1 (x)⟩], . . . , E[f (x), ψ m (x)] is a linear functional of f , and a linear functional images a convex set to another convex set. To prove the convexity of∆ X d , let f, f ′ ∈ ∆ X d . This means that f i (x), f ′ i (x) ∈ [0, 1] for all i ∈ [1 : d] and d i=1 f i (x) = d i=1 f ′ i (x) = 1. Consequently, af i (x) + (1 -a)f ′ i (x) ≥ 0, since a, 1 -a ≥ 0. Moreover, d i=1 af i (x) + (1 -a)f ′ i (x) = a d i=1 f i (x) + (1 - a) d i=1 f ′ i (x) = a + 1 -a = 1.As a result of these two facts, af + (1 -a)f ′ ∈ ∆ X d , and the proof of this step is completed.• Step (iv): In this step we show that if the tuple of constraints is an interior points of all possible achievable tuples of constraints using different prediction functions, then a point in C achieves its supremum in terms of objective E ⟨f (x), ψ 0 (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 pointsE[⟨f (x), ψ 1 (x)⟩], . . . , E[f (x), ψ m (x)]and the space M of all points E[⟨f (x), ψ 1 (x)⟩], . . . , E[f (x), ψ 0 (x)] are compact and convex. Now, assume that v = (δ 1 , . . . , δ m ) is an interior point of N . Then, the corresponding set in M, i.e., B v = {(δ 0 , . . . , δ m ) ∈ M : δ 0 ∈ R} has a supremum and an infimum of the first component that we name δ * * and δ * . Now, since M is compact, then v * * = (δ * * , δ 1 , . . . , δ m ) and v * = (δ * , δ 1 , . . . , δ m ) are contained in M. Next, assume the following two cases:1. δ * * = δ * : In this case for all other points v = (δ 1 , . . . , δ m ) of N , the corresponding set B v ′ in M is a single point. The reason is that, if it is not so, then we have two points v * * = (δ * * , δ 1 , . . . , δ m ) and v * = (δ * , δ 1 , . . . , δ m ) where δ * * > δ * . Now, since v is an interior point of N , then on any direction in a small neighborhood around v there exists a point v ′ within N . Let that direction be opposite the connecting line of v and v, i.e., let v be on a connecting line of v ′ and v * . Now, make a convex hull using the three points v ′ , v * * , and v * , which are all in M. Because of the convexity of M, the convex hull is also a subset of M. Since v 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 δ * = δ * * . (See Figure 4 ) Now, we know that in such case all points within N have one corresponding point in M. Because of the convexity of M this is equivalent to M being a subset of a hyperplane with the generating formulax 0 = m i=1 k i x i + k 0 . Therefore, we have E ⟨f, ψ 0 ⟩ = E ⟨f, m i=1 k i ψ i ⟩ + k 0 for all f ∈ ∆ X d . Therefore, for d ≥ 2, if we set f 1 = ( p(x) d-2 , . . . , p(x) d-2 , 1 -p(x) i , p(x) d-2 , . . . , 0 j , p(x) d-2 , . . . , p(x) d-2 ) and f 2 = ( p(x) d-2 , . . . , p(x) d-2 , 0 i , p(x) d-2 , . . . , 1 -p(x) j , p(x) d-2 , . . . , p(x) d-2 ) for p(x) ∈ [0, 1] X , then we have E ⟨f 1 , ψ 0 ⟩ -E ⟨f 1 , m i=1 k i ψ i ⟩ = E ⟨f 2 , ψ 0 ⟩ -E ⟨f 2 , m i=1 k i ψ i ⟩ ,or equivalentlyE (1 -p(x))(ψ i 0 (x) - m t=1 k t ψ i t (x) -ψ j m+1 (x) + m t=1 k t ψ j t (x)) = 0,for all function p(x) ∈ ∆ X d . A similar result can be achieved for d = 2 and by setting f 1 = (p(x), 1 -p(x)) and f 2 = (1 -p(x), p(x)). As a result, we haveψ i 0 (x) - m t=1 k t ψ i t (x) = ψ j 0 (x) - m t=1 k t ψ j t (x),for all i ̸ = j ∈ [1 : d],and consequentlyψ i 0 (x) - m t=1 k t ψ i t (x) = max j∈[1:d] {ψ j 0 (x) - m t=1 k t ψ j t (x)}, for all i ∈ [1 : n + 1]. As a result, there is a set of k 1 , . . . , k m such that ψ 0 (x) - m i=1 k i ψ i (x)has equal components almost everywhere. As a result, due to the freedom of choice for τ (ψ 0 (x) -m i=1 k i ψ i (x), x) where τ ∈ S d 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 τ (ψ m+1 (x) -m i=1 k i ψ i (x), x). 2. δ * * > δ * : In such case, for all δ 0 ∈ [δ * , δ * * ], we can show that v = (δ 0 , . . . , δ m ) is an interior point of M.To show that, we first find m points v ′ 1 , . . . , v ′ m ∈ N that are linearly independent and such that their convex hull include (δ 1 , . . . , δ m ). Using the definition of M, for each of these pointsv ′ i = (δ ′ 1 i , . . . , δ ′ m i ), there exists h ′ i ∈ R such that v ′′ i = (h ′ i , δ ′ 1 i , . . . , δ ′ m i) is within M. Now, we add the two points v * * and v * to these sets of points. It is easy to see that v ′′ i s are linearly independent. Furthermore, we know that(δ 1 , . . . , δ m ) is a convex combination of v ′ i s, i.e., i a i v ′ i = (δ 1 , . . . , δ m ). As a result, if i b i v ′′ i -v * * = (0, . . . , 0), then we have b i = a i for i ∈ [1 : m]. Furthermore, we have a i h ′ i = b i h ′ i = δ * * . Similarly, if i c i v ′′ i -v * = (0, . . . , 0) we have c i = a i and a i h ′ i = c i h ′ i = δ * .As a result, since δ * ̸ = δ * * at least one of these cases would not occur, or equivalently, the dimension of the convex hull of v ′′ 1 , . . . v ′′ m , v * * , v * is of dimension m + 1. As a result, v is an interior point of this convex hull, and because the convex hull is (m + 1)-dimensional, it is an interior point of M. Now, since v * * is a border point in M and due to the convexity of M there is a hyperplane P such that it passes v * * and it lays above all points of M. Since v is an interior point of M, a neighborhood of v is laid under the hyperplane P, hence v cannot be laid on the hyperplane. Therefore, if the generating formula of such hyperplane ism i=0 k i x i = m i=1 k i δ i + k 0 δ * * , since v is not laid on the hyperplane we assure that m i=1 k i δ i + k 0 δ 0 ̸ = m i=1 k i δ i + k 0 δ * * ,or equivalently k 0 ̸ = 0. Hence, without loss of generality assume that k 0 = -1. This shows that for all points in (u 0 , . . . , u m ) ∈ M we haveu 0 - m i=1 k i u i ≤ δ * * - m i=1 k i δ i ,or equivalently, by the definition of M, for all prediction function f , we haveE ⟨f (x), ψ 0 (x) - m i=1 k i ψ i (x)⟩ ≤ δ * * - m i=1 k i δ i .Assuming that f ∈ C maximizes the objective, we haveEQUATIONThis shows that almost everywhere when there is a unique maximizing component j inψ 0 (x) - m i=1 k i ψ i (x), then fj (x) = 1.The reason is that otherwise and if there is a set A such that µ(A) > 0 and for x ∈ A and a choice of l ∈ [0, 1), ϵ ∈ R, and all t ̸ = j we haveψ j m+1 (x) - m i=1 k i ψ j i (x) ≥ ϵ + ψ t m+1 (x) - m i=1 k i ψ t i (x) while f j ≤ 1 -l, then we can make a function f (x) that is f (x) = f (x) for x ∈ X \ A and f (x) = [0, . . . , 1 j , . . . , 0] for x ∈ A. Such function leads to E ⟨f (x), ψ 0 (x) - m i=1 k i ψ i (x)⟩ ≥ ϵlµ(A) + E ⟨ f (x), ψ 0 (x) - m i=1 k i ψ i (x)⟩ ,that is in contradiction with (37) . This completes the proof of this step.In the following, we introduce a few lemmas that are useful in our proofs.Lemma J.1. For every random variable X on R we havelim τ →t -Pr(τ ≤ X < t) = lim τ →t + Pr(t < X < τ ) = 0 Proof. For each increasing sequence {τ i } ∞i=1 we show that the first limit is zero, which proves the claim that the function of τ has a zero limit. We defineS i = [τ i , t),and notice thatS 1 ⊇ S 2 ⊇ . . . . Further, we note that ∞ i=1 S i = ∅.EQUATION∞ i=1 S c i = R.Next, because probability measure is σ-additive, we conclude its lower-semicontinuity [38, Theorem 13.6] , and therefore we havelim i→∞ Pr(X ∈ S c i ) = Pr(X ∈ ∪ ∞ i=1 S c i ) = 1,which proves lim i→∞ Pr(X ∈ S i ) = 0.We could take similar steps to show that since∞ i=1 (t, τ ′ i ) = ∅ for decreasing τ ′ i we have lim i→∞ Pr(X ∈ (t, τ ′ i )) = 0.Lemma J.2. Let ψ 1 : X → R d be a bounded function. Further, we define two functionsEQUATIONF (k) = E ⟨f * k,1 (x), ψ 0 (x)⟩ , where f * k,p is defined in Theorem 4.2. Then, 1. C(k) is monotonically non-increasing, 2. C(k) is upper semi-continuous, 3. F (k) is monotonically non-decreasing, 4. D(k) is lower semi-continuous, and we have 5. lim k ′ ↑k C(k) = lim k ′ ↑k D(k) Proof.1. Firstly, let us define ℓ k (x) = ψ 0 (x) -kψ 1 (x). For the setting where p = 0, the prediction function f * k,p (x) is defined asEQUATIONFurther, for k 1 , k 2 such that k 1 ≤ k 2 , let us define j 1 and j 2 as the only non-zero index of f * k1,0 (x, p) and f * k2,0 (x, p), respectively. To show that C(k) is monotonically non-increasing we only need to show that ψ 1 (x) (j 1 ) = ⟨f * k1,0 (x), ψ 1 (x)⟩ ≥ ⟨f * k2,0 (x), ψ 1 (x)⟩ = ψ 1 (x) (j 2 ). Assume that this does not occur, or equivalently ψ 1 (x) (j 1 ) < ψ 1 (x) (j 2 ).In such case we haveEQUATIONwhere (a) and (b) holds due to the definition of j 1 and j 2 , and (c) holds due to the assumption ψ 1 (x) (j 1 ) < ψ 1 (x) (j 2 ). The last inequality is clearly a contradiction, and shows that ⟨f * k1,0 (x), ψ 1 (x)⟩ ≥ ⟨f * k2,0 (x), ψ 1 (x)⟩, and therefore C(k 1 ) ≥ C(k 2 ). 2. Let us divide the space X into two subsetsA k = x ∈ X : argmax i (ℓ k (x))(i) = d , B k = x ∈ X : argmax i (ℓ k (x))(i) ∈ [1 : d -1] . For each x ∈ A k we know f * k,0 (x) (i) = 1 i = min{argmin j ψ 1 (x) (j)} 0 otherwiseUsing previous part, we know that by increasing k we have no increase in ⟨f * k,0 (x), ψ 1 (x)⟩, and in this case since ⟨f * k,0 (x), ψ 1 (x)⟩ = min j ψ 1 (x) (j), then this value cannot reduce with the change of k. Therefore, ⟨f * k,0 (x), ψ 1 (x)⟩ is a constant function for all k ′ ≥ k, and consequentlyE ⟨f * k ′ ,0 (x), ψ 1 (x)⟩|x ∈ A k Pr(x ∈ A k ) is a constant function for k ′ ≥ k. If x ∈ B k , then for j / ∈ argmax i ℓ k (x) (i) and l ∈ argmax i ℓ k (x) (i), we have ℓ k (x) (j) < ℓ k (x) (l). Define the set C δ for δ ≥ 0 as C δ = {x ∈ B k : ℓ k (x) (j) ≤ ℓ k (x) (l) -δ}.Using Lemma J.1 we know thatlim δ→0 Pr(B k \ C δ ) = 0,or equivalently for all ϵ ≥ 0, there exists δ such thatPr(B k \ C δ ) ≤ ϵ ′ .Therefore, if without loss of generality, we assume that ψ 1 (x) is bounded by 1, then there exists δ ≥ 0 such that we haveE ⟨f * k ′ ,0 (x), ψ 1 (x)⟩|x ∈ B k \ C δ Pr(x ∈B k \ C δ ) (a) ≤ ∥ψ 1 (x)∥ ∞ Pr(x ∈ B k \ C δ ) ≤ ϵ/2,where (a) holds due to Hölder's inequality. If x ∈ C δ , and because we assumed ∥ψ 1 (x)∥ ∞ ≤ 1, then we know that by increasing k to k ′ ∈ [k -δ/2, k + δ/2), we haveEQUATIONThis means that⟨f * k,0 (x), ψ 1 (x)⟩ = min j∈J ψ 1 (x) (j) ≤ min j∈I ψ 1 (x) (j) = ⟨f * k ′ ,0 (x), ψ 1 (x)⟩.This, together with the previous part in which we showed ⟨f * k,0 (x),ψ 0 (x)⟩ ≥ ⟨f * k ′ ,0 (x), ψ 0 (x)⟩, concludes that ⟨f * k,0 (x), ψ 0 (x)⟩ = ⟨f * k ′ ,0 (x), ψ 0 (x)⟩. This means that E ⟨f * k ′ ,0 (x), ψ 0 (x)⟩|x ∈ C δ Pr(x ∈ C δ ) is a constant function for all k ′ ≥ k . Finally, since we have C(k ′ ) = E ⟨f * k ′ ,0 (x), ψ 1 (x)⟩ =E ⟨f * k ′ ,0 (x), ψ 1 (x)⟩|x ∈ A k Pr(x ∈ A k ) + E ⟨f * k ′ ,0 (x), ψ 1 (x)⟩|x ∈ B k \ C δ Pr(x ∈ B k \ C δ ) + E ⟨f * k ′ ,0 (x), ψ 1 (x)⟩|x ∈ C δ Pr(x ∈ C δ ), and because the first term and the third term in RHS are constant in terms of k ′ and for k ′ ≥ k, and the second term is diminishing, then we haveC(k ′ ) -C(k) = E ⟨f * k ′ ,0 (x), ψ 1 (x)⟩|x ∈ B k \ C δ Pr(x ∈ B k \ C δ ) -E ⟨f * k,0 (x), ψ 1 (x)⟩|x ∈ B k \ C δ Pr(x ∈ B k \ C δ ) ≤ ϵ/2 + ϵ/2, which is equivalent to say that lim k ′ ↑k C(k ′ ) = C(k).3. For p = 1, we know that the prediction function f * k,p (x) is obtained asf * k,1 (x) =    1 i = min{ argmax j∈argmax ℓ k (x) ψ 0 (x) (j)} 0 otherwise . If we define ψ ′ 1 (x) := -ψ 0 (x), then we have f * k,1 (x) =    1 i = min{ argmin j∈argmax ℓ k (x) ψ ′ 1 (x) (j)} 0 otherwise .Since the above is equal to (38) , then using the first part of this lemma, we know thatEQUATION, ψ 0 (x)⟩ being monotonically non-decreasing. 4. This part is similar to the second part of the proof. In fact, if x ∈ A k , then we haveEQUATION)For k ′ ≤ k and because of the third part of this lemma, we know that ⟨f * k ′ ,1 (x), ψ 0 (x)⟩ ≥ ⟨f * k,1 (x), ψ 0 (x)⟩. Furthermore, because of ( 41) we know that ⟨f * k,1 (x), ψ 0 (x)⟩ = max ψ 0 (x), and therefore by reducing k ′ , the prediction functionf * k ′ ,1 (x) stays constant. As a result, E ⟨f * k ′ ,1 (x), ψ 1 (x)⟩|x ∈ A k Pr(x ∈ A k ) is a constant function for k ′ ≤ k.Furthermore, similar to the second part of this lemma, we can show that for each ϵ > 0, there exists δ ′ ≥ 0 such that for all 0 ≤ δ ≤ δ ′ we haveEQUATIONMoreover, for the case of x ∈ C δ , since in this case J ⊆ I, then we know thatEQUATIONNext, using the third part of this lemma, we know that for k ′ ≤ k we haveEQUATION, ψ 0 (x)⟩, which together with (43) concludes that ⟨f * k,1 (x), ψ 0 (x)⟩ = ⟨f * k ′ ,1 (x), ψ 0 (x)⟩. Next, because ψ 0 (x) -kψ 1 (x) (i) = ψ 0 (x)kψ 1 (x) (j) for i, j ∈ J , then we know thatℓ k ′ (x) (i) -ℓ k ′ (x) (j) = (k - k ′ ) ψ 1 (x))(i) -ψ 1 (x))(j) ≤ 2|k -k ′ |.Therefore, if for i, j ∈ J we know that ψ 0 (x) (i) = ψ 0 (x) (j), then the difference between ψ 1 for those indices is bounded asEQUATIONNow, we know that becausex ∈ C δ , then ⟨f * k,1 (x), ψ 1 (x)⟩ = ψ 1 (x) (i) for i ∈ argmax j∈J ψ 0 (x) (j), and ⟨f * k ′ ,1 (x), ψ 1 (x)⟩ = ψ 1 (x) (j) for j ∈ argmax k∈I ψ 0 (x) (j).Hence, we can see that i ∈ J ⊆ I and j ∈ I, and because ψ 0 (x) (i) = ⟨f * k,1 (x), ψ 0 (x)⟩ = ⟨f * k ′ ,1 (x), ψ 0 (x)⟩ = ψ 0 (x) (j), and due to (44) we haveEQUATIONFinally, we can rewrite D(k ′ ) asD(k ′ ) = E ⟨f * k ′ ,1 (x), ψ 0 (x)⟩ =E ⟨f * k ′ ,1 (x), ψ 0 (x)⟩|x ∈ A k Pr(x ∈ A k ) + E ⟨f * k ′ ,1 (x), ψ 0 (x)⟩|x ∈ B k \ C δ Pr(x ∈ B k \ C δ ) + E ⟨f * k ′ ,1 (x), ψ 0 (x)⟩|x ∈ C δ Pr(x ∈ C δ ),and because of ( 42) and (45) , and since the first term is a constant function in terms of k ′ and for all k ′ ∈ [k -δ/2, k], then we haveEQUATIONThis shows that D(k ′ ) is lower semi-continuous around k ′ = k. 5. To prove this part, we first divide X into two subsetsEQUATIONandEQUATIONThis concludes thatEQUATIONMoreover, let us define the setΨ k ′ 1 = {x ∈ X : ∃c ∈ R, ∀j ∈ argmax ℓ k ′ (x), ψ 1 (x) (j) = c} . We show that sum of the probabilities of H k ′ \ Ψ k ′1 is always bounded by 2 d for a set of choices for k ′ , or equivalentlyEQUATIONfor all finite or countably infinite choice of K ⊆ R + . In fact, we know that for each instance x, argmax j∈ [1:d] ℓ k (x) (j) can take up to 2 d cases of all subsets of {1, . . . , d}. Therefore, we need to show that there cannot exist two values of k, k ′ such that forEQUATIONIf we prove such identity, then due to pigeonhole principle, we haveEQUATIONwhich by integration over all values of x concludes in (50) . We prove this claim by contradiction. If we assume k, k′ ∈ K such that for x ∈ H k \ Ψ k 1 ∩ H k ′ \ Ψ k ′ 1 the identity (51) holds, then because x ∈ H k ∩ H k ′ , then the size of argmax j ℓ k (x) (j) and argmax j ℓ k ′ (x) (j) is at least 2. This concludes that ψ 0 (x) -kψ 1 (x) (i) = ψ 0 (x) -kψ 1 (x) (j)as well asψ 0 (x) -k ′ ψ 1 (x) (i) = ψ 0 (x) -k ′ ψ 1 (x) (j)for all choices of i, j ∈ argmax ℓ k (x). As a result, we have(k -k ′ ) ψ 1 (x) (i) -ψ 1 (x) (j) = 0,and because k ′ ̸ = k, we haveψ 1 (x) (i) = ψ 1 (x) (j),for all i, j ∈ argmax ℓ k (x). Therefore, x ∈ Ψ k ′ 1 and that is a contradiction. Now that we know that the sum of the probabilities of Pr(x ∈ H k ′ \ Ψ k ′ 1) is bounded, we can renormalize that and make a probability measure asg(A) = k∈A,Pr(x∈H k \Ψ k 1 )>0 Pr(x ∈ H k \ Ψ k 1 ) k:Pr(x∈H k \Ψ k 1 )>0 Pr(x ∈ H k \ Ψ k 1 ).Due to Lemma J.1, for all ϵ ≥ 0 we can find a small enough δ ≥ 0 such that g([k -δ, k)) ≤ ϵ/2 d+1 , and therefore for all k ′ ∈ [k -δ, k) we havePr(x ∈ H k ′ \ Ψ k ′ 1 ) ≤ t∈[k-δ,k),Pr(x∈Ht\Ψ t 1 )>0] Pr(x ∈ H t \ Ψ t 1 ) = g [k -δ, k) k:Pr(x∈H k \Ψ k 1 )>0 Pr(x ∈ H k \ Ψ k 1 ) ≤ ϵ 2 d+1 2 d = ϵ/2,where the last inequality holds because of (50). Now, using this and due to (49) , and by defining g i (x) = ⟨f * k,i (x), ψ 0 (x)⟩ for i = 1, 2, we can bound the difference of D(k) and C(k) asD(k) -C(k) = E g 1 (x) -g 0 (x)| x ∈ H k ′ Pr(x ∈ H k ′ ) ≤ Pr(x ∈ H k ′ \ Ψ k ′ 1 |x ∈ H k ′ ) E g 1 (x) -g 0 (x)| x ∈ H k ′ \ Ψ k ′ 1 + Pr(x ∈ H k ′ ∩ Ψ k ′ 1 |x ∈ H k ′ ) E g 1 (x) -g 0 (x)| x ∈ H k ′ ∩ Ψ k ′ 1 (a) ≤ 2(ϵ/2) + E g 1 (x) -g 0 (x)| x ∈ H k ′ ∩ Ψ k ′ 1 (b) = ϵ, where (a) holds because ∥f * k,0 -f * k,1 ∥ 1 ≤ ∥f * k,0 ∥ 1 + ∥f * k,1 ∥ 1 = 2 and because of Hölder inequality we have ⟨f * k,0 (x) -f * k,1 , ψ 1 (x)⟩ ≤ ∥f * k,0 -f * k,1 ∥ 1 ∥ψ 1 (x)∥ ∞ ≤ 2.Moreover, to show that (b) holds we know that for x ∈ Ψ k ′ 1 we have ψ 1 (x) (i) = ψ 1 (x) (j) for all i, j ∈ argmax ℓ k ′ (x). Therefore, because we know g 0 (x) = ψ 1 (x) (i) for i ∈ argminj∈argmax l ℓ k ′ (x) (l) ψ 1 (x) (j) ⊆ argmax l ℓ k ′ (x) (l) and g 1 (x) = ψ 1 (x) (j) for j ∈ argmax j∈argmax l ℓ k ′ (x) (l) ψ 0 (x) (j) ⊆ argmax l ℓ k ′ (x) (l), we have g 0 (x) = g 1 (x). The above inequality proves that the limit of C(k ′ ) and D(k ′ ) for k ′ ↑ k are equal and that completes the proof.To prove this theorem, we take the following steps: (i) We show that the set K has a non-negative member, (ii) we show that the prediction function f * k,p (x) achieves the inequality constraint tightly, and by Theorem 4.1 we can conclude that f * k,p (x) is the optimal solution. • step (i): It is easy to see that the Bayes optimal solution of the prediction function in (3) without any constraint isf * (x) (i) =    1 ψ 0 (x) (i) > ψ 0 (x) (j) for all j ̸ = i 0 ψ 0 (x) (i) < max j ψ 0 (x) (j) p i (x) otherwise, where p i (x) ∈ ∆ d is an arbitrary vector. We can see that by settingp i (x) (j) =    1 j = min{ argmin t∈argmax ℓ0(x) ψ 1 (x) (t)} 0 otherwise, then the two prediction functions f * (x) and f * 0,0 (x) are equal (See statement of Theorem 4.2). Now, in the first and second part of Lemma J.2 we have shown that E ⟨f * k,0 (x), ψ 1 (x)⟩ is upper semi-continuous and monotonically non-increasing. Therefore, for all k ∈ R + we haveE ⟨f * k,0 (x), ψ 1 (x)⟩ ≤ E ⟨f * 0,0 (x), ψ 1 (x)⟩ = E ⟨f * (x), ψ 1 (x)⟩ .Similarly, we can show that for k → ∞, the solution is equivalent to the Bayes minimizer off * * (x) = argmin f ∈∆ X d E ⟨f (x), ψ 1 (x)⟩ .Therefore, since δ is an interior point of all possible values, it lays on the interval E ⟨f * * (x), ψ 1 (x)⟩ , E ⟨f * (x), ψ 1 (x)⟩ , due to the montonicity and upper semicontinuity of E ⟨f * k,0 , ψ 1 (x)⟩ , we can find t such thatEQUATIONMoreover, this t should be a positive scalar, since otherwise we have (54) .E ⟨f * t,0 (x), ψ 1 (x)⟩ ≥ E ⟨f * 0,0 (x), ψ 1 (x)⟩ = E ⟨f * (x), ψ 1 (x)⟩ > δ, which is a contradiction to• step (ii): In this step, we consider the following two cases:-C(t) is continuous at t: In this case, ( 54) is equivalent to δ = C(t) = E ⟨f * t,0 (x), ψ 0 (x)⟩ , which means that the prediction function f * k,0 (x) achieves the constraint tightly, and therefore using Theorem 4.1 f * k,0 (x) is the optimal solution. -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 ∈ G k and x ∈ X \ G k , where G k is defined in (47) . We know that in the latter case x ∈ X \ G k , the prediction function f * k,p can be decomposed into two componentsEQUATIONwhile for x ∈ G k the prediction functionEQUATION) for all p ∈ [0, 1]. Therefore, in both cases (55) holds, and we haveEQUATIONwhere C(•) and D(•) are defined in Lemma J.2. Using this lemma, we know that D(•) is lower semi-continuous, andlim k ′ ↑k C(k) = lim k ′ ↑k D(k).Therefore, together with (56) and the definition of p in the statement of theorem, we haveEQUATIONEquivalently, the prediction function achieves the constraint inequality tightly, and therefore by Theorem 4.1 this is sufficient to be the optimal solution to the constrained optimization problem.we prove that the VC dimension of the hypothesis class of all such functions is less than the VC dimension of G = f : R × R → {0, 1} : f (x, y) = sgn(x -k 1 )sgn(k 2 -y), k 1 , k 2 ∈ R . The reason is that if the aforementioned interval can shatter a set S, then we can find the corresponding values of f 1 (x) and f 2 (x) for each x ∈ S, and then form the pair (x i , y i ) where x i = f 1 (x) and y i = f 2 (x), and by setting k 1 = k 2 = k, we can shatter the set {(x i , y i )} |S| i=1 with G. Note that here all pairs are identical. The reason is that if not, i.e., if f 1 (x) = f 1 (x ′ ) and f 2 (x) = f 2 (x ′ ) for x, x ′ ∈ S and x ̸ = x ′ , then, for all possible k, we have sgn(k -f 1 (x))sgn(f 2 (x) -k) = sgn(k -f 1 (x ′ ))sgn(f 2 (x ′ )-k), and therefore we cannot shatter S by sgn(k -f 1 (x))sgn(f 2 (x)-k). Therefore, the set {(x i , y i )} |S| i=1 has the same cardinality of S, which in consequence proves that the VC dimension of all sgn(k -f 1 (x))sgn(f 2 (x) -k) is bounded by V C(G). Moreover, V C(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 V C(G) ≤ 4.Up to now, we have shown that the class of functions equal to the first two terms of (60) has a VC dimension that is bounded by 4. Next, we show that multiplying a hypothesis class H with a binary function ϕ(x) does not increase the VC dimension of that class. More formally, if we defineH = {ϕ(x)f (x) : f ∈ H ′ }, then V C(H) ≤ V C(H ′ ).The reason is that if we can shatter a set S using H, then for each member x ∈ S there exists two members f 1 , f 2 of H ′ such that f 1 (x) = 1 and f 2 (x) = 0. This means that ϕ(x) ̸ = 0, because otherwise f 1 (x) = 1 would not be achievable. Therefore, ϕ(x) = 1 for all x ∈ S, and as a result similarly H ′ can shatter S, which proves that V C(H) ≤ V C(H ′ ).Finally, since we know that the class of all functions in H is in form of sgn(k -f 1 (x))sgn(f 2 (x) -k) multiplied with a binary function, then we conclude that V C(H) ≤ 4.To prove the rest of the theorem, we need to show that for all choices of k and p the difference of the empirical and the true loss is bounded. In fact, we should find a bound in form ofPr sup k,p E S n ⟨f * k,p (x), ψ 0 (x)⟩ -E µ ⟨f * k,p (x), ψ 0 (x)⟩ ≤ d n ≥ 1 -ϵ.Here, we divide the class X into two subsets G k and H k = X \ G k , where G k is defined in (47) . Now, using the definition of f * k,p (x), we know that within G k , the inner-product ⟨f * k,p (x), ψ 1 (x)⟩ can be rewritten as⟨f * k,p (x), ψ 1 (x)⟩ = ψ 1 (x) (argmax i ℓ k (x) (i)) = d j=1 ψ 1 (x) (j) i̸ =j sgn ℓ k (x) (j) -ℓ k (x) (i) = d j=1 ψ 1 (x) (j) i̸ =j sgn ψ 0 (x) (j) -ψ 0 (x) (0) -k ψ 1 (x) (j) -ψ 1 (x) (i) Φ k j (x). Now, we can condition x on being a member of G k , and therefore the maximum difference between the two empirical and true expectation is asEQUATIONNow, 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 a function h ∈ H over empirical distribution and the true distribution is 2R(H) + 4c ln 4/ϵ n where R(H) is the Rademacher's complexity of the class of function H and c is maximum value that h can take. By definingh(x) := ψ 1 (x) (j) • Φ k j (x),As shown in Lemma K.1, the class of such function has VC dimension of at most 4. Furthermore, multiplying a hypothesis class with a function such as sgn ψ 0 (x) (i) ≥ ψ 0 (x) (j) and sgn ψ 0 (x) (i) > ψ 0 (x) (j) does not increase the VC dimension (See proof of Lemma K.1, and neither does negation. Therefore, in RHS of (66) we can count d number of functions, each with a hypothesis class with the VC dimension of at most 4, and therefore using the early discussions in this proof (58) , fk,1 (x) (i) is within a function class with the VC dimension of at most 8d log(3d). Therefore, similar to (63) Therefore, using ( 63), ( 64), ( 65), ( 67), (68) , and the application Bonferonni's inequality we haveEQUATIONEQUATIONwith probability at least 1 -ϵ. Therefore, by assuming E S n ⟨f * k,p (x), ψ 1 (x)⟩ ≤ α -d n (ϵ), we assure that E µ ⟨f * k,p (x), ψ 1 (x)⟩ ≤ α, with probability at least 1 -ϵ, and this completes the proof.We first introduce three lemmas that are useful in proving this theorem.Lemma L.1. If δ is an ϵ-interior point of the set C = E µ ⟨f (x), ψ 1 (x)⟩ : f ∈ ∆ X d , then δ is (ϵ/2)-interior point of D = E S n ⟨f (x), ψ 1 (x)⟩ : f ∈ ∆ X d with probability 1 -2e -lϵ 2 4 .Proof. The proof of this lemma is a direct application of Hoeffding's inequality. In fact, for ∥ψ 1 ∥ ∞ ≤ C that inequality together with Hölder's inequality imply thatPr E µ ⟨f (x), ψ 1 (x)⟩ -E S n ⟨f (x), ψ 1 (x)⟩ ≥ ϵ/2 ≤ e -nϵ 2 4C 2 .Therefore, if there exists f 1 such that E µ ⟨f 1 (x), ψ 1 (x)⟩ = ϵ, then with probability at least 1-e -nϵ 2 4C 2we haveE S n ⟨f 1 (x), ψ 1 (x)⟩ ∈ [ϵ/2, 3ϵ/2]. Similarly, if f 2 exists such that E µ ⟨f 1 (x), ψ 1 (x)⟩ = -ϵ, then with probability 1 -e -nϵ 2 4C 2 we have E S n ⟨f 2 (x), ψ 1 (x)⟩ ∈ [-3ϵ/2, -ϵ/2].As a result of Bonferroni's inequality, with probability at least 1 -2e -nϵ 2 4C 2 both these events happen, and because of the convexity of the set D we can say that with such probability all values between a 0 ∈ [-3ϵ/2, -ϵ/2] and a 1 ∈ [ϵ/2, 3ϵ/2] are in D too. This, of course at least contains the interval [-ϵ/2, ϵ/2].Lemma L.2. Assume that we have an approximation ψ1 (x) of ψ 1 (x) with the error bounded as∥ ψ1 (x) -ψ 1 (x)∥ ∞ ≤ ϵ. Further let ϵ ′ ∈ R + such that ϵ ′ ≥ ϵ. Now, if for σ ∈ {-ϵ ′ , ϵ ′ } there exists a rule f ∈ ∆ X d such that E µ ⟨f (x), ψ 1 (x)⟩ = δ + σ, then there exists k ∈ R as well as p ∈ [0, 1] such that E µ ⟨ fk,p (x), ψ1 (x)⟩ = δ + ϵ ′ -ϵ 2 .Proof. Firstly, because of Hölder's inequality we know thatE µ ⟨f (x), ψ 1 (x)⟩ -E µ ⟨f (x), ψ1 (x)⟩ ≤ ϵ∥f * k,p (x)∥ 1 = ϵ,for all f ∈ ∆ X d . Therefore, by setting σ = ϵ ′ and σ = -ϵ ′ , we can show that for f 1 ∈ ∆ X d such thatE µ ⟨f 1 (x), ψ 1 (x)⟩⟩ = δ + ϵ ′ , then E µ ⟨f 1 (x), ψ1 (x)⟩ ≥ δ + ϵ ′ -ϵ,and where forf 2 ∈ ∆ X d E µ ⟨f 2 (x), ψ 1 (x)⟩⟩ = δ -ϵ ′ , then E µ ⟨f 2 (x), ψ1 (x)⟩ ≤ δ -ϵ ′ + ϵ.Now, because of step (iii) of the proof of Theorem 4.1, we know that the set of constraints for all rules within ∆ X d is convex. Therefore, since we can achieve two points f 1 , f 2 such that the constraint E µ ⟨f i (x), ψ1 (x)⟩ can achieve two points above δ + ϵ ′ -ϵ and below δ -ϵ ′ + ϵ, then for each c ∈ [δ -ϵ ′ + ϵ, δ + ϵ ′ -ϵ] there exists f ∈ ∆ X d such that E µ ⟨f (x), ψ1 (x)⟩ = c. Now, let c = δ + ϵ ′ -ϵ 2 .In the following, we show that there exists k ∈ R and p ∈ [0, 1] such that further E µ ⟨ fk,p (x), ψ1 (x)⟩ = c. To that end, we first remind that Lemma J.2 shows that E µ ⟨ fk,0 (x), ψ1 (x)⟩ is monotonically nonincreasing in terms of k. We show that for k ∈ R -we have max ψ1(x) -⟨ fk,0 (x), ψ1 (x)⟩ ≤ -2 k . The reason is that if j ∈ argmax l ψ0 (x) -k ψ1 (x) (l) and j ′ ∈ argmax l ψ1 (x) (l), then we have ψ0 (x) -k ψ1 (x) (j) ≥ ψ0 (x) -k ψ1 (x) (j ′ ), which concludes that -k ψ1 (x) (j) -ψ1 (x) (j ′ ) ≥ ψ0 (x) (j ′ ) -ψ0 (x) (j) ≥ -2.Therefore, sinceE µ ⟨argmax ψ1 (x), ψ1 (x)⟩ = max f ∈∆ X d E µ ⟨f (x), ψ1 (x)⟩ ≥ δ + ϵ ′ -ϵ,where the last inequality holds due to the existence of f 1 , then for k ≤ -8/(ϵ ′ -ϵ) we haveE µ ⟨ fk,0 (x), ψ1 (x)⟩ ≥ δ + ϵ ′ -ϵ - 2 -8/(ϵ ′ -ϵ) ≥ δ + 3 ϵ ′ -ϵ 4 .Similarly, if we let k ≥ 8/(ϵ ′ -ϵ) we can prove thatE µ ⟨ fk,0 (x), ψ1 (x)⟩ ≤ δ -ϵ ′ + ϵ + 2l ≤ δ -3 ϵ ′ -ϵ 4 .As a result, the set C = {k : E µ ⟨ fk,0 (x), ψ1 (x)⟩ ≥ c} is non-empty and bounded below by -8 ϵ ′ -ϵ . Therefore, its infimum exists and is also bounded below by -8 ϵ ′ -ϵ . Let us name that infimum k. Now, if E µ ⟨ fk,0,0 (x), ψ1 (x)⟩ is continuous at k = k, then we can show that E µ ⟨ fk ,0 (x), ψ1 (x)⟩ = c. If not, then as shown in step (ii) of the proof of Theorem 4.1, and in particular in (57) , there exists p such that E µ ⟨ fk ,p (x), ψ1 (x)⟩ = c. This completes the proof.Lemma L.3. If ∥ ψ0 -ψ 0 ∥ ∞ ≤ δ 0 and ∥ ψ1 -ψ 1 ∥ ∞ ≤ δ 1 , and for k ∈ [-K, K], and k ′ ≤ k -2(δ0+Kδ1) T for T ∈ R + , then we have E ⟨ fk,0,0 (x) -f * k ′ ,0 (x), ψ 1 (x)⟩ ≤ T.Proof. The proof of this lemma bears similarity to that of Lemma J.2. Here too, we define lk (x) = ψ0 (x) -k ψ1 (x). Next, we haveEQUATIONNext, we need to show that ψ 1 (x) (j 1 ) = ⟨r k ′ ,0 (x), ψ 1 (x)⟩ ≥ ⟨ fk,0,0 (x), ψ 0 (x)⟩ -T = ψ 0 (x) (j 2 ) -T . Assume otherwise, meaning that ψ 1 (x) (j 1 ) < ψ 1 (x) (j 2 ) -T . In this case, we haveEQUATION≤ lk (x) (j 1 ) -(δ 0 + Kδ 1 ) + (δ 0 + Kδ 1 ) = lk (x) (j 1 ), which is a contradiction. Note that (a) holds because of definition of j 2 and ( 71), (b) holds due to approximation assumptions ∥ ψ0 -ψ 0 ∥ ∞ ≤ δ 0 and ∥ ψ1 -ψ 1 ∥ ∞ ≤ δ 1 , (c) holds because of the assumption ψ 1 (x) (j 1 ) < ψ 1 (x) (j 2 ) -T , (d) is followed by the definition of j 1 on maximizing ℓ k ′ (x), and (e) holds because k ≥ k ′ + 2(δ0+Kδ1) T , and (f ) is followed by approximation assumptions.We first formally express Theorem 5.3 as following: Theorem L.4. Assume that (δ -ϵ l , δ + ϵ u ) is a subset of of all achievable constraints E ⟨f (x), ψ 1 (x)⟩ , and that ∥ψ i (x)∥ ∞ ≤ 1 for i = 1, 2. Further, let the size n of validation data be large enough such that d n (δ/3) ≤ ϵ l 2 . Now, if the optimal predictor f * k,0 (x) is (γ, ∆)sensitive around optimal k * for ∆ ≥ δ , and with probability at least 1 -δ, the optimal empirical classifier, as of Algorithm 1 has an objective that is at most D 0 -far from the true optimal objective where D 0 is defined as where K is an upper-bound to the absolute value of k * .In order to prove this theorem, we first define a measure of distance between two rules f 1 , f 2 ∈ ∆ R Using this measure of distance, the difference of objectives between two rules f 1 and f 2 can be written as E ⟨f 1 (x), ψ 0 (x)⟩ -E ⟨f 2 (x), ψ 0 (x)⟩ =D k * (f 1 , f 2 ) + k * E ⟨f 1 (x), ψ 1 (x)⟩ -E ⟨f 2 (x), ψ 1 (x)⟩ . (74)Therefore, if two rules achieve similar constraints, and if D k (f 1 , f 2 ) is small enough, we can prove that the two rules achieve similar objectives too, since k is bounded above by K.In fact, if we let f 1 (x) = f * k,p (x) and f 2 (x) := fk , p, where k and p are optimal solutions as in Theorem 4.2, then due to this optimality, and because E ⟨ fk , p, ψ 1 (x)⟩ ≤ δ with probability at least 1 -ϵ as shown in Theorem 5.1, 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 fk , 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.1. In fact, there we showed that if the empirical constraint E S n ⟨ fk , p, ψ 1 (x)⟩ ≤ δ -d n (π), then using (69) the true expectation is bounded as E µ ⟨ fk , p, ψ 1 (x)⟩ ≤ δ with probability at least 1 -π. However, ( 69) is symmetric in empirical and true constraint, i.e., if we show that E S n ⟨ fk , p, ψ 1 (x)⟩ ≥ δ -d n (π), then we have E µ ⟨ fk , p, ψ 1 (x)⟩ ≥ δ -2d n (π) with probability at least 1 -π.To show E S n ⟨ fk , p, ψ 1 (x)⟩ ≥ δ -d n (π), we follow three steps, (i) because δ is (ϵ l , ϵ u )-interior point of the set of constraints, i.e., (δ -ϵ l , δ + ϵ u ) is a subset of all plausible constraints, then δ -d n (π) is (ϵ l -d n (π), ϵ u + d n (π))-interior point. Now, using Lemma L. there exists k and p such that δ ≥ E ⟨ fk,p (x), ψ 1 (x)⟩ ≥ δ -2d n (π). Now, since we know that E ⟨f 1 (x), ψ 1 (x)⟩ = E ⟨f * k,p (x), ψ 1 (x)⟩ = δ, then we haveEQUATIONwith probability at least 1 -π -2e -nϵ ′2 4 . The above discussion together with (74) and the assumption of boundedness of k shows that the difference of objectives is bounded with a high probability, if we bound D k (f 1 , f 2 ). However, before we proceed with bounding that term, we should derive a relationship between k and k * for the reasons that we see in proving boundedness of D k (f 1 , f 2 ). We have already shown that there exists p ∈ [0, 1] such that δ ≥ E ⟨ fk , p, ψ 1 (x)⟩ ≥ δ -2d l (π).Here, Lemma L.3 shows that for k ′ = k -2(δ0+Kδ1) T we have E ⟨f * k ′ ,0 , ψ 1 (x)⟩ ≥ δ -2d l (π) -T with probability at least 1 -π -2e -nϵ ′2 4 . Moreover, using symmetry in Lemma L.3 and for k ′′ = k + 2(δ0+Kδ1) T we have E ⟨f * k ′′ ,0 (x) -fk (x), ψ1 (x)⟩ ≤ T . Now, since ∥ψ 1 (x) -ψ1 (x)∥ ∞ ≤ δ 0 , using Hölder's inequality we conclude that E ⟨f * k ′′ ,0 (x) -fk (x), ψ1 (x)⟩ ≤ T + 2δ 1 , and consequently E ⟨f * k ′′ ,0 (x), ψ1 (x)⟩ ≤ δ + T + 2δ 0 Now that we have found a lower-bound on constraint of the rule f * k-q (x) for q = 2(δ0+Kδ1), then if we find an upper bound on the constraint of the rule f * k * +e (x) for an e ∈ R + , then we can use monotonicity of the constraint of f * k in terms of k and prove a relationship between k and k * . To that end, we use detection assumption with which we can show thatE ⟨f * k * + 1 C (2dn(π)+T ) 1/γ , ψ 1 (x)⟩ ≤ δ -2d n (π) -T,where we assume that d n (π) ≤ (C∆) γ -T. Now, using previous discussions conclude thatE ⟨f * k * + 1C (2dn(π)+T ) 1/γ , ψ 1 (x)⟩ ≤ E ⟨f * k ′ ,0 , ψ 1 (x)⟩ , with probability at least 1 -π -2e -nϵ ′2 4 . This together with the first part of Lemma J.2 shows that k ′ ≤ k * + 1 C (2d n (π) + T ) 1/γ , or equivalently k ≤ k * + 2(δ0+Kδ1) T + 1 C (2d n (π) + T ) 1/γ with probability at least 1 -π -2e -nϵ ′24 . Since we know that γ is clamped above by 1, and using the inequality (1 + x) a ≤ 1 + ax for a ≥ 1 we can substitute the above inequality with 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 = ψ 0 (x) (i) -k ψ 1 (x) (i)} n+1 i=1 in terms of k with slope m i = -ψ 1 (x) (i) and y-intercept of b i = ψ 0 (x) (i). Therefore, such piecewise-linear function has a Lipschitz factor equal to the maximum slope of the lines, which in here is equal to max i m i = max i ψ 1 (x) (i) ≤ 1. Therefore, t(k) is a 1-Lipschitz function. Therefore, using (77) we can bound D k * (f 1 , f 2 ) as As a result, we can rewrite min ri≥0, D k * (f 1 , f 2 ) ≤ E[t x (|d i | ≥ -ϵ • max i∈[1:n] |d i |,where (a) holds using Hölder's inequality.Next, we know that the optimal deterministic deferral policy should satisfy The rejection here differs from hypothesis rejection and indicates that the classifier rejects making a decision and defers the decision to the human expert.We named this an embedding function because it embeds the constraint or loss of the optimization problem into a vector function.A point is an interior point of a set, if the set contains an open neighborhood of that point.The code is available in https://github.com/AminChrs/PostProcess/.This is as opposed to the experiment in[44] where the human decision is simulated.If we have a probability measure that contains atoms, one can follow the same steps for the first counterexample.Note that in case that wi = 0 the Knapsack problem has a degenerate solution of ri = 1. Hence, we could drop that point and without loss of generality assume that wi is non-zero.(x) . Next, 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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.
questions: 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?

2. If we have rather accurate class probability estimates and expert accuracy, why not use it as the solver of this problem?
limitations: limitations: Please see the weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. The experiments could potentially be expanded further.
questions: 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?

2. What is the motivation for imposing specific constraints in learning to defer? Could this compromise the accuracy of the process?

3. How does the proposed algorithm empirically compare with the baselines on the ACSIncome datasets? Do you think the experiments could be expanded further?

4. It seems that the method could potentially be applicable to other constrained objectives beyond the L2D setting. Could the authors further elaborate on this?

5. Could the authors further comment on the challenges of extending the analysis and algorithm to multiple constraint cases?

6. How are the tolerances chosen during the experiments? Can the assumptions in Theorem 5.3 be verified in practice?
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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}$?

2.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.
questions: 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)?


2.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: limitations: See weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Expert Intervention Budget: 

Liu S, Cao Y, Zhang Q, et al. Mitigating Underfitting in Learning to Defer with Consistent Losses. ICML, 2024.

Narasimhan H, Jitkrittum W, Menon A K, et al. Post-hoc estimators for learning to defer to an exper. NeurIPS, 2022.

Long-Tail Classification:

Narasimhan H, Menon A K, Jitkrittum W, et al. Learning to Reject Meets Long-tail Learning. ICLR, 2024.
questions: 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?
2. There are many studies similar to L2D, such as the dynamic classifier selection literature (DCS). What is the main difference between L2D and DCS?

Cruz R M O, Sabourin R, Cavalcanti G D C. Dynamic classifier selection: Recent advances and perspectives[J]. Information Fusion, 2018, 41: 195-216.
limitations: limitations: N/A.

Comments: title: A Resoponse to Your Concerns
Concerns remain about the experimental component
New Comparative Experiments + Theoretical Equivalence
Response
comment: We thank the reviewer for their response and comments our experimental results. As we have tried to show that via experimental results as well as theoretical results, our method provides the same theoretical post-processing method as of Narasimhan et al. 2022 for the case of human intervention budget. The differences of these methods are reflecting the way that the probabilities are estimated, i.e., the choice of loss function, and the encoding of deferral choice in the network. We have used a softmax loss function, while as mentioned, in our limited time, we implemented Section 4.1 of Narasimhan et al. that uses a form of one-vs-all loss. These two as we see have the difference of order of 0.001, while the standard deviation of accuracies is larger than this amount. As a result, we believe this is an evidence that the two methods lead to a similar result.

Here, we want to reiterate the empirical results of our work:

1- We have obtained the L2D solution under demographic parity for COMPAS dataset and compared to Madras et al. 2018 and Mozannar et al. 2022.

2- We have obtained the L2D solution under equalized odds for ACS dataset.

3- In the rebuttal period, we have implemented our work to Hatespeech dataset and under demographic parity and equality of opportunity constraint.

4- To address the reviewer's concern, we have obtained the optimal solution under multiple constraints of demographic parity+human intervention budget and Type-II error+human intervention budget.

5- To address the reviewer's concern, we have compared our method with Narasimhan et al. 2022 and Liu et al. 2024 for Hatespeech dataset as well as COMPAS dataset.
Thank you to the authors for providing some of the experimental results. However, I’m afraid I still feel that this paper is not very complete. Despite the theoretical section being thorough, there are too many omissions in the experimental part that need to be addressed.

Specifically:

1. There is a lack of separate experiments addressing the various constraints involved in this work.
2. There are no cross-experiments with different constraints (they do not need to be exhaustive).
3. There is a lack of comparative experiments with methods that have already addressed the constraints.


Additionally, I have concerns regarding the experimental results related to the expert intervention budget that were added at the end. Although the method proposed by Narasimhan et al. (2022) cannot be directly compared (as the cost needs to be adjusted), according to the viewpoint in [1], their optimal solutions should be the same. Furthermore, you have employed the same post-processing method; therefore, the experimental results should be fundamentally similar. However, from the aforementioned experiments, it appears that the method presented in this paper performs better.


[1] W. Jitkrittum, G. Neha, A. K. Menon, H. Narasimhan, A. Rawat, and S. Kumar. When Does Confidence-Based Cascade Deferral Suffice? In NeurIPS, 2023
Dear Reviewer,

We further thank you for the suggestion of comparing our unifying methods with other methods in specific cases. In the time we had we could compare our method to the two of the mentioned work, Liu et al 2024, and Narasimhan et al. 2022. for the sanity check. We have indeed simulated the post-hoc formula of (11) in Narasimhan et al. 2022 and the modified equation (9) of Liu et al. with One-vs-All Losses. Since these works are not tailored to handle hard thresholds, we have fitted the parameters for each specific tolerance via validation data in Narasimhan et al. and via re-training in Liu et al. and searching within 1000 values of deferral cost between -1 and 1. The comparison shows a competetive accuracy in our method compared to these baselines. We note here that the high variance of the accuracy in COMPAS dataset is already reported in Mozannar et al. 2023, Figure 3 (b).  

### Hatespeech
| Tolerance | d-GNP Accuracy | d-GNP Constraint | Liu et al. 2024 Accuracy | Liu et al. 2024 Constraint | Narasimhan et al. 2022 Accuracy | Narasimhan et al. 2022 Constraint |
|----|---|---|---|---|---|----|
| 0.05      | **0.890 ± 0.004** | 0.049 ± 0.005 | 0.887 ± 0.004 | 0.043 ± 0.005 | 0.886 ± 0.005 | 0.047 ± 0.006 |
| 0.10      | **0.902 ± 0.005** | 0.099 ± 0.007 | 0.899 ± 0.005 | 0.092 ± 0.005 | 0.898 ± 0.005 | 0.098 ± 0.007 |
| 0.15      | **0.910 ± 0.004** | 0.147 ± 0.011 | 0.908 ± 0.005 | 0.137 ± 0.009 | 0.908 ± 0.005 | 0.148 ± 0.009 |
| 0.20      | **0.916 ± 0.004** | 0.200 ± 0.011 | 0.914 ± 0.005 | 0.186 ± 0.010 | 0.914 ± 0.004 | 0.195 ± 0.012 |
| 0.25      | **0.920 ± 0.004** | 0.244 ± 0.009 | 0.918 ± 0.004 | 0.233 ± 0.013 | 0.917 ± 0.005 | 0.240 ± 0.017 |
| 0.30      | **0.921 ± 0.005** | 0.287 ± 0.016 | 0.920 ± 0.005 | 0.276 ± 0.025 | 0.919 ± 0.005 | 0.283 ± 0.015 |

### COMPAS
| Tolerance | d-GNP Accuracy | d-GNP Constraint | Liu et al. 2024 Accuracy | Liu et al. 2024 Constraint | Narasimhan et al. 2022 Accuracy | Narasimhan et al. 2022 Constraint |
|---|---|---|---|---|---|---|
| 0.015  | 0.646 ± 0.022  | 0.014 ± 0.010 | **0.649 ± 0.031** | 0.003 ± 0.004 | **0.649 ± 0.031**  | 0.016 ± 0.018  |
| 0.075  | 0.647 ± 0.026  | 0.042 ± 0.033 | 0.648 ± 0.031 | 0.030 ± 0.022 | **0.650 ± 0.031**  | 0.053 ± 0.032  |
| 0.135  | 0.649 ± 0.026  | 0.072 ± 0.050 | **0.651 ± 0.026**  | 0.065 ± 0.040 | 0.649 ± 0.031  | 0.082 ± 0.048   |
| 0.195  | **0.656 ± 0.023** | 0.111 ± 0.074  | 0.654 ± 0.027 | 0.079 ± 0.054  | 0.652 ± 0.033 | 0.132 ± 0.069 |
| 0.255  | **0.656 ± 0.029** | 0.122 ± 0.085  | 0.653 ± 0.027  | 0.108 ± 0.085  | 0.655 ± 0.033 | 0.165 ± 0.095  |

We further discuss the theoretical equivalence between our method and other methods that tackle human intervention budget and long-tail classification by which we conclude that the closeness of the accuracies to these baselines are not surprising. 

  For human intervention budget, since using Table 1 we know that the embedding functions are as
  $$\psi_0(x)=[\Pr(Y=0|X=x), \ldots, \Pr(Y=L|X=x), \Pr(Y=M|X=x)],$$
  and
  $$\psi_1(x)=[0, \ldots, 0, 1],$$  therefore, the optimal predictor using Theorem 4.1 and the discussion after (4) is equal to
  $$h^*(x)=\arg\max_{i\in [1:L]} \psi_0(x)-k\psi_1(x) $$,
  and $r^*(x) = 1$ if $L+1=\arg\max_{i\in [1:L+1]} \psi_0(x)-k\psi_1(x)$. Therefore, using the definitions of embedding functions, we have
  $$h^*(x)= \arg\max_{1:L} [\Pr(Y=1|X=x), \ldots, \Pr(Y=L|X=x)],$$ and $r(x)=1$ if $\Pr(Y=M|X=x)-k>\max \{\Pr(Y=1|X=x), \ldots, \Pr(Y=L|X=x)\}$. This is equivalent to what is proposed in (11) in Narasimhan et al. 2022.

  For the long-tail classification problem using Table 1, we have 
  $$\psi_0(x)= \Big[\frac{\Pr(Y=1|X=x)}{\alpha_{i_1}\Pr(Y\in G_{\alpha_{i_1}})}, \ldots, \frac{\Pr(Y=L|X=x)}{\alpha_{i_L}\Pr(Y\in G_{\alpha_{i_L}})}, 0\Big]$$
  and 
  $$ \psi_t(x) = \frac{\Pr(Y\in G_t|X=x)}{\Pr(Y\in G_t)}[1, \ldots, 1, 0] - \frac{\alpha_t}{K}$$
  as embedding functions, where $i_j$ is the index of the group $G_{i_j}$ to which the label $j$ belongs. Now, since the first $L$ components of all $\psi_t$s are equal to each other, we have
  $$h^*(x)=\arg\max_{i\in [1:L]} \psi_0(x) - \sum_{t=1}^K k_t \psi_t(x) = \arg\max_{i\in [1:L]} \psi_0(x) = \arg\max \Big[\frac{\Pr(Y=1|X=x)}{\alpha_{i_1}\Pr(Y\in G_{\alpha_{i_1}})}, \ldots, \frac{\Pr(Y=L|X=x)}{\alpha_{i_L}\Pr(Y\in G_{\alpha_{i_L}})}\Big].$$
 Furthermore, the tightness condition $\mathbb{E}\big[\langle \psi_t(x), f^*(x)\rangle\big]=0$ concludes that $\alpha_{i_j}\Pr(Y\in G_{\alpha_{i_j}}) = \alpha^*_{j}$ where $\alpha^*_{j}$ defined in (8) of Narasimhan et al. 2024. These two conclude in the optimal classifier (8) of Narasimhan et al. 2024.
 Similarly, we can show that the optimal deferral strategy using $d$-GNP is
 $r(x)=1$ if $\sum_{t}\frac{k_t \Pr(Y\in G_t|X=x)}{\Pr(Y\in G_t)}>\max\Big[\frac{\Pr(Y=1|X=x)}{\alpha_{1}^*}, \ldots, \frac{\Pr(Y=L|X=x)}{\alpha_{L}^*}\Big]$ which is a similar rule to that of (8) in Narasimhan et al. by setting $\mu^*\_t=1-k_t \alpha_{i_t}$.
Thank you for your detailed response. I will keep my score as is.
Thank you for your response. Your discussions on the motivation of this work and the hardness analyses have solved my concerns. I’ll keep my decision of acceptance.
We first thank the reviewer for their clarifications and their response. Here, we mention a few notes.

Q1: We are glad that the reviewer agrees with us on our choice of surrogate functions. We further agree with the reviewer that linearly combining the scores might propagate the error, in a controlled manner, and in the value of objective and not the constraints. This is precisely what we have discussed after Theorem 5.1 regarding the constraint generalization.
 There, we have discussed that for a given error in $\ell_{\infty}$ norm of the scores, the constraints can deter at most for that error, plus the  sample complexity term. Furthermore, in the error upper-bound (10) that is provided in **Theorem 5.3**, we observe that given the linear combination coefficient being bounded by $K$, and given the sensitivity factor being bounded away from $0$, **the objective cannot be far from the true objective, as long as score errors $\delta_0$ and $\delta_1$ are small enough**.  We note that, when the constraint is well within the feasibility set, the value $K$ is more tightly upper-bounded. Furthermore,  as we discussed it in the response to Q6 of Reviewer 7rh1, and as we have shown as an example, in Figure (f) and (g) of the submitted PDF, the constraints that lie within the feasibility set improve the sensitivity factor, thereby reducing the risk of error propagation.

 ## Weaknesses

We appreciate the reviewer's clarification of their comments. It is important to emphasize that our work does not aim to compete with other constrained L2D optimal methods but rather to unify these methods within a single framework. Our method should indeed provide a reasonable solution for simple constraints, and improve the empirical methods by obtaining the true optimal solution for cases in which **the true optimal is not known in the literature**, such as **L2D with fairness criteria (demographic parity, equalized odds, and equality of opportunity), or a combination of a set of constraints**. These claims are supported by the experiments within the manuscript and the rebuttal. However, we do not expect that our method outperforms methods that already achieve or approximate the true optimality, such as those dealing with expert intervention budgets or long-tail classification.

We will further attempt to run the additional experiments suggested by the reviewer during the remaining discussion period. However, given the time constraints and the incompleteness of the reviewer's initial comments, it might not be feasible to complete them within this period.
Dear Reviewer,

Thank you for your response and for raising the score. We are glad that we could address your concerns. Regarding the notation issues, we assure you that we will carefully proofread the next version of the manuscript to eliminate any typos.
Thank you for your elaborated response to my review. Please allow me a response to your response.

add Q1/A1: I know that addressing the probability calibration issue caused by overfitting is challenging, so the author's plug-in method relies on excellent surrogate loss functions. However, we need to point out that in previous surrogate loss function, only comparisons between probabilities are required (e.g., comparisons may be accurate, but values may not be accurate, such as Mozannar et al. 2020), rather than direct use. In contrast, the author's method requires direct utilization of estimated probabilities that may be inaccurate for multiple operations, which may amplify errors. I know that calibrating probabilities is not the focus of this study, but I believe this is a potential risk of the plug-in method that warrants discussion.

add Weaknesses: I apologize for not accurately expressing my confusion earlier. My main concern is that the authors claim their framework can solve various constraint problems, but in the experiment section, they don't compare their work with previous works that have already solved some of these constraint problems (such as expert intervention budget and long-tail classification). I think such comparative experiments are very important.

In my opinion, the lack of comparative experiments is the main drawback of the work.
Thank you for your response. It addresses some of my concerns and I have raised the score. However, I must emphasize that the typos and notation issues significantly hinder the understanding of the work. In my view, a high-quality paper should have minimal typos and consistent notations to ensure clarity and readability.