mattbrown

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

Mohammad-Amin Charusaie
Max Planck Institute for Intelligent Systems
Tuebingen, 72076
<EMAIL_ADDRESS>
&Samira Samadi
Max Planck Institute for Intelligent Systems
Tuebingen, 72076
<EMAIL_ADDRESS>

###### 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 and ACSIncome datasets. Our algorithm shows improvements in terms
of constraint violation over a set of baselines.

##  1 Introduction

Machine learning algorithms are increasingly used in diverse fields, including
critical applications, such as medical diagnostics [68] and predicting optimal
prognostics [60]. 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 [32], or playing a supportive role by taking
over the tasks on which machine learning is uncertain [36, 57, 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 [57, 47]. 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
[43], algorithmic biases [11], or human expert intervention [54], 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 [41], a general solution to such class of problems, besides
specific examples [23, 54, 48, 49], 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 [16] while optimizing accuracy. Recent advances in the
algorithmic fairness literature have suggested the superiority of _post-
processing_ methodology for tackling this multi-objective problem [69, 12, 18,
72]. 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 [48, 49], which is in line with
classical results such as Chow’s rule [14] 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 $\\{\Psi_{0},\ldots,\Psi_{m}\\}$ that are functions of
the system outcome $\hat{Y}$, the target label $Y$, and the input $X$. The
goal is to optimize the average value of $\Psi_{0}$ over data distribution
while keeping the average value of the rest of performance measures
$\Psi_{1},\ldots,\Psi_{m}$ for all inputs under control. As an example, in
binary classification, $\Psi_{0}$ can be the $0-1$ deferral loss function,
while $\Psi_{1}$ can be the difference between positive prediction rates of
$\hat{Y}$ for all instances of $X$ that belong to demographic group $A=0$ or
$A=1$. The solution for which we aim optimizes the accuracy while assuring
that the demographic parity measure between the two groups is bounded by a
tolerance value $\delta_{1}\in[0,1]$.

To provide the optimal solution, we move beyond staged learning [10]
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 [59] the obtained
deferral system is not necessarily fair (see Appendix A), and in fact
abstention systems can deter the algorithmic biases [33]. Secondly, the
feasibility of constraints is not guaranteed under staged learning methodology
[70], e.g., there can be cases in which achieving a purely fair solution is
impossible, while this occurs neither in vanilla classification [18] 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 [52]. 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:

Figure 1: Diagram of applying $d$-GNP to solve multi-objective L2D problem via
Algorithm 1. The role of randomness is neglected due to simplicity of
presentation.

  * •

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(\sqrt{\log n/n},\sqrt{\log(1/\epsilon)/n},\epsilon^{\prime})$ and $O(({\log
n/n})^{1/2\gamma},({\log(1/\epsilon)/n})^{1/2\gamma},\epsilon^{\prime})$,
respectively, with probability at least $1-\epsilon$ where $n$ is the size of
the set using which we fine-tune the algorithm, $\epsilon^{\prime}$ measures
the accuracy of learned post-processing scores, and $\gamma$ 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
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.

##  2 Related Works

Human and ML’s collaboration in decision-making has been demonstrated to
enhance the accuracy of final decisions compared to predictions that are made
solely by humans or ML [34, 65]. 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 [7, 47, 10, 48, 8, 40, 45, 42]. The multi-objective classification with
abstention problems is studied for specific objectives in [41, 54, 45] via in-
processing methods. The application of Neyman-Pearson lemma for learning
problems with fairness criteria is recently introduced in [71].

We refer the reader to Appendix B for further discussion on related works.

##  3 Problem Setting

Assume that we are given input features $x_{i}\in{\cal X}$ , corresponding
labels $y_{i}\in{\cal Y}=\\{1,\ldots,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\sim\mu=\mu_{XYM}$. 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 $\ell_{AI}(y,h(x))$ for the classifier prediction $h(x)$, and a loss
function $\ell_{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)\in\\{0,1\\}$ be the rejection function111The rejection here differs from
hypothesis rejection and indicates that the classifier rejects making a
decision and defers the decision to the human expert., 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

$\displaystyle\ell_{\mathrm{def}}(y,m,h(x),r(x))$
$\displaystyle=r(x)\ell_{H}(y,m)+(1-r(x))\ell_{AI}(y,h(x)).$

Therefore, we can find the average deferral loss on distribution $\mu$ as

$\displaystyle
L_{\mathrm{def}}^{\mu}(h,r):=\mathbb{E}_{X,Y,M\sim\mu}\big{[}\ell_{\mathrm{def}}(Y,M,h(X),r(X))\big{]}.$
(1)

We aim to find a randomized algorithm ${\cal A}$ that defines a probability
distribution $\mu_{{\cal A}}$ on ${\cal H}\times{\cal R}$ that solves the
optimization problem

$\displaystyle\mu_{{\cal A}}\in\mathop{\rm argmin}\limits_{\mu_{\cal
A}}\mathbb{E}_{(h,r)\sim{\cal A}}\big{[}L_{\mathrm{def}}^{\mu}(h,r)\big{]},$
$\displaystyle s.t.~{}~{}~{}$
$\displaystyle\mathbb{E}_{X,Y,M\sim\mu}\mathbb{E}_{(h,r)\sim\mu_{{\cal
A}}}\big{[}\Psi_{i}\big{(}X,Y,M,h(X),r(X)\big{)}\big{]}\leq\delta_{i}$ (2)

where $\Psi_{i}$ is a performance measure that induces the desired constraint
in our optimization problem. We assume that $\Psi_{i}$, similar to
$\ell_{\mathrm{def}}$, is an _outcome-dependent_ function, i.e., if the
deferral occurs, the outcome of the classifier does not change $\Psi_{i}$, and
otherwise, if deferral does not occur, the human decision does not change
$\Psi_{i}$. In other words, the value of the constraints can only be a
function of input feature $x$ and of the deferral system prediction
$\hat{Y}=r(x)M+\big{(}1-r(x)\big{)}h(x)$. Here, $\hat{Y}$ is the expert
decision when deferral occurs, and is the classifier decision otherwise.

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):=\tfrac{\mathbb{I}_{A=1}}{Pr(Y=y,A=1)}-\tfrac{\mathbb{I}_{A=0}}{Pr(Y=y,A=0)}$. Name | Embedding Function $\psi_{i}(x)$
---|---
Accuracy | $[\mathbb{P}(Y=0|x),\ldots,\mathbb{P}(Y=n|x),\mathbb{P}(Y=M|x)]$
Expert Intervention Budget [54] | $[{0,\ldots,0},1]$
OOD Detection [50] | $[0,\ldots,0,\tfrac{f_{X}^{\mathrm{out}}(x)}{f_{X}^{\mathrm{in}}(x)}]$
| $-\Big{[}\sum_{i=1}^{K}\frac{\mathbb{P}(Y\neq 1,Y\in
G_{i}|X=x)}{\alpha_{i}\mathbb{P}(Y\in
G_{i})},\ldots,\sum_{i=1}^{K}\frac{\mathbb{P}(Y\neq l,Y\in
G_{i}|X=x)}{\alpha_{i}\mathbb{P}(Y\in G_{i})},0\Big{]}$
Long-Tail Classification [49] | and
| $\frac{\mathbb{P}(Y\in G_{i}|X=x)}{\mathbb{P}(Y\in
G_{i})}\Big{[}1,\ldots,1,0\Big{]}-\frac{\alpha_{i}}{K}$
Bound on Type-$K$ Error [66] | $\frac{1}{\mathbb{P}(Y=k)}[1,\ldots,\underbrace{0}_{k\text{-th}},\ldots,1,\mathbb{P}(M\neq k,Y=k|x)]$
Demographic Parity [25] | $(\tfrac{\mathbb{I}_{A=1}}{Pr(A=1)}-\tfrac{\mathbb{I}_{A=0}}{Pr(A=0)})[0,1,\mathbb{P}(M=1|x)]$
Equality of Opportunity [31] | $t(A,1)[0,\mathbb{P}(Y=1|x),\mathbb{P}(M=1,Y=1|x)]$
| $t(A,1)[0,\mathbb{P}(Y=1|x),\mathbb{P}(M=1,Y=1|x)]$
Equalized Odds [31] | and
| $t(A,0)[\mathbb{P}(Y=0|x),0,\mathbb{P}(M=0,Y=0|x)]$

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
$\mathbb{P}\big{(}r(X)=1\big{)}\leq\delta$, limits the rejection function to
defer up to $\delta$ proportion of the instance, (2) demographic parity that
is formulated as $\big{|}P(\hat{Y}=1|A=0)-P(\hat{Y}=1|A=0)\big{|}\leq\delta$,
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
$|Pr(\hat{Y}=1|A=1,Y=1)-Pr(\hat{Y}|A=0,Y=1)|\leq\delta$ 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}\big{|}Pr(\hat{Y}=1|A=1,Y=y)-Pr(\hat{Y}=1|A=0,Y=y)\big{|}\leq\delta$,
(5) out-of-distribution (OOD) detection that is written as
$\mathbb{P}_{\mathrm{out}}(r(X)=0)\leq\delta$ 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 [50] is equivalent to minimizing
$\sum_{i=1}^{K}\frac{1}{\alpha_{i}}\mathbb{P}(Y\neq h(X),r(X)=0|Y\in G_{i})$
when the feasible set is $\mathbb{P}(r(X)=0,Y\in G_{i})=\frac{\alpha_{i}}{K}$,
and where $\\{G_{i}\\}_{i=1}^{K}$ 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 $\mathbb{P}(\hat{Y}\neq
k|Y=k)\leq\delta$.

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 of

$\displaystyle f^{*}=[f_{1}^{*},\ldots,f_{d}^{*}]\in\mathop{\rm
argmax}\limits_{f\in\Delta_{d}^{{\cal X}}}\mathbb{E}\big{[}\langle
f(X),\psi_{0}(X)\rangle\big{]},~{}~{}~{}~{}\text{s.t.
}\mathbb{E}\big{[}\langle
f(x),\psi_{i}(x)\rangle\big{]}\leq\delta_{i},i\in[1:m]$ (3)

where $\Delta_{d}$ is a simplex of $d$ dimensions, $d=L+1$, and
$\psi_{i}:{\cal X}\to\mathbb{R}^{d}$ is defined as

$\displaystyle\psi_{i}(x):=\mathbb{E}_{Y,M|X=x}\bigg{[}\Big{[}\Psi_{i}(x,Y,M,1,0),\ldots,\Psi_{i}(x,Y,M,l,0),\Psi_{i}(x,Y,M,0,1)\big{]}\Big{]}\bigg{]}$
(4)

that we name the _embedding function_ 222We named this an embedding function
because it embeds the constraint or loss of the optimization problem into a
vector function. corresponding to the performance measure $\Psi_{i}$ for
$i\in[0:m]$, where for simplifying the notation we define
$\Psi_{0}\equiv-\ell_{\mathrm{def}}$. Furthermore, the optimal algorithm is
obtained by predicting $h(x)=i$ with normalized probability of
${f_{i}^{*}(x)}/{\sum_{j=1}^{d-1}f_{j}^{*}(x)}$, where
$\sum_{j=1}^{d-1}f_{j}^{*}(x)\neq 0$, and rejecting $r(x)=1$ with probability
$f_{d}^{*}(x)$. In case of $\sum_{j=1}^{d-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 [55, 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},\ldots,x_{n}$, each of which have probability of
$\mathbb{P}(X=x_{i})=p_{i}$, and if we set
$\psi_{1}(x_{i})=[0,\frac{w_{i}}{p_{i}}]$ and
$\psi_{0}(x_{i})=[0,\frac{v_{i}}{p_{i}}]$ for $v_{i},w_{i}\in\mathbb{R}^{+}$,
then (3) reduces in $\mathop{\rm argmax}\limits\sum_{i}f^{1}(x_{i})v_{i}$
subjected to ${f^{1}:{\cal X}\to\\{0,1\\}}$ and
$\sum_{i}f^{1}(x_{i})w_{i}\leq\delta_{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 $\psi_{0}$ and $\psi_{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
$\mathcal{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 [46, Theorem 1] and [20, 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.

##  4 $d$-dimensional Generalization of Neyman-Pearson Lemma

The idea behind minimizing an expected error while keeping another expected
error bounded is naturally related to the problem that is designed by Neyman
and Pearson [52]. 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)\in{[0,1]}$ that rejects the null hypothesis
when $T(x)=1$, they solved the problem

$\displaystyle\max_{T\in{[0,1]^{{\cal X}}}}\mathbb{E}_{X\sim
g_{1}}\big{[}T(X)\big{]},~{}~{}~{}~{}s.t.~{}~{}\mathbb{E}_{X\sim
g_{0}}\big{[}T(X)\big{]}\leq\alpha.$ (5)

They concluded that thresholding the likelihood ratio is a solution to the
above problem. Formally, they show that all optimal hypothesis tests take the
value $T(x)=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 $\alpha$.

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},\ldots,H_{d-1}$, each of which corresponding to $X$ being
drawn from the density function $g_{i}(x)$ for $i\in\\{0,\ldots,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 $\ell_{i}(x)$. Assume that we aim to find a test $f:{\cal
X}\to\Delta_{d}$ that for each input $x\in{\cal 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 $\mathop{\rm
argmax}\limits_{f\in\Delta_{d}^{{\cal X}}}\sum_{i=0}^{d-1}\mathbb{E}_{X\sim
g_{i}}\Big{[}f^{i}(x)r_{i}(x)\Big{]}$ subjected to
$\sum_{i=0}^{d-1}\mathbb{E}_{X\sim
g_{i}}\Big{[}(1-f^{i}(x))\ell_{i}(x)\Big{]}\leq\delta_{1}$ which in turns is
equivalent to

$\displaystyle\mathop{\rm argmax}\limits_{f\in\Delta_{d}^{{\cal
X}}}\mathbb{E}_{X\sim
g_{0}}\Big{[}\sum_{i=0}^{d-1}f^{i}(x)r_{i}(x)\frac{g_{i}(x)}{g_{0}(x)}\Big{]}~{}~{}~{}~{}~{}~{}\text{s.t.
}\mathbb{E}_{X\sim g_{0}}\Big{[}\sum_{i=0}^{d-1}f^{i}(x)\sum_{j\neq
i}\ell_{j}(x)\frac{g_{j}(x)}{g_{0}(x)}\Big{]}\leq\delta_{1}.$ (6)

This problem can be seen as instance of (3), when we set
$\psi_{0}(x)=[r_{0}(x),\ldots,r_{d-1}(x)\frac{g_{d-1}(x)}{g_{0}(x)}]$ and
$\psi_{1}(x)=\big{[}\sum_{j\neq
0}\ell_{j}(x)\tfrac{g_{j}(x)}{g_{0}(x)},\ldots,\sum_{j\neq
d-1}\ell_{j}(x)\tfrac{g_{j}(x)}{g_{0}(x)}\big{]}$. Similarly, we can show that
for all $\psi_{0}(x),\psi_{1}(x)$ in (3) there exists a set of densities
$g_{1}(x),\ldots,g_{d-1}(x)$ and rewards and losses such that (6) and (3) are
equivalent. This can be done by setting $g_{i}\equiv g_{0}$ and noting that
the mapping from $\ell_{i}$s and $r_{i}$s into $\psi_{0}$ and $\psi_{2}$ is
invertible.

The formulation of (3) can be seen as an extension of the setting in [66] 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 $\mathop{\rm argmax}\limits$ function that
helps us articulate the optimal predictor. In fact, we define

$\displaystyle{\cal
T}_{d}=\big{\\{}\tau:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\Delta_{d}\,|\,\sum_{i:x_{i}=\max\\{x_{1},\ldots,x_{d}\\}}\big{(}\tau(\mathbf{x}_{1}^{d},\cdot)\big{)}(i)=1\big{\\}}$
(7)

that is a set of functions that result in one-hot encoded $\mathop{\rm
argmax}\limits$ 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 $\psi_{i}$ where $i\in[0,m]$, assume that
$(\delta_{1},\ldots,\delta_{m})$ is an interior point333A point is an interior
point of a set, if the set contains an open neighborhood of that point. of the
set ${\cal F}=\Big{\\{}\big{(}\mathbb{E}[\langle
r(x),\psi_{1}(x)\rangle],\ldots,\mathbb{E}[\langle
r(x),\psi_{m}(x)\rangle]\big{)}:f\in\Delta_{d}^{{\cal X}}\Big{\\}}$. Then,
there is a set of fixed values $k_{1},\ldots,k_{m}$ and $\tau\in{\cal T}_{d}$
such that the predictor

$\displaystyle
f^{*}(x)=\tau\big{(}\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x),x\big{)},$ (8)

obtains the optimal solution of $\sup_{f\in\Delta_{d}^{{\cal
X}}}\mathbb{E}\big{[}\langle f(x),\psi_{0}(x)\rangle\big{]}$, subjected to the
constraints being achieved tightly, i.e., when for $i\in[1:m]$ we have
$\mathbb{E}\big{[}\langle f(x),\psi_{i}(x)\rangle\big{]}=\delta_{i}$. If
$k_{1},\ldots,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 ${\cal 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 $\delta$, we can set
$\psi_{0}(x)=\big{[}\mathbb{P}(Y=0|x),\mathbb{P}(Y=1|x),\mathbb{P}(Y=M|x)\big{]}$
and $\psi_{1}(x)=s(A)\big{[}0,1,\mathbb{P}(M=1|x)\big{]}$, using Table 1,
where
$s(A):=\big{(}\tfrac{\mathbb{I}_{A=1}}{Pr(A=1)}-\tfrac{\mathbb{I}_{A=0}}{Pr(A=0)}\big{)}$.
Therefore, $d$-GNP, together with the discussion after (4) shows that the
optimal classifier and rejection function are obtained as

$\displaystyle
h(x)=\left\\{\begin{array}[]{cc}1&\mathbb{P}(Y=1|x)>\frac{1+ks(A)}{2}\\\
0&\mathbb{P}(Y=1|x)<\frac{1+ks(A)}{2}\end{array}\right.,$

and

$\displaystyle
r(x)=\left\\{\begin{array}[]{cc}1&\mathbb{P}(Y=M|x)-ks(A)\mathbb{P}(M=1|x)>\lambda(A,x)\\\
0&\mathbb{P}(Y=M|x)-ks(A)\mathbb{P}(M=1|x)<\lambda(A,x)\end{array}\right.,$

for a fixed value $k\in\mathbb{R}$, and where
$\lambda(A,x):=\max\\{\mathbb{P}(Y=0|x),\mathbb{P}(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 [12, 18]. However, the rejection function does
not merely threshold the scores for different groups, but adds an input-
dependent threshold $ks(A)\mathbb{P}(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
$\psi_{0}(x)=\big{[}\mathbb{P}(Y=0|x),\mathbb{P}(Y=1|x),\mathbb{P}(Y=M|x)\big{]}$
and
$\psi_{1}(x)=t(A,1)\big{[}0,\mathbb{P}(Y=1|x),\mathbb{P}(M=1,Y=1|x)\big{]}$,
respectively. Therefore, the characterization of optimal classifier and
rejection function using $d$-GNP results in

$\displaystyle
h(x)=\left\\{\begin{array}[]{cc}1&\big{(}2-kt(A,1)\big{)}\mathbb{P}(Y=1|x)>1\\\
0&\big{(}2-kt(A,1)\big{)}\mathbb{P}(Y=1|x)<1\end{array}\right.,$

and

$\displaystyle
r(x)=\left\\{\begin{array}[]{cc}1&\mathbb{P}(Y=M|x)\big{(}1-kt(A,1)\mathbb{P}(M=1|Y=M,x)\big{)}>\nu(A,x)\\\
0&\mathbb{P}(Y=M|x)\big{(}1-kt(A,1)\mathbb{P}(M=1|Y=M,x)\big{)}<\nu(A,x)\end{array}\right.,$

for $k\in\mathbb{R}$ and where
$\nu(A,x):=\max\\{\mathbb{P}(Y=0|x),\big{(}1-kt(A,1)\big{)}\mathbb{P}(Y=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
$\big{|}\mathbb{P}(\hat{Y}=0|A=0)-\mathbb{P}(\hat{Y}=0|A=1)\big{|}\leq\delta$
or equality of opportunity
$\big{|}\mathbb{P}(\hat{Y}=0|Y=0,A=0)-\mathbb{P}(\hat{Y}=0|Y=0,A=1)\big{|}\leq\delta$
on Class $0$, then we can follow similar steps as in Appendix D to find the
embedding functions as

$\displaystyle\psi_{\mathrm{DP}}=s(A)\big{[}1,0,\ldots,0\big{]},$

and

$\displaystyle\psi_{\mathrm{EO}}=t(A,0)\big{[}\mathbb{P}(Y=0|x),0,\ldots,0\big{]}.$

As a result, since the accuracy embedding function is
$\psi_{0}(x)=\big{[}\mathbb{P}(Y=0|x),\ldots,\mathbb{P}(Y=L|x)\big{]}$, then,
by neglecting the effect of randomness, the optimal classifier under such
constraints are as

$\displaystyle h_{\mathrm{DP}}(x)=\mathop{\rm
argmax}\limits\big{\\{}\mathbb{P}(Y=0|x)-ks(A),\mathbb{P}(Y=1|x),\ldots,\mathbb{P}(Y=L|x)\big{\\}},$
(9)

and

$\displaystyle h_{\mathrm{EO}}(x)=\mathop{\rm
argmax}\limits\big{\\{}\mathbb{P}(Y=0|x)\big{(}1-kt(A,0)\big{)},\mathbb{P}(Y=1|x),\ldots,\mathbb{P}(Y=L|x)\big{\\}}.$
(10)

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},\ldots,k_{m}$, and further
does not give us the form of the optimal solution when
$\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{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)=\tau\big{(}\psi_{0}(x)-k\psi_{1}(x),x\big{)}$
where $\tau$ is a member of ${\cal T}_{d}$ such that if there is a non-
singleton set ${\cal I}$ of maximizers of a vector
$\mathbf{y}\in\mathbb{R}^{d}$, then we have
$\big{(}\tau(\mathbf{y},x)\big{)}(i)=p$ and
$\big{(}\tau(\mathbf{y},x)\big{)}(j)=1-p$, where $i$ and $j$ are the first
indices in ${\cal I}$ that minimizes $\psi_{1}(x)$, and maximizes
$\psi_{0}(x)$, respectively.

In this case, $k$ is a member of the set ${\cal
K}=\Big{\\{}t:\,\delta\in\big{[}\lim_{\tau\uparrow
t}C(\tau),C(t)\big{]}\Big{\\}}$ where $C(t)=\mathbb{E}\big{[}\langle
f^{*}_{t,0}(x),\psi_{0}(x)\rangle\big{]}$ is the expected constraint of the
predictor $f^{*}_{t,0}$. Moreover, $p=\frac{C(k)-c}{C(k)-\lim_{\tau\uparrow
t^{-}}C(\tau)}$, if $C(\cdot)$ is lower-discontinuous at $k$, and otherwise
$p=0$.

This theorem reduces the complexity of finding $k_{i}$s from the complexity of
an exhaustive search to the complexity of finding the root of the monotone
function $C(t)-\delta$ (see Lemma I.2 for the proof of monotonicity), and
further finds the randomized response for the cases that Theorem 4.1 leaves
undetermined.

Before we proceed to the designed algorithm based on $d$-GNP, we should
address two issues. Firstly, during the course of optimization, it can occur
that the solution of Theorem 4.1 does not compute non-negative values $k_{i}$
for an $i\in[1:m]$. This means that the constraints are not achieved tightly
in the final solution of (3). Therefore, we are able to achieve the optimal
solution with the constraint $\delta^{\prime}_{i}<\delta_{i}$. Now, if we can
assure that the constraint tuples are still inner points of ${\cal F}$ when we
substitute $\delta_{i}$ by $\delta^{\prime}_{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 $\delta$ and
$-\delta$. However, since both bounds cannot hold tightly and simultaneously
unless the tolerance is $\delta=0$, then we can use only one of the
constraints in turn and apply the result of Theorem 4.2 and check whether the
constraint is active in the final solution.

In the next section, we design an algorithm based on these results and show
its generalization to the unseen data.

##  5 Empirical $d$-GNP and its Statistical Generalization

In previous sections, we obtained the optimal solution to the constrained
optimization problem (3) using $d$-GNP. In this section, we propose a plug-in
method in Algorithm 1 and tackle the generalization error of the objective and
constraints based on this solution. The results in this section, which are
extensions of the generalization results for Neyman-Pearson [1, 67], address
single constraint setting, and the extension to the multiple constraint case
is left for future research.

We start this section by 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.

Algorithm 1 Finding Optimal Classifier and Rejection Function

1:The formulation of $\ell_{\mathrm{def}}(\cdot,\cdot,\cdot)$ and
$\\{\Psi_{i}(\cdot,\cdot,\cdot)\\}_{i=1}^{m}$, and the datasets ${\cal
D}_{\mathrm{train}}=\\{(x^{i},a^{i},m^{i},y^{i})\\}_{i=1}^{n_{\text{train}}}$,
${\cal
D}_{\mathrm{val}}=\\{(x^{i},a^{i},m^{i},y^{i})\\}_{i=n_{\text{train}}+1}^{n_{\text{train}}+n_{\text{val}}}$,
and tolerances $\\{\delta_{i}\\}_{i=1}^{m}$

2:Optimal deferral rule $r^{*}(x)$ and classifier $h^{*}(x)$

3:Parameters: $\epsilon=1e-8$

4:procedure ConstrainedDefer($\ell_{\mathrm{def}}$,
$\\{\Psi_{i}\\}_{i=1}^{m}$, ${\cal D}_{\mathrm{train}}$, ${\cal
D}_{\mathrm{val}}$)

5: Obtain closed-form of $\\{\psi_{i}(x)\\}_{i=0}^{m}$ using
$\ell_{\mathrm{def}}$ and $\Psi_{i}$s via (4) and in terms of the scores as in
Table 1

6: Estimate the scores in Table 1 using classification/regression methods on
${\cal D}_{\text{train}}$

7: Find estimate $\\{\hat{\psi}_{i}\\}_{i=0}^{m}$ using estimated scores in
previous step and closed-form of Step 3

8: if $m=2$ then

9: Define routine
$\hat{f}_{k,p}(x):=\tau\big{(}\hat{\psi}_{0}(x)-k\hat{\psi}_{1}(x),x\big{)}$
for $\tau$ in Theorem 4.2

10: Define routine $\hat{C}(t):=\widehat{\mathbb{E}}_{{\cal
D}_{\mathrm{val}}}\Big{[}\langle\hat{f}_{k,0}(x_{i}),\hat{\psi}_{1}(x_{i})\rangle\Big{]}$

11: Find $\hat{k}=\min k$ over the feasibility set $\hat{C}(t)\leq\delta_{1}$

12: if $\hat{k}=\emptyset$ then

13: Return ‘Not Feasible’

14: else

15: if $\hat{C}(\hat{k}-\epsilon)-\hat{C}(k^{*})\leq 1e-3$ then

16: $\hat{p}\leftarrow 0$

17: else

18:
$\hat{p}\leftarrow\frac{\delta-\hat{C}(\hat{k})}{\hat{C}(\hat{k}-\epsilon)-\hat{C}(\hat{k})}$

19: end if

20: end if

21: $s(x):=\hat{f}_{\hat{k},\hat{p}}(x)$

22: else

23: Optimize (3) for ${\cal D}_{\mathrm{val}}$ and for
$f(x)=\tau(\hat{\psi}_{0}(x)-\sum_{i=1}^{m}\hat{\psi}_{i}(x),x)$ for $\tau$ as
in Theorem 4.1 and via exhaustive search over $\\{k_{1},\ldots,k_{m}\\}$ and
randomizations of $\tau$ and find $s(x):=\hat{f}(x)$

24: end if

25: $h^{*}(x):=\mathop{\rm argmax}\limits_{i\in[0:L-1]}s_{i}(x)$

26: $r^{*}(x):=\mathop{\rm
argmax}\limits_{i\in\\{0,1\\}}\big{[}s_{h^{*}(x)}(x),s_{L}(x)\big{]}$

27: Return $h^{*}(x),r^{*}(x)$

28:end procedure

######  Theorem 5.1 (Generalization of the Constraints).

For the approximation of the Neyman-Pearson solution
$\hat{f}_{\hat{k},\hat{p}}(x)$ in Algorithm 1 such that
$\mathbb{E}_{S^{n}}\big{[}\langle\hat{f}_{\hat{k},\hat{p}}(x),\hat{\psi}_{1}(x)\rangle\big{]}\leq\delta$,
if we assume that embedding functions are bounded, then for
$d_{n}(\epsilon)\simeq O(\frac{\sqrt{\log n}+\sqrt{\log
1/\epsilon}}{\sqrt{n}})$ and $S^{n}\sim\mu$ we have
$\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{\hat{k},\hat{p}}(x),\psi_{1}(x)\rangle\big{]}\leq\delta+d_{n}(\epsilon)$
with probability at least $1-\epsilon$.

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
$\hat{\psi}_{1}(x)$ in hand where
$\|\hat{\psi}_{1}(x)-\psi_{1}(x)\|_{\infty}\leq\epsilon^{\prime}$ with high
probability, this theorem together with Hölder’s inequality shows that we need
to assure
$\mathbb{E}_{S^{n}}\big{[}\langle\hat{f}_{\hat{k},\hat{p}}(x),\hat{\psi}_{1}(x)\rangle\big{]}\leq\delta-
d_{n}-\epsilon^{\prime}$ 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 ($\gamma$,
$\Delta$)-sensitivity condition as the following. This is an extension to
detection condition in [67] and assumes that changing the parameter in
predictor leads to a detectable change in constraints.

######  Definition 5.2.

For an embedding function $\psi_{1}$, and a distribution $\mu_{X}$ on ${\cal
X}$, we refer to a function $r_{k}(x)$ as a prediction with ($\gamma$,
$\Delta$)-sensitivity around $k$, if there exists $C\in\mathbb{R}^{+}$ such
that for all $\delta\in(0,\Delta]$ we have

$\displaystyle\Big{|}\mathbb{E}_{\mu_{X}}\big{[}\langle
r_{k}(x)-r_{k+\delta}(x),\psi_{1}(x)\rangle\big{]}\Big{|}\geq
C\delta^{\gamma}.$ (11)

Now, we express the following generalization theorem for predictors that
address the above conditions:

######  Theorem 5.3 (Generalization of Objective).

Assume that $(\delta-\epsilon_{l},\delta+\epsilon_{u})$ is a subset of of all
achievable constraints $\mathbb{E}\big{[}\langle
f(x),\psi_{1}(x)\rangle\big{]}$, and that $\|\psi_{i}(x)\|_{\infty}\leq 1$ for
$i=1,2$. Further, let the size $n$ of validation data be large enough such
that $d_{n}(\delta/3)\leq\frac{\epsilon_{l}}{2}$. Now, if the optimal
predictor $f^{*}_{k,0}(x)$ is ($\gamma$, $\Delta$)-sensitive around optimal
$k^{*}$ for
$\Delta\geq\frac{\Big{(}2\max\\{d_{n}(\delta/3),\delta_{1}\\}+\sqrt{2\gamma
C(\delta_{0}+K\delta_{1})}\Big{)}}{C}^{1/\gamma}$ and $\gamma\leq 1$, then for
$n\geq\frac{16}{\epsilon_{l}^{2}}\log\frac{3}{\delta}$, and with probability
at least $1-\delta$, the optimal empirical classifier, as of Algorithm 1 has
an objective that is close to the true optimal objective as

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k^{*},p^{*}}(x),\psi_{0}(x)\rangle\big{]}-\mathbb{E}\big{[}\langle\hat{f}_{\hat{k},\hat{p}}(x),\psi_{0}(x)\rangle\big{]}\leq$
$\displaystyle
2\Big{(}\frac{2\max\\{d_{n}(\delta/3),\delta_{0}\\}}{C}\Big{)}^{1/\gamma}+4\sqrt{\frac{2(\delta_{0}+K\delta_{1})}{\gamma
C}}$ $\displaystyle+2(\delta_{0}+K\delta_{1})+2Kd_{n}(\delta/3),$ (12)

where $K$ is an upper-bound to the absolute value of $k^{*}$.

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 $\frac{1}{n}$-suboptimal solution
for human intervention budget as shown in Theorem F.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 $\hat{r}$ for empirical distributions
and based on the two losses $\mathds{1}_{m\neq y}$ and $\mathds{1}_{h(x)\neq
y}$, there exist two probability measures $\mu_{1}$ and $\mu_{2}$ on ${\cal
X}\times{\cal Y}\times{\cal M}$ such that the corresponding $(\hat{r},X)$ for
both measures is distributed equally. However, the optimal deferral
$r^{*}_{\mu_{1}}$ and $r^{*}_{\mu_{2}}$ for these measures are not
interchangeable, that is
$L_{\mathrm{def}}^{\mu_{i}}(h,r^{*}_{\mu_{i}})\leq\frac{1}{3}$ while
$L_{\mathrm{def}}^{\mu_{i}}(h,r^{*}_{\mu_{j}})=\frac{2}{3}$ for $i=1,2$ and
$j\neq 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 L for more details and
proof of aforementioned proposition.

##  6 Experiments

Figure 2: Performance of $d$-GNP on COMPAS dataset (left), and ACSIncome
(center and right)

We implemented 444The code is available in
https://github.com/AminChrs/PostProcess/.  Algorithm 1, first for COMPAS
dataset [24] in which the recidivism rate of 7214 criminal defendants is
predicted. The human assessment is done in this 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.555This is as
opposed to the experiment in [41] where the human decision is simulated. 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. [41] 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. [47] 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.

We further tested our method on folktables dataset [22] 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.

##  7 Conclusion

The $d$-GNP is a general framework that obtains the optimal solution to
various constrained learning problems, including but not limited to multi-
objective L2D problems. Using this post-processing framework, we can first
estimate the scores related to our problem and then find 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.

##  8 Acknowledgment

M.A. Charusaie thanks the International Max Planck Research School for
Intelligent Systems (IMPRS-IS) 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.

## References

  * [1] Jean-Yves Audibert and Alexandre B Tsybakov.  Fast learning rates for plug-in classifiers.  2007\.
  * [2] Gagan Bansal, Besmira Nushi, Ece Kamar, Eric Horvitz, and Daniel S Weld.  Is the most accurate ai the best teammate? optimizing ai for teamwork.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11405–11414, 2021.
  * [3] Peter L Bartlett and Marten H Wegkamp.  Classification with a reject option using a hinge loss.  Journal of Machine Learning Research, 9(8), 2008.
  * [4] Emma Beede, Elizabeth Baylor, Fred Hersch, Anna Iurchenko, Lauren Wilcox, Paisan Ruamviboonsuk, and Laura M Vardoulakis.  A human-centered evaluation of a deep learning system deployed in clinics for the detection of diabetic retinopathy.  In Proceedings of the 2020 CHI conference on human factors in computing systems, pages 1–12, 2020.
  * [5] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth.  Learnability and the vapnik-chervonenkis dimension.  Journal of the ACM (JACM), 36(4):929–965, 1989.
  * [6] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  Foundations and Trends® in Machine learning, 3(1):1–122, 2011.
  * [7] Yuzhou Cao, Tianchi Cai, Lei Feng, Lihong Gu, GU Jinjie, Bo An, Gang Niu, and Masashi Sugiyama.  Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses.  In Advances in Neural Information Processing Systems.
  * [8] Yuzhou Cao, Hussein Mozannar, Lei Feng, Hongxin Wei, and Bo An.  In defense of softmax parametrization for calibrated and consistent learning to defer.  Advances in Neural Information Processing Systems, 36, 2024.
  * [9] Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama.  Classification with rejection based on cost-sensitive classification.  In International Conference on Machine Learning, pages 1507–1517. PMLR, 2021.
  * [10] Mohammad-Amin Charusaie, Hussein Mozannar, David Sontag, and Samira Samadi.  Sample efficient learning of predictors that complement humans.  In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 2972–3005. PMLR, 2022.
  * [11] Richard J Chen, Judy J Wang, Drew FK Williamson, Tiffany Y Chen, Jana Lipkova, Ming Y Lu, Sharifa Sahai, and Faisal Mahmood.  Algorithmic fairness in artificial intelligence for medicine and healthcare.  Nature biomedical engineering, 7(6):719–742, 2023.
  * [12] Wenlong Chen, Yegor Klochkov, and Yang Liu.  Post-hoc bias scoring is optimal for fair classification.  arXiv preprint arXiv:2310.05725, 2023.
  * [13] Xin Cheng, Yuzhou Cao, Haobo Wang, Hongxin Wei, Bo An, and Lei Feng.  Regression with cost-based rejection.  Advances in Neural Information Processing Systems, 36, 2024.
  * [14] C Chow.  On optimum recognition error and reject tradeoff.  IEEE Transactions on information theory, 16(1):41–46, 1970.
  * [15] Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil.  Leveraging labeled and unlabeled data for consistent fair binary classification.  Advances in Neural Information Processing Systems, 32, 2019.
  * [16] Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq.  Algorithmic decision making and the cost of fairness.  In Proceedings of the 23rd acm sigkdd international conference on knowledge discovery and data mining, pages 797–806, 2017.
  * [17] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri.  Learning with rejection.  In Algorithmic Learning Theory: 27th International Conference, pages 67–82. Springer, 2016.
  * [18] André F Cruz and Moritz Hardt.  Unprocessing seven years of algorithmic fairness.  arXiv preprint arXiv:2306.07261, 2023.
  * [19] George B Dantzig and Abraham Wald.  On the fundamental lemma of neyman and pearson.  The Annals of Mathematical Statistics, 22(1):87–93, 1951.
  * [20] Abir De, Paramita Koley, Niloy Ganguly, and Manuel Gomez-Rodriguez.  Regression under human assistance.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2611–2620, 2020.
  * [21] Abir De, Nastaran Okati, Ali Zarezade, and Manuel Gomez Rodriguez.  Classification under human assistance.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5905–5913, 2021.
  * [22] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt.  Retiring adult: New datasets for fair machine learning.  Advances in neural information processing systems, 34:6478–6490, 2021.
  * [23] Kate Donahue, Alexandra Chouldechova, and Krishnaram Kenthapadi.  Human-algorithm collaboration: Achieving complementarity and avoiding unfairness.  In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1639–1656, 2022.
  * [24] Julia Dressel and Hany Farid.  The accuracy, fairness, and limits of predicting recidivism.  Science advances, 4(1):eaao5580, 2018.
  * [25] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel.  Fairness through awareness.  In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214–226, 2012.
  * [26] Cynthia Dwork and Christina Ilvento.  Fairness under composition.  arXiv preprint arXiv:1806.06122, 2018.
  * [27] Ran El-Yaniv et al.  On the foundations of noise-free selective classification.  Journal of Machine Learning Research, 11(5), 2010.
  * [28] David Heaver Fremlin.  Measure theory, volume 4.  Torres Fremlin, 2000.
  * [29] Aditya Gangrade, Anil Kag, and Venkatesh Saligrama.  Selective classification via one-sided prediction.  In International Conference on Artificial Intelligence and Statistics, pages 2179–2187. PMLR, 2021.
  * [30] Yonatan Geifman and Ran El-Yaniv.  Selective classification for deep neural networks.  Advances in neural information processing systems, 30, 2017.
  * [31] Moritz Hardt, Eric Price, and Nati Srebro.  Equality of opportunity in supervised learning.  Advances in neural information processing systems, 29, 2016.
  * [32] Xiaoqian Jiang, Melanie Osl, Jihoon Kim, and Lucila Ohno-Machado.  Calibrating predictive model estimates to support personalized medicine.  Journal of the American Medical Informatics Association, 19(2):263–274, 2012.
  * [33] Erik Jones, Shiori Sagawa, Pang Wei Koh, Ananya Kumar, and Percy Liang.  Selective classification can magnify disparities across groups.  arXiv preprint arXiv:2010.14134, 2020.
  * [34] Ece Kamar, Severin Hacker, and Eric Horvitz.  Combining human and machine intelligence in large-scale crowdsourcing.  In AAMAS, volume 12, pages 467–474, 2012.
  * [35] Achim Klenke.  Probability theory: a comprehensive course.  Springer Science & Business Media, 2013.
  * [36] Benjamin Kompa, Jasper Snoek, and Andrew L Beam.  Second opinion needed: communicating uncertainty in medical machine learning.  NPJ Digital Medicine, 4(1):1–6, 2021.
  * [37] Thomas Landgrebe and R Duin.  On neyman-pearson optimisation for multiclass classifiers.  In Proceedings 16th Annual Symposium of the Pattern Recognition Association of South Africa. PRASA, pages 165–170, 2005.
  * [38] Joshua K Lee, Yuheng Bu, Deepta Rajan, Prasanna Sattigeri, Rameswar Panda, Subhro Das, and Gregory W Wornell.  Fair selective classification via sufficiency.  In International conference on machine learning, pages 6076–6086. PMLR, 2021.
  * [39] Erich Leo Lehmann, Joseph P Romano, and George Casella.  Testing statistical hypotheses, volume 3.  Springer, 1986.
  * [40] Shuqi Liu, Yuzhou Cao, Qiaozhen Zhang, Lei Feng, and Bo An.  Mitigating underfitting in learning to defer with consistent losses.  In International Conference on Artificial Intelligence and Statistics, pages 4816–4824. PMLR, 2024.
  * [41] David Madras, Toni Pitassi, and Richard Zemel.  Predict responsibly: improving fairness and accuracy by learning to defer.  Advances in Neural Information Processing Systems, 31, 2018.
  * [42] Anqi Mao, Mehryar Mohri, and Yutao Zhong.  Predictor-rejector multi-class abstention: Theoretical analysis and algorithms.  In International Conference on Algorithmic Learning Theory, pages 822–867. PMLR, 2024.
  * [43] Charles E Metz.  Basic principles of roc analysis.  In Seminars in nuclear medicine, volume 8, pages 283–298. Elsevier, 1978.
  * [44] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  Foundations of machine learning.  MIT press, 2018.
  * [45] Hussein Mozannar, Hunter Lang, Dennis Wei, Prasanna Sattigeri, Subhro Das, and David Sontag.  Who should predict? exact algorithms for learning to defer to humans.  In International conference on artificial intelligence and statistics, pages 10520–10545. PMLR, 2023.
  * [46] Hussein Mozannar, Hunter Lang, Dennis Wei, Prasanna Sattigeri, Subhro Das, and David Sontag.  Who should predict? exact algorithms for learning to defer to humans.  arXiv preprint arXiv:2301.06197, 2023.
  * [47] Hussein Mozannar and David Sontag.  Consistent estimators for learning to defer to an expert.  In International Conference on Machine Learning, pages 7076–7087. PMLR, 2020.
  * [48] Harikrishna Narasimhan, Wittawat Jitkrittum, Aditya K Menon, Ankit Rawat, and Sanjiv Kumar.  Post-hoc estimators for learning to defer to an expert.  Advances in Neural Information Processing Systems, 35:29292–29304, 2022.
  * [49] Harikrishna Narasimhan, Aditya Krishna Menon, Wittawat Jitkrittum, Neha Gupta, and Sanjiv Kumar.  Learning to reject meets long-tail learning.  In The Twelfth International Conference on Learning Representations.
  * [50] Harikrishna Narasimhan, Aditya Krishna Menon, Wittawat Jitkrittum, and Sanjiv Kumar.  Plugin estimators for selective classification with out-of-distribution detection.  arXiv preprint arXiv:2301.12386, 2023.
  * [51] Harikrishna Narasimhan, Harish G Ramaswamy, Shiv Kumar Tavker, Drona Khurana, Praneeth Netrapalli, and Shivani Agarwal.  Consistent multiclass algorithms for complex metrics and constraints.  arXiv preprint arXiv:2210.09695, 2022.
  * [52] Jerzy Neyman and Egon Sharpe Pearson.  Ix. on the problem of the most efficient tests of statistical hypotheses.  Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 231(694-706):289–337, 1933.
  * [53] Jerzy Neyman and Egon Sharpe Pearson.  Contributions to the theory of testing statistical hypotheses.  Statistical research memoirs, 1936.
  * [54] Nastaran Okati, Abir De, and Manuel Rodriguez.  Differentiable learning under triage.  Advances in Neural Information Processing Systems, 34:9140–9151, 2021.
  * [55] Christos H Papadimitriou and Kenneth Steiglitz.  Combinatorial optimization: algorithms and complexity.  Courier Corporation, 1998.
  * [56] Charles Chapman Pugh and CC Pugh.  Real mathematical analysis, volume 2011.  Springer, 2002.
  * [57] Maithra Raghu, Katy Blumer, Greg Corrado, Jon Kleinberg, Ziad Obermeyer, and Sendhil Mullainathan.  The algorithmic automation problem: Prediction, triage, and human effort.  arXiv preprint arXiv:1903.12220, 2019.
  * [58] Philippe Rigollet and Xin Tong.  Neyman-pearson classification, convexity and stochastic constraints.  Journal of machine learning research, 2011.
  * [59] Salvatore Ruggieri, Jose M Alvarez, Andrea Pugnana, Franco Turini, et al.  Can we trust fair-ai?  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 15421–15430, 2023.
  * [60] Stephen-John Sammut, Mireia Crispin-Ortuzar, Suet-Feung Chin, Elena Provenzano, Helen A Bardwell, Wenxin Ma, Wei Cope, Ali Dariush, Sarah-Jane Dawson, Jean E Abraham, et al.  Multi-omic machine learning predictor of breast cancer therapy response.  Nature, 601(7894):623–629, 2022.
  * [61] Clayton Scott.  Performance measures for neyman–pearson classification.  IEEE Transactions on Information Theory, 53(8):2852–2863, 2007\.
  * [62] Clayton Scott and Robert Nowak.  A neyman-pearson approach to statistical learning.  IEEE Transactions on Information Theory, 51(11):3806–3819, 2005\.
  * [63] Shai Shalev-Shwartz and Shai Ben-David.  Understanding machine learning: From theory to algorithms.  Cambridge University Press, 2014.
  * [64] Dharmesh Tailor, Aditya Patra, Rajeev Verma, Putra Manggala, and Eric Nalisnick.  Learning to defer to a population: A meta-learning approach.  In International Conference on Artificial Intelligence and Statistics, pages 3475–3483. PMLR, 2024.
  * [65] Sarah Tan, Julius Adebayo, Kori Inkpen, and Ece Kamar.  Investigating human+ machine complementarity for recidivism predictions.  arXiv preprint arXiv:1808.09123, 2018.
  * [66] Ye Tian and Yang Feng.  Neyman-pearson multi-class classification via cost-sensitive learning.  arXiv preprint arXiv:2111.04597, 2021.
  * [67] Xin Tong.  A plug-in approach to neyman-pearson classification.  The Journal of Machine Learning Research, 14(1):3011–3040, 2013\.
  * [68] C Vermeulen, M Pagès-Gallego, L Kester, MEG Kranendonk, P Wesseling, N Verburg, P de Witt Hamer, EJ Kooi, L Dankmeijer, J van der Lugt, et al.  Ultra-fast deep-learned cns tumour classification during surgery.  Nature, 622(7984):842–849, 2023.
  * [69] Ruicheng Xian, Lang Yin, and Han Zhao.  Fair and optimal classification via post-processing.  In International Conference on Machine Learning, pages 37977–38012. PMLR, 2023.
  * [70] Tongxin Yin, Jean-François Ton, Ruocheng Guo, Yuanshun Yao, Mingyan Liu, and Yang Liu.  Fair classifiers that abstain without harm.  arXiv preprint arXiv:2310.06205, 2023.
  * [71] Xianli Zeng, Guang Cheng, and Edgar Dobriban.  Bayes-optimal fair classification with linear disparity constraints via pre-, in-, and post-processing.  arXiv preprint arXiv:2402.02817, 2024.
  * [72] Xianli Zeng, Edgar Dobriban, and Guang Cheng.  Bayes-optimal classifiers under group fairness.  arXiv preprint arXiv:2202.09724, 2022.

###### Content of Appendices

  1. 1 Introduction
  2. 2 Related Works
  3. 3 Problem Setting
  4. 4 $d$-dimensional Generalization of Neyman-Pearson Lemma
  5. 5 Empirical $d$-GNP and its Statistical Generalization
  6. 6 Experiments
  7. 7 Conclusion
  8. 8 Acknowledgment
  9. A Lack of Compositionality of Fairness Criteria
  10. B Extended Related Works
  11. C Rephrasing (2) into Linear Functional Programming
  12. D Derivation of Embedding Functions
  13. E Limitations of Cost-Sentitive Methods
  14. F On Failure of In-Processing Methods
  15. G Proof of Theorem 3.1
  16. H Proof of Theorem 4.1
  17. I Proof of Theorem 4.2
  18. J Proof of Theorem 5.1
  19. K Proof of Theorem 5.3
  20. L Proof of Theorem F.1

##  Appendix A Lack of Compositionality of Fairness Criteria

Here, we show an example of lack of compositionality of fairness criteria for
learn-to-defer problems. This falls in line with [26], 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 ${\cal X}$, and if it could take a decision over only a subset of
${\cal X}$ it will not necessarily be a fair predictor. This can be seen as a
particular application of Yule’s effect [59] 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 ${\cal X}$ contains only four points $x_{1}$,
$x_{2}$, $x_{3}$, and $x_{4}$, and that the input takes these values with
probability
$\mathbb{P}(X=x_{1})=\mathbb{P}(X=x_{2})=\mathbb{P}(X=x_{3})=\mathbb{P}(X=x_{4})=\frac{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 is
$\mathbb{P}(Y=1|x_{1})=\mathbb{P}(Y=1|x_{2})=\mathbb{P}(Y=1|x_{3})=\mathbb{P}(Y=1|x_{4})=1$.
Moreover, we consider the equality of opportunity as the measure of fairness.
Now, assume that the classifier $h(\cdot):{\cal X}\to\\{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
$\frac{1}{2}$ on the data.

Following the above assumptions, we can find the fairness measure for
classifier as

$\displaystyle\mathbb{P}$
$\displaystyle(h(X)=1|Y=1,A=0)-\mathbb{P}(h(X)=1|Y=1,A=1)$ $\displaystyle=$
$\displaystyle\mathbb{P}(h(X)=1|Y=1,A=0,X=x_{1})\mathbb{P}(X=x_{1}|Y=1,A=0)$
$\displaystyle+\mathbb{P}(h(X)=1|Y=1,A=0,X=x_{2})\mathbb{P}(X=x_{2}|Y=1,A=0)$
$\displaystyle-\mathbb{P}(h(X)=1|Y=1,A=1,X=x_{3})\mathbb{P}(X=x_{3}|Y=1,A=1)$
$\displaystyle-\mathbb{P}(h(X)=1|Y=1,A=1,X=x_{4})\mathbb{P}(X=x_{4}|Y=1,A=1)=\frac{1}{2}+0-\frac{1}{2}-0=0,$
(13)

which means that the classifier is fully fair. We can derive a similar result
for the human expert, i.e.,

$\displaystyle\mathbb{P}$
$\displaystyle(M=1|Y=1,A=0)-\mathbb{P}(M=1|Y=1,A=1)=0.$ (14)

Now 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 have

$\displaystyle\mathbb{P}$
$\displaystyle(\hat{Y}=1|Y=1,A=0)-\mathbb{P}(\hat{Y}=1|Y=1,A=1)$
$\displaystyle=$
$\displaystyle\mathbb{P}(h(X)=1|Y=1,A=0,X=x_{1})\mathbb{P}(X=x_{1}|Y=1,A=0)$
$\displaystyle+\mathbb{P}(M=1|Y=1,A=0,X=x_{2})\mathbb{P}(X=x_{2}|Y=1,A=0)$
$\displaystyle-\mathbb{P}(h(X)=1|Y=1,A=1,X=x_{3})\mathbb{P}(X=x_{3}|Y=1,A=1)$
$\displaystyle-\mathbb{P}(h(X)=1|Y=1,A=1,X=x_{4})\mathbb{P}(X=x_{4}|Y=1,A=1)=\frac{1}{2}+\frac{1}{2}-\frac{1}{2}-0=\frac{1}{2},$
(15)

or 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 $\frac{1}{2}$ is
fair.

##  Appendix B Extended Related Works

The deferral problem has been studied under a variety of conditions. Rejection
learning [17, 3, 9, 13] or selective classification [27, 30, 29], 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 [14]. Assuming that the accuracy of human, and consequently the
cost of deferring to the human, can vary for different inputs, [47] 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 [20, 21]. Most recently, the implementation of
deferral rules using neural networks and surrogate losses is studied for
binary and multi-class classification [7, 47, 10, 48, 8, 40, 45, 42]. A
possible shift in human expert for L2D methods recently studied in [64]. 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
[54, 49, 50] and [70, 38] for L2D and rejection learning, respectively.

Neyman-Pearson’s fundamental lemma is introduced in [52] originally for binary
hypothesis testing and later was generalized in [53] to give a close-form
formulation for a variety of binary constrained optimization problems. Later,
[19] found conditions for which Neyman and Pearson solution exists and is
unique. The generalization 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 [62, 61, 58], and (ii) the
generalization of plug-in methods [67] 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 [37] and under strong duality assumption is proved in
[66]. 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 [72]
(later as [71]). More recently, a similar post-processing method is introduced
in [12] 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.

Lastly, this work differs from multi-class classification with complex
performance metrics [51] 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.

##  Appendix C Rephrasing (2) into Linear Functional Programming

Here, we first characterize functions that are outcome-dependent. To that end,
we define $\imath(x)$ as

$\displaystyle\imath=\big{[}\mathbb{I}_{r(x)=0}\mathbb{I}_{h(x)=1},\ldots,\mathbb{I}_{r(x)=0}\mathbb{I}_{h(x)=L},\mathbb{I}_{r(x)=1}\big{]}.$
(16)

This 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)=\big{(}\imath(x)\big{)}(L+1)$ and $h(x)=i$ if $r(x)=0$ and
$\big{(}\imath(x)\big{)}(i)=1$. Therefore, for a function
$\overline{\Psi}(x,h(x),r(x))=\mathbb{E}_{Y,M|X=x}\big{[}\Psi(x,Y,M,h(x),r(x))\big{]}$
and
$\overline{\ell}_{\mathrm{def}}(x,h(x),r(x))=\mathbb{E}_{Y,M|X=x}\big{[}\ell_{\mathrm{def}}(x,Y,M,h(x),r(x))\big{]}$
to be outcome dependent, it must only be a function of $x$ and $\imath(x)$. In
fact, we must have

$\displaystyle\overline{\Psi}_{i}(x,h(x),r(x))=\Psi^{\prime}_{i}(x,\imath(x)),$
(17)

and

$\displaystyle\overline{\ell}_{\mathrm{def}}(x,h(x),r(x))=\ell^{\prime}_{\mathrm{def}}(x,\imath(x)),$
(18)

for a choice of $\Psi^{\prime}$ and $\ell^{\prime}_{\mathrm{def}}$, where
$\overline{\ell}_{\mathrm{def}}(x,h(x),r(x))=\mathbb{E}_{Y,M|X=x}\big{[}{\ell}_{\mathrm{def}}(x,Y,M,h(x),r(x))\big{]}$.

Now, we can check that $\imath(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 have

$\displaystyle\Psi^{\prime}_{i}(x,\imath(x))=\sum_{i=1}^{L+1}\Psi^{\prime}(x,[0,\ldots,\underbrace{1}_{i},\ldots,0])\Big{(}\big{(}\imath(x)\big{)}(i)\Big{)}=\langle\imath(x),\psi_{i}(x)\rangle,$
(19)

where $\psi_{i}(x)$ is defined as

$\displaystyle\psi_{i}(x)$
$\displaystyle=\Big{[}\Psi^{\prime}_{i}(x,[1,0,\ldots,0]),\ldots,\Psi^{\prime}(x,[0,0,\ldots,1])\Big{]}$
$\displaystyle=\big{[}\overline{\Psi}_{i}(x,1,0),\ldots,\overline{\Psi}_{i}(x,L,0),\overline{\Psi}_{i}(x,0,1)\big{]}.$
(20)

Similarly, we can show that

$\displaystyle\ell^{\prime}_{\mathrm{def}}(x,\imath(x))=\langle\imath(x),\vec{\ell}_{\mathrm{def}}(x)\rangle,$
(21)

where $\vec{\ell}_{\mathrm{def}}(x)$ is defined as

$\displaystyle\vec{\ell}_{\mathrm{def}}(x)=\big{[}\overline{\ell}_{\mathrm{def}}(x,1,0),\ldots,\overline{\ell}_{\mathrm{def}}(x,L,0),\overline{\ell}_{\mathrm{def}}(x,0,1)\big{]}.$
(22)

Next, we know that due to the randomization of ${\cal A}$, the vector
$\imath(x)$ can take various values on each instance $x$. This, however, is
not the case for $\psi_{i}(x)$ and $\vec{\ell}_{\mathrm{def}}(x)$, since they
are defined independent of $r(x)$ and $h(x)$. Therefore, the average of
constraints and loss can be rewritten as

$\displaystyle\mathbb{E}_{(r,h)\sim{\cal
A}}\big{[}\overline{\Psi}_{i}(x,h(x),r(x))\big{]}=\mathbb{E}_{(r,h)\sim{\cal
A}}\big{[}\langle\psi_{i}(x),\imath(x)\rangle\big{]}=\langle
f(x),\psi_{i}(x)\rangle,$ (23)

and

$\displaystyle\mathbb{E}_{(r,h)\sim{\cal
A}}\big{[}\ell_{\mathrm{def}}(x,h(x),r(x))\big{]}=\mathbb{E}_{(r,h)\sim{\cal
A}}\big{[}\langle\vec{\ell}_{\mathrm{def}}(x),\imath(x)\rangle\big{]}=\langle
f(x),\vec{\ell}_{\mathrm{def}}(x)\rangle,$ (24)

where $f(x)$ is defined as

$\displaystyle
f(x)=\mathbb{E}[\imath(x)]=\big{[}\mathbb{P}(r(x)=0,h(x)=1),\ldots,\mathbb{P}(r(x)=0,h(x)=L),\mathbb{P}(r(x)=1)\big{]}.$
(25)

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
$\mathbb{P}(r(x)=1)=\big{(}f^{*}(x)\big{)}(L+1)$, where $h(x)$ should be
distributed as
$\mathbb{P}(h(x)=i)=\mathbb{P}(h(x)=i|r(x)=0)=\frac{\big{(}f(x)\big{)}(i)}{\sum_{i=1}^{L}\big{(}f(x)\big{)}(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$.

##  Appendix D Derivation of Embedding Functions

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 ${\cal A}$ and the input variable $X$, and then we use (20) 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 $\hat{Y}$. Therefore, the corresponding
$\ell_{def}(x,h(x),r(x))$ in this case, as defined in (1) is obtained as

$\displaystyle\overline{\ell}_{def}(x,h(x),r(x))=$
$\displaystyle\mathbb{E}_{Y,M|X=x}\big{[}\mathbb{I}_{r(x)=1}\mathbb{I}_{M\neq
Y}+\mathbb{I}_{r(x)=0}\mathbb{I}_{h(x)\neq Y}\big{]}$
$\displaystyle=\mathbb{I}_{r(x)=1}\mathbb{P}(M=Y|X=x)+\mathbb{I}_{r(x)=0}\mathbb{P}(Y\neq
h(x)|X=x).$

Therefore, using (22) we find $\vec{\ell}_{\mathrm{def}}$ as

$\displaystyle\vec{\ell}_{\mathrm{def}}=\big{[}\mathbb{P}(Y\neq
1|X=x),\ldots,\mathbb{P}(Y\neq n|X=x),\mathbb{P}(Y\neq M|X=x)\big{]}.$

  * •

Expert intervention budget: In this case, similar to the case before, we first
derive $\overline{\Psi}(x,h(x),r(x))$. To that end, we first note that the
expert intervention constraint in Section 3 is equivalent with

$\displaystyle\mathbb{P}(r(X)=1)=\mathbb{E}_{x\sim\mu_{X},(r,h)\sim{\cal
A}}\big{[}\mathbb{I}_{r(x)=1}\big{]}\leq\delta,$

which in turn suggests that

$\displaystyle\overline{\Psi}(x,h(x),r(x))=\mathbb{I}_{r(x)=1}.$

Next, we find $\psi(x)$ using (20), as

$\displaystyle\psi(x)=[0,\ldots,0,1].$

  * •

OOD Detection: To obtain the corresponding embedding function to the OOD
detection constraint in Section 3, we can rewrite
$\mathbb{P}_{\mathrm{out}}\big{(}r(X)=1\big{)}$ as

$\displaystyle\mathbb{P}_{~{}~{}~{}~{}~{}~{}\mathrm{out}}\big{(}r(X)=1\big{)}$
$\displaystyle=\mathbb{E}_{X\sim f_{X}^{\mathrm{out}},(r,h)\sim{\cal
A}}\big{[}\mathbb{I}_{r(X)=1}\big{]}$
$\displaystyle=\mathbb{E}_{X\sim\mu_{X^{\mathrm{in}}},(r,h)\sim{\cal
A}}\big{[}\tfrac{\mathbb{I}_{r(X)=1}f_{X}^{\mathrm{out}}(X)}{f_{X}^{\mathrm{in}}(X)}\big{]},$

where the last equation holds when $X$ and $X_{\mathrm{out}}$ are absolutely
continuous distributions, and therefore have probability density functions. A
similar assumption is made by [50]. This results in
$\overline{\Psi}(x,h(x),r(x))$ being obtained as

$\displaystyle\overline{\Psi}(x,h(x),r(x))=\frac{\mathbb{I}_{r(x)=1}f_{X}^{\mathrm{out}}(X)}{f_{X}^{\mathrm{in}}(X)}.$

Therefore, we conclude that the embedding function can be calculated using
(20) as

$\displaystyle\psi(x)=\big{[}0,\ldots,0,\tfrac{f_{X}^{\mathrm{out}}(X)}{f_{X}^{\mathrm{in}}(X)}].$

In the simple case that
$f_{X}^{\mathrm{out}}(x)=\frac{f_{X}^{\mathrm{in}}(x)\mathbb{I}_{f_{X}^{\mathrm{in}}(x)\leq\epsilon}}{\int
f_{X}^{\mathrm{in}}(x)\mathbb{I}_{f_{X}^{\mathrm{in}}(x)\leq\epsilon}{\rm
d}x}$, the embedding function is equal to

$\displaystyle\psi(x)=\big{[}0,\ldots,0,\frac{\mathbb{I}_{f_{X}^{\mathrm{in}}(x)\leq\epsilon}}{\mathbb{P}_{\mathrm{in}}(f_{X}^{\mathrm{in}}(X)\leq\epsilon)}].$

  * •

Long-Tail Classification: This methodology aims to minimize the balanced loss

$\displaystyle\frac{1}{K}\sum_{i=1}^{K}\mathbb{P}(Y\neq h(X)|r(X)=0,Y\in
G_{i}).$

However, as mentioned in [49], this optimization problem can be rewritten as

$\displaystyle\sum_{i=1}^{K}\frac{\mathbb{P}(Y\neq h(X),r(X)=0|Y\in
G_{i})}{\alpha_{i}},~{}~{}~{}~{}~{}\text{s.t. }~{}~{}\mathbb{P}(r(X)=0|Y\in
G_{i})=\frac{\alpha_{i}}{K}.$

Therefore, the objective can rewritten as

$\displaystyle\sum_{i=1}^{K}\frac{\mathbb{E}_{(r,h)\sim{\cal
A},X^{\prime}\sim\mu_{X}}\big{[}\mathbb{P}(Y\neq h(X),r(X)=0,Y\in
G_{i}|X=X^{\prime})\big{]}}{\alpha_{i}\mathbb{P}(Y\in G_{i})},$

which together with (20) shows that

$\displaystyle\psi_{0}(x)=-\Big{[}\sum_{i=1}^{K}\frac{\mathbb{P}(Y\neq 1,Y\in
G_{i}|X=x)}{\alpha_{i}\mathbb{P}(Y\in
G_{i})},\ldots,\sum_{i=1}^{K}\frac{\mathbb{P}(Y\neq L,Y\in
G_{i}|X=x)}{\alpha_{i}\mathbb{P}(Y\in G_{i})},0\Big{]}.$

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 as

$\displaystyle\frac{\mathbb{E}_{(r,h)\sim{\cal
A},X^{\prime}\sim\mu_{X}}\big{[}\mathbb{P}(r(X)=0,Y\in
G_{i}|X=X^{\prime})-\frac{\alpha_{i}}{K}\mathbb{P}(Y\in
G_{i})\big{]}}{\mathbb{P}(Y\in G_{i})}.$

Therefore, using (20) we can obtain $\psi_{i}(x)$ as

$\displaystyle\psi_{i}(x)=\frac{\mathbb{P}(Y\in G_{i}|X=x)}{\mathbb{P}(Y\in
G_{i})}\Big{[}1,\ldots,1,0\Big{]}-\frac{\alpha_{i}}{K}.$ (26)

  * •

Type-$k$ Error Bound: We first rewrite Type-$k$ constraint in 3 as

$\displaystyle\mathbb{P}(\hat{Y}\neq k|Y=k)$
$\displaystyle=\frac{\mathbb{P}(\hat{Y}\neq k,Y=k)}{\mathbb{P}(Y=k)}$
$\displaystyle\overset{(a)}{=}\frac{\mathbb{E}_{X\sim\mu_{X}}\big{[}\mathbb{P}(\hat{Y}\neq
k,Y=k|X=x)\big{]}}{\mathbb{P}(Y=k)}$
$\displaystyle=\frac{\mathbb{E}_{X\sim\mu_{X}}\big{[}\mathbb{P}(\hat{Y}\neq
k|Y=k,X=x)\mathbb{P}(Y=k|X=x)\big{]}}{\mathbb{P}(Y=k)},$ (27)

where $(a)$ is followed by chain rule.

Next, we condition $\mathbb{P}(\hat{Y}\neq k|Y=k,X=x)$ on $r(X)$ being $1$ and
$0$, which concludes that

$\displaystyle\mathbb{P}(\hat{Y}\neq k|Y=k,X=x)$
$\displaystyle=\mathbb{P}(\hat{Y}\neq k,r(x)=1|Y=k,X=x)$
$\displaystyle\phantom{=}+\mathbb{P}(\hat{Y}\neq k,r(x)=0|Y=k,X=x)$
$\displaystyle=\mathbb{P}(M\neq k,r(x)=1|Y=k,X=x)$
$\displaystyle\phantom{=}+\mathbb{P}(h(x)\neq k,r(x)=0|Y=k,X=x)$
$\displaystyle=\mathbb{E}_{(r,h)\sim{\cal
A},M|X=x,Y=k}\big{[}\mathbb{I}_{M\neq
k}\mathbb{I}_{r(x)=1}+\mathbb{I}_{h(x)\neq k}\mathbb{I}_{r(x)=0}\big{]}$
$\displaystyle=\mathbb{E}_{(r,h)\sim{\cal A}|X=x,Y=k}\big{[}\mathbb{P}({M\neq
k}|X=x,Y=k)\mathbb{I}_{r(x)=1}$
$\displaystyle\phantom{=\mathbb{E}_{(r,h)\sim{\cal
A}|X=x,Y=k}\big{[}}~{}~{}+\mathbb{I}_{h(x)\neq k}\mathbb{I}_{r(x)=0}\big{]}.$

Therefore, using (27) we conclude that

$\displaystyle\mathbb{P}(\hat{Y}\neq k|Y=k)=$
$\displaystyle\frac{\mathbb{E}_{X^{\prime}\sim\mu_{X},(r,h)\sim{\cal
A}}\big{[}\mathbb{I}_{r(X)=1}\mathbb{P}(M\neq
k,Y=k|X=X^{\prime})\big{]}}{\mathbb{P}(Y=k)}$
$\displaystyle+\frac{\mathbb{E}_{X^{\prime}\sim\mu_{X},(r,h)\sim{\cal
A}}\big{[}\mathbb{I}_{h(X^{\prime})\neq
k}\mathbb{I}_{r(X^{\prime})=0}\mathbb{P}(Y=k|X=X^{\prime})\big{]}}{\mathbb{P}(Y=k)},$

which together with (20) shows that the embedding function is obtained as

$\displaystyle\psi(x)=\frac{\mathbb{P}(Y=k|X=x)}{\mathbb{P}(Y=k)}\Big{[}1,\ldots,1,\underbrace{0}_{k},1,\ldots,1,\mathbb{P}(M\neq
k|X=x,Y=k)\Big{]}.$

Note that here we used the assumption that $(Y,M)$ and ${\cal A}$ are
independent for each choice of $X$, i.e., the value noise that is introduced
in ${\cal 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 as

$\displaystyle-\delta\leq\mathbb{P}(\hat{Y}=1|A=0)-\mathbb{P}(\hat{Y}=1|A=1)\leq\delta.$
(28)

Here, we find the corresponding embedding function $\psi(x)$ for the upper-
bound in the above inequality. For the lower-bound, we can use $-\psi(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 (28), we
first rewrite $\mathbb{P}(\hat{Y}=1|A=0)-\mathbb{P}(\hat{Y}=1|A=1)$ as

$\displaystyle\mathbb{P}(\hat{Y}=1|A=0)-\mathbb{P}(\hat{Y}=1|A=1)=\frac{\mathbb{P}(\hat{Y}=1,A=0)}{\mathbb{P}(A=0)}-\frac{\mathbb{P}(\hat{Y}=1,A=1)}{\mathbb{P}(A=1)}.$
(29)

Now, similar to what we did in previous section, we condition
$\mathbb{P}(\hat{Y}=1,A=a)$ for $a\in\\{0,1\\}$ on the value of $h(x)$ and
$r(x)$, and we conclude

$\displaystyle\mathbb{P}(\hat{Y}=1,A=a)$
$\displaystyle=\mathbb{P}(\hat{Y}=1,A=a,r(X)=1)+\mathbb{P}(\hat{Y}=1,A=a,r(X)=0)$
$\displaystyle=\mathbb{P}(M=1,A=a,r(X)=1)+\mathbb{P}(h(X)=1,A=a,r(X)=0)$
$\displaystyle=\mathbb{E}_{X,A,M,{\cal
A}}\big{[}\mathbb{I}_{M=1}\mathbb{I}_{A=a}\mathbb{I}_{r(X)=1}+\mathbb{I}_{h(X)=1}\mathbb{I}_{A=a}\mathbb{I}_{r(X)=0}\big{]}$
$\displaystyle=\mathbb{E}_{X,{\cal
A}}\big{[}\mathbb{P}(M=1,A=a|X=x)\mathbb{I}_{r(X)=1}$
$\displaystyle\phantom{=\mathbb{E}_{X,{\cal
A}}\big{[}}+\mathbb{P}(A=a|X=x)\mathbb{I}_{h(X)=1}\mathbb{I}_{r(X)=0}\big{]}.$
(30)

Here, we used the assumption of independence of $X$ and $(M,Y)$ given a choice
of $X$.

As a result of (29), (30), and (20) we can find the embedding function as

$\displaystyle\psi(x)=\Big{[}$ $\displaystyle
0,\frac{\mathbb{P}(A=1|X=x)}{\mathbb{P}(A=1)}-\frac{\mathbb{P}(A=0|X=x)}{\mathbb{P}(A=0)},$
$\displaystyle\frac{\mathbb{P}(M=1,A=1|X=x)}{\mathbb{P}(A=1)}-\frac{\mathbb{P}(M=1,A=0|X=x)}{\mathbb{P}(A=0)}\Big{]}.$

  * •

(In-)Equality of Opportunity: Similar to the previous items, we rewrite
equality of opportunity constraint in Section 3 as

$\displaystyle-\delta\leq\mathbb{P}(\hat{Y}=1|Y=1,A=1)-\mathbb{P}(\hat{Y}=1|Y=1,A=0)\leq\delta.$

Again, we only consider the upper-bound and rewrite
$\mathbb{P}(\hat{Y}=1|Y=1,A=1)-\mathbb{P}(\hat{Y}=1|Y=1,A=0)$ as

$\displaystyle\mathbb{P}(\hat{Y}=1$
$\displaystyle|Y=1,A=1)-\mathbb{P}(\hat{Y}=1|Y=1,A=0)$
$\displaystyle=\frac{\mathbb{P}(\hat{Y}=1,Y=1,A=1)}{\mathbb{P}(Y=1,A=1)}-\frac{\mathbb{P}(\hat{Y}=1,Y=1,A=0)}{\mathbb{P}(Y=1,A=0)}.$
(31)

Next, by conditioning on $r(X)=1$ and $r(X)=0$, we rewrite
$\mathbb{P}(\hat{Y}=1,Y=1,A=a)$ for $a\in\\{0,1\\}$ as

$\displaystyle\mathbb{P}(\hat{Y}=1,Y=1,A=a)$
$\displaystyle=\mathbb{P}(\hat{Y}=1,Y=1,A=a,r(X)=1)$
$\displaystyle\phantom{=}+\mathbb{P}(\hat{Y}=1,Y=1,A=a,r(X)=0)$
$\displaystyle=\mathbb{P}(M=1,Y=1,A=a,r(X)=1)$
$\displaystyle\phantom{=}+\mathbb{P}(h(X)=1,Y=1,A=a,r(X)=0)$
$\displaystyle=\mathbb{E}_{X,Y,M,A,{\cal
A}}\big{[}\mathbb{I}_{M=1}\mathbb{I}_{Y=1}\mathbb{I}_{A=a}\mathbb{I}_{r(X)=1}$
$\displaystyle\phantom{=\mathbb{E}_{X,Y,M,A,{\cal
A}}\big{[}}+\mathbb{I}_{h(X)=1}\mathbb{I}_{Y=1}\mathbb{I}_{A=a}\mathbb{I}_{r(X)=0}\big{]}$
$\displaystyle=\mathbb{E}_{X,{\cal
A}}\big{[}\mathbb{I}_{r(X)=1}\mathbb{P}({M=1},{Y=1},{A=a}|X=x)$
$\displaystyle\phantom{=\mathbb{E}_{X,{\cal
A}}\big{[}}+\mathbb{I}_{h(X)=1}\mathbb{I}_{r(X)=0}\mathbb{P}({Y=1},{A=a}|X=x)\big{]},$
(32)

where the last identity is followed by the assumption of independence of
${\cal A}$ and $(Y,M,A)$ given an instance $X=x$.

As a result of (31), (32), and (20) we can obtain the embedding function as

$\displaystyle\psi(x)=\Big{[}$ $\displaystyle
0,\frac{\mathbb{P}(Y=1,A=1|X=x)}{\mathbb{P}(Y=1,A=1)}-\frac{\mathbb{P}(Y=1,A=0|X=x)}{\mathbb{P}(Y=1,A=0)}$
$\displaystyle\frac{\mathbb{P}(M=1,Y=1,A=1|X=x)}{\mathbb{P}(Y=1,A=1)}-\frac{\mathbb{P}(M=1,Y=1,A=0|X=x)}{\mathbb{P}(Y=1,A=0)}\Big{]}.$

  * •

(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

$\displaystyle\psi_{1}(x)=\Big{[}$ $\displaystyle
0,\frac{\mathbb{P}(Y=1,A=1|X=x)}{\mathbb{P}(Y=1,A=1)}-\frac{\mathbb{P}(Y=1,A=0|X=x)}{\mathbb{P}(Y=1,A=0)}$
$\displaystyle\frac{\mathbb{P}(M=1,Y=1,A=1|X=x)}{\mathbb{P}(Y=1,A=1)}-\frac{\mathbb{P}(M=1,Y=1,A=0|X=x)}{\mathbb{P}(Y=1,A=0)}\Big{]},$

and another similar to that with changing $Y=1$ into $Y=0$, and therefore as

$\displaystyle\psi_{2}(x)=\Big{[}$
$\displaystyle\frac{\mathbb{P}(Y=0,A=1|X=x)}{\mathbb{P}(Y=0,A=1)}-\frac{\mathbb{P}(Y=0,A=0|X=x)}{\mathbb{P}(Y=0,A=0)},0$
$\displaystyle\frac{\mathbb{P}(M=1,Y=0,A=1|X=x)}{\mathbb{P}(Y=0,A=1)}-\frac{\mathbb{P}(M=1,Y=0,A=0|X=x)}{\mathbb{P}(Y=0,A=0)}\Big{]}.$

##  Appendix E Limitations of Cost-Sentitive Methods

A variety of works have tackled constrained classification problems using
cost-sensitive modeling [39, 15, 54]. 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 ${\cal X}$ are distributed with an atomless probability measure
$\mu_{X}$ (e.g., normal or uniform distribution).666If we have a probability
measure that contains atoms, one can follow the same steps for the first
counterexample.  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., $\mathbb{P}(Y=1|X=x)=1/2$ for all $x\in{\cal 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 G), which in this case, since there is no clear
maximizer, without loss of generality can be set to $h(x)\equiv 1$.

For such assumptions, if we write the Lagrangian in form of

$\displaystyle
L(\lambda,r)=L^{\mu}_{\mathrm{def}}(h,r)+\lambda(\mathbb{E}[r(X)]-b)=\frac{1}{2}-\frac{1}{2}\mathbb{E}\big{[}r(X)\big{]}+\lambda(\mathbb{E}[r(X)]-b),$

then strong duality shows that

$\displaystyle\min_{r\in[0,1]^{{\cal X}}}\max_{\lambda\geq
0}L(\lambda,r)=\max_{\lambda\geq 0}\min_{r\in[0,1]^{{\cal X}}}L(\lambda,r),$
(33)

or 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
$\operatorname{argmin}_{r\in[0,1]}L(\lambda^{*},r)=f^{*},$ where
$\lambda^{*}\in\operatorname{argmax}_{\lambda}\min_{r\in[0,1]}L(\lambda,r),$
and $f^{*}\in\operatorname{argmin}_{r\in[0,1]}\max_{\lambda}L(\lambda,r)$. In
fact, this guarantee holds only in particular examples, e.g., when
$L(\lambda^{*}_{r},r)$ is strictly convex [6, page 8].

In fact, if we optimize $r$ for all $\lambda$ as in RHS of (33), we can show
that $r_{\lambda}(x)=\left\\{\begin{array}[]{cc}1&\lambda<\frac{1}{2}\\\
0&\text{otherwise}\end{array}\right.$. Therefore, $\lambda^{*}$ can be
obtained as $\lambda^{*}=\mathop{\rm argmax}\limits_{\lambda\geq
0}(\lambda-1/2)^{-}-\lambda b$ where $(x)^{-}:=\min\\{x,0\\}$. This can be
rewritten as

$\displaystyle\lambda^{*}$ $\displaystyle=\mathop{\rm
argmax}\limits_{\lambda\geq 0}\left\\{\begin{array}[]{c
c}-\frac{1}{2}-\lambda(b-1)&0\leq\lambda\leq\frac{1}{2}\\\ -\lambda
b&\lambda>\frac{1}{2}\end{array}\right.=\frac{1}{2}.$

Hence, the condition $\lambda<1/2$ is never satisfied and we have
$r_{\lambda^{*}}(x)=0$, i.e., we should never defer. For the deferral rule
$r_{\lambda^{*}}$, the deferral loss (1) is

$\displaystyle
L_{\mathrm{def}}^{\mu}(h,\hat{f})=\mathbb{E}_{X,Y,M}\big{[}\ell_{AI}(Y,h(X),X)\big{]}=\frac{1}{2}.$

To show that $r_{\lambda^{*}}$ 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:

  * $\diamond$

Let $f^{*}(x)=b$, that is a random deferral rule that defers with probability
$b$ everywhere on ${\cal 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 to

$\displaystyle L^{\mu}_{\mathrm{def}}(h,f^{*})$
$\displaystyle=\underbrace{\mathbb{E}[r(X)]}_{b}\cdot\underbrace{\mathbb{E}[\ell_{H}(Y,M)]}_{0}$
$\displaystyle~{}~{}~{}~{}+\underbrace{\mathbb{E}[1-r(X)]}_{1-b}\cdot\underbrace{\mathbb{E}[\ell_{AI}(Y,h(X))]}_{\frac{1}{2}}$
$\displaystyle=\frac{1-b}{2}<\frac{1}{2}.$

  * $\diamond$

The second example is a deterministic deferral rule. Since the probability
measure on ${\cal X}$ is atomless, for all $b\in[0,1]$ there exists a set
${\cal A}$ such that $\mathbb{P}(X\in{\cal A})=b$ [28, Proposition 215D].
Hence, defining $r^{**}(x)=\mathds{1}_{x\in{\cal A}}$ the constraint in (2) is
met. Similar to the last example
$L^{\mu}_{\mathrm{def}}(h,r^{**})=\frac{1-b}{2}<\frac{1}{2}$.

The above two examples show that the deferral rule $r_{\lambda^{*}}$ is sub-
optimal. The reason is that, for optimality of $r_{\lambda^{*}}$ we should
make sure that $L(\lambda^{*}_{r},r)$ has a single minimizer of $r$. However,
in our example we had $L(\frac{1}{2},r)=-\lambda 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.

##  Appendix F 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.

Algorithm 2 Deterministic Algorithm for Deferring Tasks to Human or AI for the
Empirical Distribution and Expert Intervention Budget

Input: The dataset ${\cal D}$, he human and classifier loss $\ell_{H}$ and
$\ell_{AI}$ and available proportion $b$ of instances to defer
Output: Labels of ”defer" or ”no defer" for each instance in ${\cal D}$

1:procedure DeferTasks(${\cal D},\ell_{H},\ell_{AI},b$)

2: Make the set $A=\\{(x,y,m)\in{\cal D}:\ell_{H}(y,m)-\ell_{AI}(y,h(x))\leq
0\\}$

3: if $|A|\geq b|{\cal D}|$ then

4: Defer all tasks in $A$ to human

5: else

6: Defer the $b|{\cal D}|$ tasks with the lowest
$\ell_{H}(x,y,m)-\ell_{AI}(x,y)$ to human

7: end if

8:end procedure

######  Theorem F.1 (Optimal Deferral for Empirical Distribution).

For a classifier $h(x)$ and dataset ${\cal
D}=\\{(x_{i},y_{i},m_{i})\\}_{i=1}^{n}$, where we assume $x_{i}\neq x_{j}$,
$i\neq j$, the deterministic deferral rule as in Algorithm 2 is (i) the
optimal deterministic deferral rule for the empirical distribution on ${\cal
D}$ and bounded expert intervention budget, and (ii) at most
$\frac{1}{n}$-suboptimal (in terms of deferral loss) compared to the optimal
random deferral rule for the empirical distribution on ${\cal 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 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 $\hat{r}$ of Algorithm 2 for each feature $x$ is a
deterministic $0$ or $1$ label, it varies with the choice of the dataset
${\cal D}$. Hence, if we draw datasets from a distribution $\mu$, the outcome
of $\hat{r}$ becomes probabilistic. In the following, we introduce two
probability distributions $\mu_{1}$ and $\mu_{2}$ over $(X,Y,M)$ such that for
random draws of the dataset from $\mu_{i}$, the conditional probability of
such optimal deferral label $\hat{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. 63], 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 ${\cal D}=\\{(x_{i},y_{i},m_{i})\\}_{i=1}^{n}$
that contains i.i.d. samples from the distribution $\mu_{XYM}$. 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 problem

$\displaystyle\min_{\hat{r}_{i}\in[0,1]}\sum_{i=1}^{n}\mathds{1}_{m_{i}\neq
y_{i}}\hat{r}_{i}+\mathds{1}_{h(x_{i})\neq y_{i}}\big{(}1-\hat{r}_{i}\big{)}.$

It is easy to see that the solution to this problem is given by
$\hat{r}_{i}=0$ if $\mathds{1}_{h(x_{i})\neq y_{i}}<\mathds{1}_{m_{i}\neq
y_{i}}$ and $\hat{r}_{i}=1$ if $\mathds{1}_{h(x_{i})\neq
y_{i}}>\mathds{1}_{m_{i}\neq y_{i}}$. As a result, the optimal deferral is
obtained as

$\displaystyle\hat{r}_{i}=\left\\{\begin{array}[]{cc}1&m_{i}=y_{i}\,,\,h(x_{i})\neq
y_{i}\\\ 0&m_{i}\neq y_{i},\,h(x_{i})=y_{i}\\\ \text{any value in
}[0,1]&o.w.\end{array}\right..$ (37)

Among all the possible policies, we can choose

$\displaystyle\hat{r}_{i}=\left\\{\begin{array}[]{cc}1&m_{i}=y_{i}\,\&\,h(x_{i})\neq
y_{i}\\\ 0&o.w.\end{array}\right..$

Next, we assume that we have a classifier $h$ and two probability
distributions $\mu_{1}$ and $\mu_{2}$ over $(X,Y,M)$. For both distributions
$X$ is uniformly distributed over $[0,1]$, and we have
${\mu_{1}(Y=M,h(X)=Y)=\frac{2}{3}},\mu_{1}(Y=M,h(X)\neq Y){=\frac{1}{3}}$ and
${\mu_{2}(Y\neq M,h(X)=Y)=\frac{2}{3}},\mu_{2}(Y=M,h(X)\neq Y){=\frac{1}{3}}$.
We can see that although the observed $\hat{r}$s are fixed for a given choice
of ${\cal D}$, since ${\cal D}$ is randomly drawn, $\hat{r}$ values are
randomly distributed. Furthermore, the distribution of $\mathbb{P}(\hat{r}|X)$
is according to $Bern(\frac{1}{3})$, since in both cases we have
$\mu_{i}(Y=M,h(X)\neq Y)=\frac{1}{3}$. However, the optimal deferral rule for
the first distribution is $r^{*}_{1}(x)=1$ for all $x\in{\cal X}$, since we
have $L_{\mathrm{def}}^{\mu_{1}}(h,r^{*}_{1})=0$, while for the second case
the optimal deferral rule is $r^{*}_{2}(x)=0$ for all $x\in{\cal X}$ because
we have $L_{\mathrm{def}}^{\mu_{2}}(h,r^{*}_{2})=\frac{1}{3}$. Furthermore,
such deferral rules are not interchangeable, because we have
${L_{\mathrm{def}}^{\mu_{1}}(h,r^{*}_{2})=L_{\mathrm{def}}^{\mu_{2}}(h,r^{*}_{1})=\frac{2}{3}}$.
As a result, $\mathbb{P}(\hat{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 F.2 (Impossibility of generalization of deferral labels).

For every deterministic deferral rule $\hat{r}$ for empirical distributions
and based on the two losses $\mathds{1}_{m\neq y}$ and $\mathds{1}_{h(x)\neq
y}$, there exist two probability measures $\mu_{1}$ and $\mu_{2}$ on ${\cal
X}\times{\cal Y}\times{\cal M}$ such that the corresponding $(\hat{r},X)$ for
both measures is distributed equally. However, the optimal deferral
$r^{*}_{\mu_{1}}$ and $r^{*}_{\mu_{2}}$ for these measures are not
interchangeable, that is
$L_{\mathrm{def}}^{\mu_{i}}(h,r^{*}_{\mu_{i}})\leq\frac{1}{3}$ while
$L_{\mathrm{def}}^{\mu_{i}}(h,r^{*}_{\mu_{j}})=\frac{2}{3}$ for $i=1,2$ and
$j\neq i$.

###### Proof.

As mentioned in (37), there are four possibilities of a deterministic deferral
rule for empirical distribution based on the events $h(X)\neq Y$ and $M\neq
Y$. The reason is that

$\displaystyle\hat{r}=\left\\{\begin{array}[]{cc}1&h(x)\neq y\,,\,m=y\\\
0&h(x)=y\,,\,m\neq y\\\ a&h(x)\neq y\,,\,m\neq y\\\
b&h(x)=y\,,\,m=y\end{array}\right.,$

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. 1.

$\mathbf{a=1,b=0}$: In this case we have

$\displaystyle\hat{r}=\left\\{\begin{array}[]{c c}1&h(x)\neq y\\\
0&o.w.\end{array}\right..$

If we define a measure $\mu_{1}$ such that

$\displaystyle\mu_{1}\big{(}h(X)\neq
Y,M=Y\big{)}=\frac{1}{3},~{}~{}\mu_{1}\big{(}h(X)=Y,M\neq Y)=\frac{2}{3},$

and a measure $\mu_{2}$ such that

$\displaystyle\mu_{2}\big{(}h(X)\neq
Y,M=Y\big{)}=\frac{1}{3},~{}~{}\mu_{2}\big{(}h(X)=Y,M=Y\big{)}=\frac{2}{3},$

then on one hand one can see that $\hat{r}$ is according to
$Bern(\frac{1}{3})$ in both cases. On the other hand, because the probability
of classifier accuracy is larger than human accuracy in $\mu_{1}$ and is
smaller than human accuracy in $\mu_{2}$, we have $r^{*}_{\mu_{1}}(x)=0$ while
$r^{*}_{\mu_{2}}(x)=1$. Therefore, we conclude that

$\displaystyle L_{\mathrm{def}}^{\mu_{1}}(r^{*}_{\mu_{1}},h)=\frac{1}{3},$

and

$\displaystyle L_{\mathrm{def}}^{\mu_{2}}(r^{*}_{\mu_{2}},h)=0,$

while the losses with interchanging deferral policies are equal to

$\displaystyle
L_{\mathrm{def}}^{\mu_{1}}(r^{*}_{\mu_{2}},h)=L_{\mathrm{def}}^{\mu_{2}}(r^{*}_{\mu_{1}},h)=\frac{2}{3}.$

  2. 2.

$\mathbf{a=0,b=1}$: In this case, the deferral rule is as

$\displaystyle\hat{r}=\left\\{\begin{array}[]{cc}0&m\neq y\\\
1&o.w.\end{array}\right..$

Next, if we set two probability measures $\mu_{1}$ and $\mu_{2}$ such that

$\displaystyle\mu_{1}\big{(}M\neq
Y,h(X)=Y\big{)}=\frac{1}{3},~{}~{}\mu_{1}\big{(}M=Y,h(X)\neq Y)=\frac{2}{3},$

and

$\displaystyle\mu_{2}\big{(}M\neq
Y,h(X)=Y\big{)}=\frac{1}{3},~{}~{}\mu_{2}\big{(}M=Y,h(X)=Y\big{)}=\frac{2}{3},$

then $\hat{r}$ is according to $Bern(\frac{2}{3})$ in both cases. However,
$r^{*}_{\mu_{1}}=1$ while $r^{*}_{\mu_{2}}=0$. Furthermore, the expected
deferral losses are equal to

$\displaystyle
L_{\mathrm{def}}^{\mu_{1}}(r^{*}_{\mu_{1}},h)=\frac{1}{3},~{}~{}L_{\mathrm{def}}^{\mu_{2}}(r^{*}_{\mu_{2}},h)=0,$

while after interchanging the deferral policies we have

$\displaystyle
L_{\mathrm{def}}^{\mu_{1}}(r^{*}_{\mu_{2}},h)=L_{\mathrm{def}}^{\mu_{2}}(r^{*}_{\mu_{1}},h)=\frac{2}{3}.$

  3. 3.

$\mathbf{a=1,b=1}$: In this case, the deferral rule is as

$\displaystyle\hat{r}=\left\\{\begin{array}[]{cc}0&h(x)=y,m\neq y\\\
1&o.w.\end{array}\right..$

Next, if we set two probability measures $\mu_{1}$ and $\mu_{2}$ such that

$\displaystyle\mu_{1}\big{(}M\neq
Y,h(X)=Y\big{)}=\frac{1}{3},~{}~{}\mu_{1}\big{(}M=Y,h(X)\neq Y)=\frac{2}{3},$

and

$\displaystyle\mu_{2}\big{(}M\neq Y,h(X)=Y\big{)}=\mu_{2}\big{(}M\neq
Y,h(X)\neq Y\big{)}=\mu_{2}(M=Y,h(X)=Y)=\frac{1}{3},$

then we can see that $\hat{r}$ has the distribution $Bern(\frac{2}{3})$.
However, one can find the optimal deferral policies for the true distributions
are $r^{*}_{\mu_{1}}=1$ and $r^{*}_{\mu_{2}}=0$. Furthermore, we have

$\displaystyle L^{\mu_{1}}_{\mathrm{def}}(r^{*}_{\mu_{1}},h)=\frac{1}{3},$

and

$\displaystyle L^{\mu_{2}}_{\mathrm{def}}(r^{*}_{\mu_{2}},h)=\frac{2}{3},$

while

$\displaystyle
L_{\mathrm{def}}^{\mu_{1}}(r^{*}_{\mu_{1}},h)=\frac{1}{3},~{}~{}L_{\mathrm{def}}^{\mu_{2}}(r^{*}_{\mu_{2}},h)=\frac{1}{3}.$

∎

##  Appendix G Proof of Theorem 3.1

Let $\mathcal{X}=\\{x_{1},\ldots,x_{n}\\}$ and $\mathcal{Y}=\\{1,\ldots,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 minimizes

$\displaystyle h^{*}(x)\in\mathop{\rm
argmin}\limits_{\hat{y}}\mathbb{E}_{\mu_{Y|X}}\big{[}\ell_{AI}(Y,\hat{y},X)|X=x\big{]},$

for all $x\in{\cal X}$. This is regardless of whether the deferral occurs or
not. Therefore, this solution is further the solution to

$\displaystyle h^{*}(x)$ $\displaystyle\in\mathop{\rm
argmin}\limits_{\hat{y}}\mathbb{E}_{\mu_{Y|X}}\big{[}(1-r(X))\ell_{AI}(Y,\hat{y},X)|X=x\big{]}$
$\displaystyle=\mathop{\rm
argmin}\limits_{\hat{y}}\mathbb{E}_{\mu_{Y,M|X}}\big{[}(1-r(X))\ell_{AI}(Y,\hat{y},X)+r(X)\ell_{H}(Y,M,X)|X=x\big{]},$

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 which
$\mathbb{E}_{\mu_{Y|X}}\big{[}\ell_{AI}(Y,1,X)|X=x\big{]}>\mathbb{E}_{\mu_{Y|X}}\big{[}\ell_{AI}(Y,0,X)|X=x\big{]}$
for all $x\in\mathcal{X}$, and therefore $h(x)=1$ over all input space.
Further, we assume the data distribution has the property
$\mu_{XYM}=\mu_{XY}\delta(M=Y)$, i.e. $M=Y$ on all the data. In this case, we
know that

$\displaystyle\mathbb{E}\big{[}\ell_{H}(Y,M,X)|X=x_{i}\big{]}=\mathbb{E}\big{[}\mathds{1}_{M\neq
Y}|X=x_{i}\big{]}=0,$

and we define

$\displaystyle\mathbb{E}\big{[}\ell_{AI}(Y,h(X),X)|X=x_{i}\big{]}=\mathbb{E}\big{[}\mathds{1}_{Y\neq
1}|X=x_{i}\big{]}=\ell_{i}.$

Now, if we set $\mathbb{P}(X=x_{i})=p_{i}$, and $r(x_{i})=r_{i}$, then the
optimization problem

$\displaystyle f^{*}=\mathop{\rm argmin}\limits_{r(\cdot)\in\\{0,1\\}^{{\cal
X}}}L^{\mu}_{\mathrm{def}}(h,r),$

is equivalent to

$\displaystyle\mathop{\rm
argmin}\limits_{r_{i}\in\\{0,1\\}}\sum_{i=1}^{n}p_{i}\times 0\times
r_{i}+p_{i}\times(1-r_{i})\times\ell_{i},~{}~{}~{}~{}s.t.~{}~{}\sum_{i=1}^{n}p_{i}r_{i}\leq
b,$

that is equivalent to

$\displaystyle\mathop{\rm
argmax}\limits_{r_{i}\in\\{0,1\\}}\sum_{i=1}^{n}p_{i}r_{i}\ell_{i},~{}~{}~{}s.t.~{}\sum_{i=1}^{n}p_{i}r_{i}\leq
b.$ (38)

Next, 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 [55]). Let

$\displaystyle\mathop{\rm
argmax}\limits_{r_{i}\in\\{0,1\\}}\sum_{i=1}^{n}r_{i}c_{i},~{}~{}~{}s.t.~{}~{}\sum_{i=1}^{n}w_{i}r_{i}\leq
K,$ (39)

be an instance of the $0-1$ knapsack problem 777Note that in case that
$w_{i}=0$ the Knapsack problem has a degenerate solution of $r_{i}=1$. Hence,
we could drop that point and without loss of generality assume that $w_{i}$ is
non-zero. with $w_{i},c_{i}>0$, $i\in[n]$, and $K>0$. With
$\ell_{i}=\frac{c_{i}/w_{i}}{\sum_{i=1}^{n}c_{i}/w_{i}}$,
$p_{i}=\frac{w_{i}}{\sum_{i=1}^{n}w_{i}}$ and
$b=\frac{K}{\sum_{i=1}^{n}w_{i}}$, problem (39) can be written in the form of
(38). Because of $\sum_{i=1}^{n}l_{i}=\sum_{i=1}^{n}p_{i}=1$ this yields
indeed a valid problem.

##  Appendix H Proof of Theorem 4.1

We start this proof by introducing a few useful lemmas:

######  Lemma H.1.

The set ${\cal F}=\Delta_{n}^{{\cal X}}$ of all functions that map ${\cal X}$
to an $n-$dimensional probability is weakly compact, i.e., for each sequence
$\\{f_{n}\\}_{n=1}^{\infty}$, there is a sub-sequence $\\{f_{n_{i}}\\}$ and a
function $f^{*}\in{\cal F}$ such that for all measurable embedding functions
$\psi$, we have

$\displaystyle\lim_{k\to\infty}\mathbb{E}\big{[}\langle
f_{n_{k}},\psi\rangle\big{]}=\mathbb{E}\big{[}\langle
f^{*},\psi\rangle\big{]}.$

###### Proof.

We know that all components of each element of the function sequence is
bounded by $1$. We define $\\{f_{m}^{i}\\}_{m=1}^{\infty}$ as the sequence of
the $i$th component of the function sequence. Therefore, using [39, Theorem
A.5.1] we know that there is a sub-sequence
$\\{f_{m_{k}^{1}}^{1}\\}_{k=1}^{\infty}$ and a non-negative $1$-bounded
function $f^{*}_{1}$, such that for each $\mu$-integrable function
$\psi_{1}(x)$ we have

$\displaystyle\lim_{k\to\infty}\mathbb{E}_{\mu}\big{[}f_{m_{k}}^{1}(x)\psi_{1}(x)\big{]}=\mathbb{E}_{\mu}\big{[}f^{*}_{1}(x)\psi_{1}(x)\big{]}.$

Next, we can repeat the same process for
$\\{f_{m^{1}_{k}}^{i}\\}_{k=1}^{\infty}$ where $i\in[2:n]$, and we can find a
sub-sequence $m_{k}^{i+1}$ of $m^{i}_{k}$ and a non-negative $1-$bounded
function $f^{*}_{i+1}$ for which

$\displaystyle\lim_{k\to\infty}\mathbb{E}_{\mu}\big{[}f_{m^{i+1}_{k}}^{i+1}(x)\psi_{i+1}(x)\big{]}=\mathbb{E}_{\mu}\big{[}f^{*}_{i+1}(x)\psi_{i+1}(x)\big{]}.$

Now, since all sub-sequences of a converging sequence converges to the same
limit, we can use $m_{k}^{n}$ that is the intersection of all sequences and
show that

$\displaystyle\lim_{k\to\infty}\mathbb{E}_{\mu}\big{[}f_{m^{n}_{k}}^{i}(x)\psi_{i}(x)\big{]}=\mathbb{E}_{\mu}\big{[}f^{*}_{i}(x)\psi_{i}(x)\big{]},$

for all $i\in[1:n]$ and integrable functions $\psi_{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 that

$\displaystyle\lim_{k\to\infty}\mathbb{E}\big{[}\langle
f_{m_{k}^{n}},\psi\rangle\big{]}$
$\displaystyle=\lim_{k\to\infty}\mathbb{E}\big{[}\sum_{i=1}^{n}f_{m_{k}^{n}}^{n}(x)\psi_{i}(x)\big{]}=\sum_{i=1}^{n}\lim_{k\to\infty}\mathbb{E}\big{[}f_{m_{k}^{n}}^{n}(x)\psi_{i}(x)\big{]}$
$\displaystyle=\sum_{i=1}^{n}\mathbb{E}_{\mu}\big{[}f^{*}_{i}(x)\psi_{i}(x)\big{]}=\mathbb{E}_{\mu}\big{[}\langle
f^{*}(x),\psi(x)\rangle\big{]}.$

Next, we need to show that $f^{*}\in{\cal 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 $\mu(A)>0$ and there exists
$l>0$ such that $|\sum_{i}f^{*}_{i}-1|\geq l$ for all $x\in A$. We know that
there is either a subset $B\subseteq A$ with $\mu(B)>0$ such that for all
$x\in B$ we have $\sum_{i}f^{*}_{i}(x)\geq 1+l$, or similarly a subset for
which $\sum_{i}f^{*}_{i}(x)\leq 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
$\sum_{i}f^{*}_{i}(x)\geq 1+l$ for $x\in B$. Now, if we define
$\hat{\psi}(x)=[1,\ldots,1]$ for $x\in B$ and otherwise
$\hat{\psi}(x)=[0,\ldots,0]$, then we have

$\displaystyle\mathbb{E}_{\mu}\big{[}\langle
f^{*}(x),\hat{\psi}(x)\rangle\big{]}\geq(1+l)\mu(B),$

while

$\displaystyle\mathbb{E}_{\mu}\big{[}\langle
f_{m_{k}^{n}}(x),\psi\rangle\big{]}=1,$

for all $k\in\mathbb{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 ${\cal C}$ of prediction functions for which
$\mathbb{E}\big{[}\langle f(x),\psi_{i}(x)\rangle\big{]}=\delta_{i}$ for
$i\in[1:m]$, we show that the supremum of the objective function
$\mathbb{E}\big{[}\langle f(x),\psi_{0}(x)\rangle\big{]}$ is a maximum, (ii)
we show that it is sufficient for a predictor $f\in{\cal C}$ to be in form of
(8) to achieve the maximum objective $\mathbb{E}\big{[}\langle
f(x),\psi_{0}(x)\rangle\big{]}$ in ${\cal C}$ and also for all predictors with
$\mathbb{E}\big{[}\langle f(x),\psi_{i}(x)\rangle\big{]}\leq\delta_{i}$, (iii)
we show that the space of all possible constraints for any prediction function
in $\Delta_{d}^{{\cal X}}$ 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 ${\cal 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
$\epsilon>0$, there exists a function $f_{\epsilon}$ in ${\cal C}$ such that
$\mathbb{E}\big{[}\langle
f_{\epsilon},\psi_{0}(x)\rangle\big{]}\geq\sup_{f\in{\cal
C}}\mathbb{E}\big{[}\langle f,\psi_{0}(x)\rangle\big{]}-\epsilon$.
Equivalently, there is a sequence of functions $f_{n}$ for which
$\lim_{n\to\infty}\mathbb{E}\big{[}\langle
f_{n},\psi_{0}(x)\rangle\big{]}=\sup_{f\in{\cal C}}\mathbb{E}\big{[}\langle
f,\psi_{0}(x)\rangle\big{]}$. Using weakly-compactness of the function class
$\Delta_{n+1}^{{\cal X}}$ as in Lemma H.1, we know that for the sequence
$f_{n}$, there exists a subsequence $f_{n_{k}}$ and a function
$f^{*}\in\Delta_{n+1}^{{\cal X}}$ such that

$\displaystyle\lim_{k\to\infty}\mathbb{E}\big{[}\langle
f_{n_{k}},\psi_{m+1}(x)\rangle\big{]}=\mathbb{E}\big{[}\langle
f^{*}(x),\psi_{m+1}(x)\rangle\big{]}.$

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}$ [56, Chapter 2, Theorem 1]. Therefore, we have

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}(x),\psi_{m+1}(x)\rangle\big{]}=\sup_{f\in{\cal
C}}\mathbb{E}\big{[}\langle f,\psi_{m+1}(x)\rangle\big{]},$

which means that the supremum of the objective is achievable by $f^{*}$.

Moreover, for $\psi_{i}(x)$ where $i\in[1:m]$, we have
$\mathbb{E}\big{[}\langle f_{n},\psi_{i}(x)\rangle\big{]}=\delta_{i}$ for all
$n$, which concludes

$\displaystyle\delta_{i}=\lim_{k\to\infty}\mathbb{E}\big{[}\langle
f_{n_{k}},\psi_{i}(x)\rangle\big{]}=\mathbb{E}\big{[}\langle
f^{*}(x),\psi_{i}(x)\rangle\big{]}.$

This means that the equality constraints holds for $f^{*}$, i.e.,
$f^{*}\in{\cal C}$, if it holds for each predictor $f_{n}$.

  * •

Step (ii): Assume that there is a predictor $\hat{f}$ such that
$\mathbb{E}\big{[}\langle\hat{f},\psi_{i}\rangle\big{]}\leq\delta_{i}$. In
this step, we show that if exists a predictor $f$ in form of (8) and in ${\cal
C}$, then $\hat{f}$ always has smaller objective than $\hat{f}$. To that end,
consider the following expression:

$\displaystyle A=\mathbb{E}\big{[}\langle
f(x)-\hat{f}(x),\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x)\rangle\big{]}.$

Now, we know that

$\displaystyle\mathbb{E}\big{[}\langle
f(x)-\hat{f}(x),\sum_{i=1}^{m}k_{i}\psi_{i}(x)\rangle\big{]}$
$\displaystyle=\sum_{i=1}^{m}k_{i}\Big{(}\mathbb{E}\big{[}\langle
f(x),\psi_{i}(x)\rangle\big{]}-\mathbb{E}\big{[}\langle\hat{f}(x),\psi_{i}(x)\rangle\big{]}\Big{)}$
$\displaystyle\overset{(a)}{=}\sum_{i=1}^{m}k_{i}\Big{(}\delta_{i}-\mathbb{E}\big{[}\langle\hat{f}(x),\psi_{i}(x)\rangle\big{]}\Big{)}\geq
0,$

where $(a)$ holds because $f\in{\cal C}$. As a result, if $A\geq 0$, then we
could show that

$\displaystyle\mathbb{E}\big{[}\langle
f(x)-\hat{f}(x),\psi_{0}(x)\rangle\big{]}\geq 0,$ (40)

and complete the proof.

To that end, first note that both $f$ and $\hat{f}$ are in $\Delta_{d}^{{\cal
X}}$, and therefore

$\displaystyle\langle
f(x),[1,\ldots,1]\rangle=\langle\hat{f}(x),[1,\ldots,1]\rangle=1.$

As a result, for any fixed scalar $c$, we have

$\displaystyle\langle
f(x)-\hat{f}(x),\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x)\rangle=\langle
f(x)-\hat{f}(x),\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x)-c\rangle.$ (41)

Next, we fix $c$ to be the maximum component of the vector
$\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x)$, i.e.,

$\displaystyle
c:=\max_{i\in[1:d]}\\{\psi_{0}^{i}(x)-\sum_{j=1}^{m}k_{j}\psi_{j}^{i}(x)\\}.$

Now, we rewrite $A$ using (41) as

$\displaystyle A$ $\displaystyle=\mathbb{E}\Big{[}\langle
f(x)-\hat{f}(x),\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x)-c\rangle\Big{]}$
$\displaystyle=\sum_{i=1}^{d}\mathbb{E}\Big{[}(f_{i}(x)-\hat{f}_{i}(x))(\psi_{0}^{i}(x)-\sum_{j=1}^{m}k_{j}\psi_{j}^{i}(x)-c)\rangle\Big{]}$

Now, we consider two cases for which $E_{1}^{i}(x):f_{i}(x)>\hat{f}_{i}(x)$,
and $E_{2}^{i}(x):f_{i}(x)\leq\hat{f}_{i}(x)$. If $f_{i}(x)>\hat{f}_{i}(x)$,
then we have $f_{i}(x)>0$, because $1\geq\hat{f}_{i}(x)\geq 0$ for all
$i\in[1:d]$. Therefore, using the definition of ${\cal S}_{d}$ and because
$f\in{\cal S}_{d}$ we have

$\displaystyle\psi_{0}^{i}(x)-\sum_{j=1}^{m}k_{j}\psi_{j}^{i}(x)=\max_{i\in[1:d]}\big{\\{}\psi_{0}^{i}(x)-\sum_{j=1}^{m}k_{j}\psi_{j}^{i}(x)\big{\\}}=c.$
(42)

Consequently, we have

$\displaystyle
A=\sum_{i=1}^{d}\mathbb{E}\Big{[}(f_{i}(x)-\hat{f}_{i}(x))(\psi_{0}^{i}(x)-\sum_{j=1}^{m}k_{j}\psi_{j}^{i}(x)-c)\rangle\Big{]}$
$\displaystyle=\sum_{i=1}^{d}\mathbb{E}\Big{[}(f_{i}(x)-\hat{f}_{i}(x))(\psi_{0}^{i}(x)-\sum_{j=1}^{m}k_{j}\psi_{j}^{i}(x)-c)\rangle|E_{1}^{i}(x)\Big{]}\mathbb{P}\big{(}E_{1}^{i}(x)\big{)}$
$\displaystyle+\sum_{i=1}^{d}\mathbb{E}\Big{[}(f_{i}(x)-\hat{f}_{i}(x))(\psi_{0}^{i}(x)-\sum_{j=1}^{m}k_{j}\psi_{j}^{i}(x)-c)\rangle|E_{2}^{i}(x)\Big{]}\mathbb{P}\big{(}E_{2}^{i}(x)\big{)}$
$\displaystyle\overset{(a)}{=}\sum_{i=1}^{d}\mathbb{E}\Big{[}(f_{i}(x)-\hat{f}_{i}(x))(\psi_{0}^{i}(x)-\sum_{j=1}^{m}k_{j}\psi_{j}^{i}(x)-c)\rangle|E_{2}^{i}(x)\Big{]}\mathbb{P}\big{(}E_{2}^{i}(x)\big{)}$
$\displaystyle\overset{(b)}{\geq}0,$

where $(a)$ holds due to (42) and $(b)$ holds because
$f_{i}(x)\leq\hat{f}_{i}(x)$ and
$\psi_{m+1}^{i}(x)-\sum_{j=1}^{m}k_{j}\psi_{j}^{i}(x)\leq
c=\max_{i\in[1:n+1]}\\{\psi_{m+1}^{i}(x)-\sum_{j=1}^{m}k_{j}\psi_{j}^{i}(x)\\}$.
As a result, we have $A\geq 0$ that concludes (40) and completes the proof of
this step.

$v$$M$$v^{**}$$v^{*}$$v^{\prime}$$\overline{v}^{**}$$\overline{v}^{*}$$\overline{v}$
Figure 3: If an interior point of ${\cal N}$ has one corresponding point at
$M$, then so are all interior points of $N$

  * •

Step (iii): In this step, we show that the space of joint set of expected
inner-products

$\displaystyle{\cal G}=\Big{\\{}\big{(}\mathbb{E}[\langle
f(x),\psi_{1}(x)\rangle],\ldots,\mathbb{E}[f(x),\psi_{m}(x)]\big{)}:\,f\in\Delta_{d}^{{\cal
X}}\\},$

is compact under Euclidean metric, and convex.

To show the compactness of that space, assume that there is a sequence
$\\{g_{n}\\}_{n=1}^{\infty}$ such that $\lim_{n\to\infty}g_{n}=g$, or
accordingly there is a sequence of $f_{n}\in\Delta_{d}^{{\cal X}}$ for which
$\lim_{n\to\infty}\big{(}\mathbb{E}[\langle
f_{n}(x),\psi_{1}(x)\rangle],\ldots,\mathbb{E}[f_{n}(x),\psi_{m}(x)]\big{)}=(g_{1},\ldots,g_{m})$.
Since the metric is Euclidean, this is equivalent to
$\lim_{n\to\infty}\mathbb{E}[\langle f_{n}(x),\psi_{i}(x)\rangle]=g_{i}$ for
all $i\in[1:m]$. The weak compactness of $\Delta_{d}^{{\cal X}}$, as proved in
Lemma H.1, shows that there exists $f^{*}$ and a sub-sequence $f_{n_{k}}$ such
that $\lim_{k\to\infty}\mathbb{E}[\langle
f_{n_{k}}(x),\psi_{i}(x)\rangle]=\mathbb{E}[\langle f^{*},\psi_{i}(x)\rangle]$
for all $i\in[1:d]$. Therefore, because of the choice of Euclidean metric, we
have

$\displaystyle\lim_{k\to\infty}\Big{(}\mathbb{E}[\langle
f_{n_{k}}(x),\psi_{1}(x)\rangle],$ $\displaystyle\ldots,\mathbb{E}[\langle
f_{n_{k}}(x),\psi_{m}(x)\rangle]\Big{)}$
$\displaystyle=\Big{(}\mathbb{E}[\langle
f^{*},\psi_{1}(x)\rangle],\ldots,\mathbb{E}[\langle
f^{*},\psi_{m}(x)\rangle]\Big{)},$

which is equivalent to compactness of ${\cal G}$.

To show the convexity of ${\cal G}$, it is enough to prove the convexity of
$\Delta_{d}^{{\cal X}}$. The reason is that $g(f)=\big{(}\mathbb{E}[\langle
f(x),\psi_{1}(x)\rangle],\ldots,\mathbb{E}[f(x),\psi_{m}(x)]\big{)}$ is a
linear functional of $f$, and a linear functional images a convex set to
another convex set.

To prove the convexity of $\Delta_{d}^{{\cal X}}$, let
$f,f^{\prime}\in\Delta_{d}^{{\cal X}}$. This means that
$f_{i}(x),f_{i}^{\prime}(x)\in[0,1]$ for all $i\in[1:d]$ and
$\sum_{i=1}^{d}f_{i}(x)=\sum_{i=1}^{d}f_{i}^{\prime}(x)=1$. Consequently,
$af_{i}(x)+(1-a)f_{i}^{\prime}(x)\geq 0$, since $a,1-a\geq 0$. Moreover,
$\sum_{i=1}^{d}af_{i}(x)+(1-a)f^{\prime}_{i}(x)=a\sum_{i=1}^{d}f_{i}(x)+(1-a)\sum_{i=1}^{d}f_{i}^{\prime}(x)=a+1-a=1$.
As a result of these two facts, $af+(1-a)f^{\prime}\in\Delta_{d}^{{\cal X}}$,
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 ${\cal C}$ achieves its
supremum in terms of objective $\mathbb{E}\big{[}\langle
f(x),\psi_{0}(x)\big{]}$ if and only if it is in form of (8) almost
everywhere. This is an extension to [19, 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 ${\cal
C}$ maximizes the objective, then it is in form of (8).

Firstly, using Step (iii), we know that the space ${\cal N}$ of all points
$\big{(}\mathbb{E}[\langle
f(x),\psi_{1}(x)\rangle],\ldots,\mathbb{E}[f(x),\psi_{m}(x)]\big{)}$ and the
space ${\cal M}$ of all points $\big{(}\mathbb{E}[\langle
f(x),\psi_{1}(x)\rangle],\ldots,\mathbb{E}[f(x),\psi_{0}(x)]\big{)}$ are
compact and convex. Now, assume that $v=(\delta_{1},\ldots,\delta_{m})$ is an
interior point of ${\cal N}$. Then, the corresponding set in ${\cal M}$, i.e.,
$B_{v}=\\{(\delta_{0},\ldots,\delta_{m})\in{\cal
M}:\delta_{0}\in\mathbb{R}\\}$ has a supremum and an infimum of the first
component that we name $\delta^{**}$ and $\delta^{*}$. Now, since ${\cal M}$
is compact, then $v^{**}=(\delta^{**},\delta_{1},\ldots,\delta_{m})$ and
$v^{*}=(\delta^{*},\delta_{1},\ldots,\delta_{m})$ are contained in ${\cal M}$.
Next, assume the following two cases:

    1. 1.

$\delta^{**}=\delta^{*}$: In this case for all other points
$\overline{v}=(\overline{\delta}_{1},\ldots,\overline{\delta}_{m})$ of ${\cal
N}$, the corresponding set $B_{v^{\prime}}$ in ${\cal M}$ is a single point.
The reason is that, if it is not so, then we have two points
$\overline{v}^{**}=(\overline{\delta}^{**},\overline{\delta}_{1},\ldots,\overline{\delta}_{m})$
and
$\overline{v}^{*}=(\overline{\delta}^{*},\overline{\delta}_{1},\ldots,\overline{\delta}_{m})$
where $\overline{\delta}^{**}>\overline{\delta}^{*}$. Now, since $v$ is an
interior point of ${\cal N}$, then on any direction in a small neighborhood
around $v$ there exists a point $v^{\prime}$ within ${\cal N}$. Let that
direction be opposite the connecting line of $v$ and $\overline{v}$, i.e., let
$v$ be on a connecting line of $v^{\prime}$ and $\overline{v}^{*}$. Now, make
a convex hull using the three points $v^{\prime}$, $\overline{v}^{**}$, and
$\overline{v}^{*}$, which are all in ${\cal M}$. Because of the convexity of
${\cal M}$, the convex hull is also a subset of ${\cal M}$. Since $v$ is an
interior point of the convex hull, this means that a neighborhood of $v$ along
any direction is inside ${\cal M}$. Now, if we set $(m+1)$th axis to be that
direction, we contradict with the fact that $\delta^{*}=\delta^{**}$. (See
Figure 3)

Now, we know that in such case all points within ${\cal N}$ have one
corresponding point in ${\cal M}$. Because of the convexity of ${\cal M}$ this
is equivalent to ${\cal M}$ being a subset of a hyperplane with the generating
formula $x_{0}=\sum_{i=1}^{m}k_{i}x_{i}+k_{0}$. Therefore, we have
$\mathbb{E}\big{[}\langle f,\psi_{0}\rangle\big{]}=\mathbb{E}\big{[}\langle
f,\sum_{i=1}^{m}k_{i}\psi_{i}\rangle\big{]}+k_{0}$ for all
$f\in\Delta_{d}^{{\cal X}}$. Therefore, for $d\geq 2$, if we set
$f_{1}=(\tfrac{p(x)}{d-2},\ldots,\tfrac{p(x)}{d-2},\underbrace{1-p(x)}_{i},\tfrac{p(x)}{d-2},\ldots,\underbrace{0}_{j},\tfrac{p(x)}{d-2},\ldots,\tfrac{p(x)}{d-2})$
and
$f_{2}=(\tfrac{p(x)}{d-2},\ldots,\tfrac{p(x)}{d-2},\underbrace{0}_{i},\tfrac{p(x)}{d-2},\ldots,\underbrace{1-p(x)}_{j},\tfrac{p(x)}{d-2},\ldots,\tfrac{p(x)}{d-2})$
for $p(x)\in[0,1]^{{\cal X}}$ , then we have

$\displaystyle\mathbb{E}\big{[}\langle
f_{1},\psi_{0}\rangle\big{]}-\mathbb{E}\big{[}\langle
f_{1},\sum_{i=1}^{m}k_{i}\psi_{i}\rangle\big{]}=\mathbb{E}\big{[}\langle
f_{2},\psi_{0}\rangle\big{]}-\mathbb{E}\big{[}\langle
f_{2},\sum_{i=1}^{m}k_{i}\psi_{i}\rangle\big{]},$

or equivalently

$\displaystyle\mathbb{E}\big{[}(1-p(x))(\psi_{0}^{i}(x)-\sum_{t=1}^{m}k_{t}\psi_{t}^{i}(x)-\psi_{m+1}^{j}(x)+\sum_{t=1}^{m}k_{t}\psi_{t}^{j}(x))\big{]}=0,$

for all function $p(x)\in\Delta_{d}^{{\cal X}}$. 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

$\displaystyle\psi_{0}^{i}(x)-\sum_{t=1}^{m}k_{t}\psi_{t}^{i}(x)=\psi_{0}^{j}(x)-\sum_{t=1}^{m}k_{t}\psi_{t}^{j}(x),$

for all $i\neq j\in[1:d]$, and consequently

$\displaystyle\psi_{0}^{i}(x)-\sum_{t=1}^{m}k_{t}\psi_{t}^{i}(x)=\max_{j\in[1:d]}\\{\psi_{0}^{j}(x)-\sum_{t=1}^{m}k_{t}\psi_{t}^{j}(x)\\},$

for all $i\in[1:n+1]$. As a result, there is a set of $k_{1},\ldots,k_{m}$
such that $\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x)$ has equal components
almost everywhere. As a result, due to the freedom of choice for
$\tau(\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x),x)$ where $\tau\in{\cal
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
$\tau(\psi_{m+1}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x),x)$.

    2. 2.

$\delta^{**}>\delta^{*}$: In such case, for all
$\delta_{0}\in[\delta^{*},\delta^{**}]$, we can show that
$v=(\delta_{0},\ldots,\delta_{m})$ is an interior point of ${\cal M}$. To show
that, we first find $m$ points $v^{\prime}_{1},\ldots,v^{\prime}_{m}\in{\cal
N}$ that are linearly independent and such that their convex hull include
$(\delta_{1},\ldots,\delta_{m})$. Using the definition of ${\cal M}$, for each
of these points
$v^{\prime}_{i}=({\delta^{\prime}_{1}}^{i},\ldots,{\delta^{\prime}_{m}}^{i})$,
there exists $h^{\prime}_{i}\in\mathbb{R}$ such that
$v^{\prime\prime}_{i}=(h^{\prime}_{i},{\delta^{\prime}_{1}}^{i},\ldots,{\delta^{\prime}_{m}}^{i})$
is within ${\cal M}$. Now, we add the two points $v^{**}$ and $v^{*}$ to these
sets of points. It is easy to see that $v^{\prime\prime}_{i}$s are linearly
independent. Furthermore, we know that $(\delta_{1},\ldots,\delta_{m})$ is a
convex combination of $v^{\prime}_{i}$s, i.e.,
$\sum_{i}a_{i}v^{\prime}_{i}=(\delta_{1},\ldots,\delta_{m})$. As a result, if
$\sum_{i}b_{i}v^{\prime\prime}_{i}-v^{**}=(0,\ldots,0)$, then we have
$b_{i}=a_{i}$ for $i\in[1:m]$. Furthermore, we have $\sum
a_{i}h^{\prime}_{i}=\sum b_{i}h^{\prime}_{i}=\delta^{**}$. Similarly, if
$\sum_{i}c_{i}v^{\prime\prime}_{i}-v^{*}=(0,\ldots,0)$ we have $c_{i}=a_{i}$
and $\sum a_{i}h^{\prime}_{i}=\sum c_{i}h^{\prime}_{i}=\delta^{*}$. As a
result, since $\delta^{*}\neq\delta^{**}$ at least one of these cases would
not occur, or equivalently, the dimension of the convex hull of
$v^{\prime\prime}_{1},\ldots v^{\prime\prime}_{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
${\cal M}$.

Now, since $v^{**}$ is a border point in ${\cal M}$ and due to the convexity
of ${\cal M}$ there is a hyperplane ${\cal P}$ such that it passes $v^{**}$
and it lays above all points of ${\cal M}$. Since $v$ is an interior point of
${\cal M}$, a neighborhood of $v$ is laid under the hyperplane ${\cal P}$,
hence $v$ cannot be laid on the hyperplane. Therefore, if the generating
formula of such hyperplane is
$\sum_{i=0}^{m}k_{i}x_{i}=\sum_{i=1}^{m}k_{i}\delta_{i}+k_{0}\delta^{**}$,
since $v$ is not laid on the hyperplane we assure that
$\sum_{i=1}^{m}k_{i}\delta_{i}+k_{0}\delta_{0}\neq\sum_{i=1}^{m}k_{i}\delta_{i}+k_{0}\delta^{**}$,
or equivalently $k_{0}\neq 0$. Hence, without loss of generality assume that
$k_{0}=-1$. This shows that for all points in $(u_{0},\ldots,u_{m})\in{\cal
M}$ we have

$\displaystyle
u_{0}-\sum_{i=1}^{m}k_{i}u_{i}\leq\delta^{**}-\sum_{i=1}^{m}k_{i}\delta_{i},$

or equivalently, by the definition of ${\cal M}$, for all prediction function
$f$, we have

$\displaystyle\mathbb{E}\big{[}\langle
f(x),\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x)\rangle\big{]}\leq\delta^{**}-\sum_{i=1}^{m}k_{i}\delta_{i}.$

Assuming that $\hat{f}\in{\cal C}$ maximizes the objective, we have

$\displaystyle\mathbb{E}\big{[}\langle
f(x),\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x)\rangle\big{]}\leq\mathbb{E}\big{[}\langle\hat{f}(x),\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x)\rangle\big{]}.$
(43)

This shows that almost everywhere when there is a unique maximizing component
$j$ in $\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x)$, then $\hat{f}_{j}(x)=1$.
The reason is that otherwise and if there is a set $A$ such that $\mu(A)>0$
and for $x\in A$ and a choice of $l\in[0,1)$, $\epsilon\in\mathbb{R}$, and all
$t\neq j$ we have
$\psi_{m+1}^{j}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}^{j}(x)\geq\epsilon+\psi_{m+1}^{t}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}^{t}(x)$
while $f_{j}\leq 1-l$, then we can make a function $f(x)$ that is
$f(x)=\hat{f}(x)$ for $x\in{\cal X}\setminus A$ and
$f(x)=[0,\ldots,\underbrace{1}_{j},\ldots,0]$ for $x\in A$. Such function
leads to

$\displaystyle\mathbb{E}\big{[}\langle
f(x),\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x)\rangle\big{]}\geq\epsilon
l\mu(A)+\mathbb{E}\big{[}\langle\hat{f}(x),\psi_{0}(x)-\sum_{i=1}^{m}k_{i}\psi_{i}(x)\rangle\big{]},$

that is in contradiction with (43). This completes the proof of this step.

##  Appendix I Proof of Theorem 4.2

In the following, we introduce a few lemmas that are useful in our proofs.

######  Lemma I.1.

For every random variable $X$ on $\mathbb{R}$ we have

$\displaystyle\lim_{\tau\to t^{-}}\mathbb{P}(\tau\leq X<t)=\lim_{\tau\to
t^{+}}\mathbb{P}(t<X<\tau)=0$

###### Proof.

For each increasing sequence $\\{\tau_{i}\\}_{i=1}^{\infty}$ we show that the
first limit is zero, which proves the claim that the function of $\tau$ has a
zero limit.

We define

$\displaystyle{\cal S}_{i}=[\tau_{i},t),$

and notice that

$\displaystyle{\cal S}_{1}\supseteq{\cal S}_{2}\supseteq\ldots.$

Further, we note that

$\displaystyle\bigcap_{i=1}^{\infty}{\cal S}_{i}=\emptyset.$

As a result

$\displaystyle{\cal S}_{1}^{c}\subseteq{\cal S}_{2}^{c}\subseteq\ldots,$

and

$\displaystyle\bigcup_{i=1}^{\infty}{\cal S}_{i}^{c}=\mathbb{R}.$

Next, because probability measure is $\sigma$-additive, we conclude its lower-
semicontinuity [35, Theorem 13.6], and therefore we have

$\displaystyle\lim_{i\to\infty}\mathbb{P}(X\in{\cal
S}_{i}^{c})=\mathbb{P}(X\in\cup_{i=1}^{\infty}{\cal S}_{i}^{c})=1,$

which proves $\lim_{i\to\infty}\mathbb{P}(X\in{\cal S}_{i})=0$.

We could take similar steps to show that since
$\bigcap_{i=1}^{\infty}(t,\tau_{i}^{\prime})=\emptyset$ for decreasing
$\tau_{i}^{\prime}$ we have

$\displaystyle\lim_{i\to\infty}\mathbb{P}(X\in(t,\tau_{i}^{\prime}))=0.$

∎

######  Lemma I.2.

Let $\psi_{1}:{\cal X}\to\mathbb{R}^{d}$ be a bounded function. Further, we
define two functions $C(k)=\mathbb{E}\big{[}\langle
f^{*}_{k,0}(x),\psi_{1}(x)\rangle\big{]}$, $D(k)=\mathbb{E}\big{[}\langle
f^{*}_{k,1}(x),\psi_{1}(x)\rangle\big{]}$, and $F(k)=\mathbb{E}\big{[}\langle
f^{*}_{k,1}(x),\psi_{0}(x)\rangle\big{]}$, where $f^{*}_{k,p}$ is defined in
Theorem 4.2. Then,

  1. 1.

$C(k)$ is monotonically non-increasing,

  2. 2.

$C(k)$ is upper semi-continuous,

  3. 3.

$F(k)$ is monotonically non-decreasing,

  4. 4.

$D(k)$ is lower semi-continuous, and we have

  5. 5.

$\lim_{k^{\prime}\uparrow k}C(k)=\lim_{k^{\prime}\uparrow k}D(k)$

###### Proof.

  1. 1.

Firstly, let us define $\ell_{k}(x)=\psi_{0}(x)-k\psi_{1}(x)$. For the setting
where $p=0$, the prediction function $f^{*}_{k,p}(x)$ is defined as

$\displaystyle
f^{*}_{k,0}(x,p)=\left\\{\begin{array}[]{cc}1&i=\min\\{\mathop{\rm
argmin}\limits_{j\in\mathop{\rm
argmax}\limits\ell_{k}(x)}\big{(}\psi_{1}(x)\big{)}(j)\\}\\\
0&\text{otherwise}\end{array}\right..$ (46)

Further, for $k_{1},k_{2}$ such that $k_{1}\leq k_{2}$, let us define $j_{1}$
and $j_{2}$ as the only non-zero index of $f^{*}_{k_{1},0}(x,p)$ and
$f^{*}_{k_{2},0}(x,p)$, respectively. To show that $C(k)$ is monotonically
non-increasing we only need to show that