$\big{(}\psi_{1}(x)\big{)}(j_{1})=\langle
f_{k_{1},0}^{*}(x),\psi_{1}(x)\rangle\geq\langle
f_{k_{2},0}^{*}(x),\psi_{1}(x)\rangle=\big{(}\psi_{1}(x)\big{)}(j_{2})$.
Assume that this does not occur, or equivalently
$\big{(}\psi_{1}(x)\big{)}(j_{1})<\big{(}\psi_{1}(x)\big{)}(j_{2})$. In such
case we have

$\displaystyle\max\ell_{k_{2}}(x)$
$\displaystyle\overset{(a)}{=}\big{(}\ell_{k_{2}}(x)\big{)}(j_{2})$
$\displaystyle=\big{(}\ell_{k_{1}}(x)-(k_{2}-k_{1})\psi_{1}(x)\big{)}(j_{2})$
$\displaystyle\leq(k_{1}-k_{2})\big{(}\psi_{1}(x)\big{)}(j_{2})+\max_{j}\big{(}\ell_{k_{1}}(x)\big{)}(j)$
$\displaystyle\overset{(b)}{=}(k_{1}-k_{2})\big{(}\psi_{1}(x)\big{)}(j_{2})+\big{(}\ell_{k_{1}}(x)\big{)}(j_{1})$
$\displaystyle\overset{(c)}{<}(k_{1}-k_{2})\big{(}\psi_{1}(x)\big{)}(j_{1})+\big{(}\ell_{k_{1}}(x)\big{)}(j_{1})$
$\displaystyle=\big{(}\ell_{k_{2}}(x)\big{)}(j_{2}),$ (47)

where $(a)$ and $(b)$ holds due to the definition of $j_{1}$ and $j_{2}$, and
$(c)$ holds due to the assumption
$\big{(}\psi_{1}(x)\big{)}(j_{1})<\big{(}\psi_{1}(x)\big{)}(j_{2})$. The last
inequality is clearly a contradiction, and shows that $\langle
f_{k_{1},0}^{*}(x),\psi_{1}(x)\rangle\geq\langle
f_{k_{2},0}^{*}(x),\psi_{1}(x)\rangle$, and therefore $C(k_{1})\geq C(k_{2})$.

  2. 2.

Let us divide the space ${\cal X}$ into two subsets

$\displaystyle A_{k}=\Big{\\{}x\in{\cal X}:\,\big{|}\mathop{\rm
argmax}\limits_{i}(\ell_{k}(x))(i)\big{|}=d\Big{\\}},$ $\displaystyle
B_{k}=\Big{\\{}x\in{\cal X}:\,\big{|}\mathop{\rm
argmax}\limits_{i}(\ell_{k}(x))(i)\big{|}\in[1:d-1]\Big{\\}}.$

For each $x\in A_{k}$ we know

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

Using previous part, we know that by increasing $k$ we have no increase in
$\langle f^{*}_{k,0}(x),\psi_{1}(x)\rangle$, and in this case since $\langle
f^{*}_{k,0}(x),\psi_{1}(x)\rangle=\min_{j}\big{(}\psi_{1}(x)\big{)}(j)$, then
this value cannot reduce with the change of $k$. Therefore, $\langle
f^{*}_{k,0}(x),\psi_{1}(x)\rangle$ is a constant function for all
$k^{\prime}\geq k$, and consequently $\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},0}(x),\psi_{1}(x)\rangle|x\in A_{k}\big{]}\mathbb{P}(x\in
A_{k})$ is a constant function for $k^{\prime}\geq k$.

If $x\in B_{k}$, then for $j\notin\mathop{\rm
argmax}\limits_{i}\big{(}\ell_{k}(x)\big{)}(i)$ and $l\in\mathop{\rm
argmax}\limits_{i}\big{(}\ell_{k}(x)\big{)}(i)$, we have
$\big{(}\ell_{k}(x)\big{)}(j)<\big{(}\ell_{k}(x)\big{)}(l)$. Define the set
$C_{\delta}$ for $\delta\geq 0$ as

$\displaystyle C_{\delta}=\\{x\in
B_{k}:\,\big{(}\ell_{k}(x)\big{)}(j)\leq\big{(}\ell_{k}(x)\big{)}(l)-\delta\\}.$

Using Lemma I.1 we know that

$\displaystyle\lim_{\delta\to 0}\mathbb{P}(B_{k}\setminus C_{\delta})=0,$

or equivalently for all $\epsilon\geq 0$, there exists $\delta$ such that

$\displaystyle\mathbb{P}(B_{k}\setminus C_{\delta})\leq\epsilon^{\prime}.$

Therefore, if without loss of generality, we assume that $\psi_{1}(x)$ is
bounded by $1$, then there exists $\delta\geq 0$ such that we have

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},0}(x),\psi_{1}(x)\rangle|x\in B_{k}\setminus
C_{\delta}\big{]}\mathbb{P}(x\in$ $\displaystyle B_{k}\setminus C_{\delta})$
$\displaystyle\overset{(a)}{\leq}\|\psi_{1}(x)\|_{\infty}\mathbb{P}(x\in
B_{k}\setminus C_{\delta})\leq\epsilon/2,$

where $(a)$ holds due to Hölder’s inequality.

If $x\in C_{\delta}$, and because we assumed $\|\psi_{1}(x)\|_{\infty}\leq 1$,
then we know that by increasing $k$ to $k^{\prime}\in[k-\delta/2,k+\delta/2)$,
we have

$\displaystyle{\cal I}=\mathop{\rm
argmax}\limits\ell_{k^{\prime}}(x)\subseteq\mathop{\rm
argmax}\limits\ell_{k}(x)={\cal J}.$ (48)

This means that

$\displaystyle\langle f_{k,0}^{*}(x),\psi_{1}(x)\rangle=\min_{j\in{\cal
J}}\big{(}\psi_{1}(x)\big{)}(j)\leq\min_{j\in{\cal
I}}\big{(}\psi_{1}(x)\big{)}(j)=\langle
f_{k^{\prime},0}^{*}(x),\psi_{1}(x)\rangle.$

This, together with the previous part in which we showed $\langle
f_{k,0}^{*}(x),\psi_{0}(x)\rangle\geq\langle
f_{k^{\prime},0}^{*}(x),\psi_{0}(x)\rangle$, concludes that $\langle
f_{k,0}^{*}(x),\psi_{0}(x)\rangle=\langle
f_{k^{\prime},0}^{*}(x),\psi_{0}(x)\rangle$. This means that
$\mathbb{E}\big{[}\langle f^{*}_{k^{\prime},0}(x),\psi_{0}(x)\rangle|x\in
C_{\delta}\big{]}\mathbb{P}(x\in C_{\delta})$ is a constant function for all
$k^{\prime}\geq k$ .

Finally, since we have

$\displaystyle C(k^{\prime})=\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},0}(x),\psi_{1}(x)\rangle\big{]}=$
$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},0}(x),\psi_{1}(x)\rangle|x\in A_{k}\big{]}\mathbb{P}(x\in
A_{k})$ $\displaystyle+\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},0}(x),\psi_{1}(x)\rangle|x\in B_{k}\setminus
C_{\delta}\big{]}\mathbb{P}(x\in B_{k}\setminus C_{\delta})$
$\displaystyle+\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},0}(x),\psi_{1}(x)\rangle|x\in
C_{\delta}\big{]}\mathbb{P}(x\in C_{\delta}),$

and because the first term and the third term in RHS are constant in terms of
$k^{\prime}$ and for $k^{\prime}\geq k$, and the second term is diminishing,
then we have

$\displaystyle\big{|}C(k^{\prime})-C(k)\big{|}=\big{|}$
$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},0}(x),\psi_{1}(x)\rangle|x\in B_{k}\setminus
C_{\delta}\big{]}\mathbb{P}(x\in B_{k}\setminus C_{\delta})$
$\displaystyle-\mathbb{E}\big{[}\langle f^{*}_{k,0}(x),\psi_{1}(x)\rangle|x\in
B_{k}\setminus C_{\delta}\big{]}\mathbb{P}(x\in B_{k}\setminus
C_{\delta})\big{|}\leq\epsilon/2+\epsilon/2,$

which is equivalent to say that $\lim_{k^{\prime}\uparrow
k}C(k^{\prime})=C(k)$.

  3. 3.

For $p=1$, we know that the prediction function $f^{*}_{k,p}(x)$ is obtained
as

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

If we define $\psi_{1}^{\prime}(x):=-\psi_{0}(x)$, then we have

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

Since the above is equal to (46), then using the first part of this lemma, we
know that $\mathbb{E}\big{[}\langle
f^{*}_{k,1}(x),\psi^{\prime}_{1}(x)\rangle\big{]}=-\mathbb{E}\big{[}\langle
f^{*}_{k,1}(x),\psi_{0}(x)\rangle\big{]}$ is monotonically non-increasing,
which is equivalent to $F(k)=\mathbb{E}\big{[}\langle
f^{*}_{k,1}(x),\psi_{0}(x)\rangle\big{]}$ being monotonically non-decreasing.

  4. 4.

This part is similar to the second part of the proof. In fact, if $x\in
A_{k}$, then we have

$\displaystyle\big{(}f_{k,1}^{*}(x)\big{)}(i)=\left\\{\begin{array}[]{cc}1&i=\min\\{\mathop{\rm
argmax}\limits_{j}\big{(}\psi_{0}(x)\big{)}(j)\\}\\\
0&\text{otherwise}\end{array}\right..$ (51)

For $k^{\prime}\leq k$ and because of the third part of this lemma, we know
that $\langle f^{*}_{k^{\prime},1}(x),\psi_{0}(x)\rangle\geq\langle
f^{*}_{k,1}(x),\psi_{0}(x)\rangle$. Furthermore, because of (51) we know that
$\langle f^{*}_{k,1}(x),\psi_{0}(x)\rangle=\max\psi_{0}(x)$, and therefore by
reducing $k^{\prime}$, the prediction function $f^{*}_{k^{\prime},1}(x)$ stays
constant. As a result, $\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},1}(x),\psi_{1}(x)\rangle|x\in A_{k}\big{]}\mathbb{P}(x\in
A_{k})$ is a constant function for $k^{\prime}\leq k$.

Furthermore, similar to the second part of this lemma, we can show that for
each $\epsilon>0$, there exists $\delta^{\prime}\geq 0$ such that for all
$0\leq\delta\leq\delta^{\prime}$ we have

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},1}(x),\psi_{1}(x)\rangle|x\in B_{k}\setminus
C_{\delta}\big{]}\mathbb{P}(x\in$ $\displaystyle B_{k}\setminus C_{\delta})$
$\displaystyle\overset{(a)}{\leq}\|\psi_{1}(x)\|_{\infty}\mathbb{P}(x\in
B_{k}\setminus C_{\delta})\leq\epsilon/4,$ (52)

Moreover, for the case of $x\in C_{\delta}$, since in this case ${\cal
J}\subseteq{\cal I}$, then we know that

$\displaystyle\langle f_{k,1}^{*}(x),\psi_{0}(x)\rangle=\max_{j\in{\cal
J}}\big{(}\psi_{0}(x)\big{)}(j)\leq\max_{j\in{\cal
I}}\big{(}\psi_{0}(x)\big{)}(j)=\langle
f_{k^{\prime},1}^{*}(x),\psi_{0}(x)\rangle.$ (53)

Next, using the third part of this lemma, we know that for $k^{\prime}\leq k$
we have $\langle f_{k^{\prime},1}^{*}(x),\psi_{0}(x)\rangle\leq\langle
f_{k,1}^{*}(x),\psi_{0}(x)\rangle$, which together with (53) concludes that
$\langle f_{k,1}^{*}(x),\psi_{0}(x)\rangle=\langle
f_{k^{\prime},1}^{*}(x),\psi_{0}(x)\rangle$. Next, because
$\big{(}\psi_{0}(x)-k\psi_{1}(x)\big{)}(i)=\big{(}\psi_{0}(x)-k\psi_{1}(x)\big{)}(j)$
for $i,j\in{\cal J}$, then we know that
$\Big{|}\big{(}\ell_{k^{\prime}}(x)\big{)}(i)-\big{(}\ell_{k^{\prime}}(x)\big{)}(j)\Big{|}=\big{|}(k-k^{\prime})\Big{(}\big{(}\psi_{1}(x))(i)-\big{(}\psi_{1}(x))(j)\Big{)}\leq
2|k-k^{\prime}|$. Therefore, if for $i,j\in{\cal J}$ we know that
$\big{(}\psi_{0}(x)\big{)}(i)=\big{(}\psi_{0}(x)\big{)}(j)$, then the
difference between $\psi_{1}$ for those indices is bounded as

$\displaystyle\Big{|}\big{(}\psi_{1}(x)\big{)}(i)-\big{(}\psi_{1}(x)\big{)}(j)\Big{|}$
$\displaystyle\leq\frac{1}{k}\Big{|}\big{(}\psi_{0}(x)\big{)}(i)-\big{(}\psi_{0}(x)\big{)}(j)\Big{|}$
$\displaystyle\quad+\Big{|}\big{(}\ell_{k}(x)\big{)}(i)-\big{(}\ell_{k}(x)\big{)}(j)\Big{|}$
$\displaystyle\leq 2|k-k^{\prime}|.$ (54)

Now, we know that because $x\in C_{\delta}$, then $\langle
f^{*}_{k,1}(x),\psi_{1}(x)\rangle=\big{(}\psi_{1}(x)\big{)}(i)$ for
$i\in\mathop{\rm argmax}\limits_{j\in{\cal J}}\big{(}\psi_{0}(x)\big{)}(j)$,
and $\langle
f^{*}_{k^{\prime},1}(x),\psi_{1}(x)\rangle=\big{(}\psi_{1}(x)\big{)}(j)$ for
$j\in\mathop{\rm argmax}\limits_{k\in{\cal I}}\big{(}\psi_{0}(x)\big{)}(j)$.
Hence, we can see that $i\in{\cal J}\subseteq{\cal I}$ and $j\in{\cal I}$, and
because $\big{(}\psi_{0}(x)\big{)}(i)=\langle
f^{*}_{k,1}(x),\psi_{0}(x)\rangle=\langle
f^{*}_{k^{\prime},1}(x),\psi_{0}(x)\rangle=\big{(}\psi_{0}(x)\big{)}(j)$, and
due to (54) we have

$\displaystyle\Big{|}\langle f^{*}_{k,1}(x),\psi_{1}(x)\rangle-\langle
f^{*}_{k^{\prime},1}(x),\psi_{1}(x)\rangle\Big{|}\leq 2|k-k^{\prime}|,$

as long as $k^{\prime}\in[k-\delta/2,k)$. Therefore, if we set
$\delta=\max\\{\delta^{\prime},\epsilon/2\\}$ we have

$\displaystyle\big{|}\langle f^{*}_{k,1}(x),\psi_{1}(x)\rangle-\langle
f^{*}_{k^{\prime},1}(x),\psi_{1}(x)\rangle\big{|}\leq\epsilon/2,$

and therefore

$\displaystyle\Big{|}\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},1}(x),\psi_{1}(x)\rangle|x\in C_{\delta}\big{]}-$
$\displaystyle\mathbb{E}\big{[}\langle f^{*}_{k,1}(x),\psi_{1}(x)\rangle|x\in
C_{\delta}\big{]}\Big{|}$ $\displaystyle\leq\mathbb{E}\Big{[}\big{\|}\langle
f^{*}_{k,1}(x),\psi_{0}(x)\rangle-\langle
f^{*}_{k^{\prime},1}(x),\psi_{0}(x)\rangle\big{\|}\Big{]}\leq\epsilon/2$ (55)

Finally, we can rewrite $D(k^{\prime})$ as

$\displaystyle D(k^{\prime})=\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},1}(x),\psi_{0}(x)\rangle\big{]}=$
$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},1}(x),\psi_{0}(x)\rangle|x\in A_{k}\big{]}\mathbb{P}(x\in
A_{k})$ $\displaystyle+\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},1}(x),\psi_{0}(x)\rangle|x\in B_{k}\setminus
C_{\delta}\big{]}\mathbb{P}(x\in B_{k}\setminus C_{\delta})$
$\displaystyle+\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},1}(x),\psi_{0}(x)\rangle|x\in
C_{\delta}\big{]}\mathbb{P}(x\in C_{\delta}),$

and because of (52) and (55), and since the first term is a constant function
in terms of $k^{\prime}$ and for all $k^{\prime}\in[k-\delta/2,k]$, then we
have

$\displaystyle|D(k^{\prime})-D(k)|\leq\epsilon/4+\epsilon/4+\epsilon/2=\epsilon.$
(56)

This shows that $D(k^{\prime})$ is lower semi-continuous around
$k^{\prime}=k$.

  5. 5.

To prove this part, we first divide ${\cal X}$ into two subsets

$\displaystyle G_{k^{\prime}}=\Big{\\{}x\in{\cal X}:\,\big{|}\mathop{\rm
argmax}\limits_{i}(\ell_{k^{\prime}}(x))(i)\big{|}=1\Big{\\}},$ (57)

and $H_{k^{\prime}}={\cal X}\setminus G_{k^{\prime}}$. We know that for $x\in
G_{k^{\prime}}$ we have

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

This concludes that

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},0}(x),\psi_{1}(x)\rangle|\,x\in
G_{k}\big{]}=\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},1}(x),\psi_{1}(x)\rangle|\,x\in G_{k}\big{]}.$ (61)

Moreover, let us define the set $\Psi_{1}^{k^{\prime}}=\\{x\in{\cal
X}:\,\exists c\in\mathbb{R},\forall j\in\mathop{\rm
argmax}\limits\ell_{k^{\prime}}(x),\big{(}\psi_{1}(x)\big{)}(j)=c\\}$ . We
show that sum of the probabilities of
$H_{k^{\prime}}\setminus\Psi_{1}^{k^{\prime}}$ is always bounded by $2^{d}$
for a set of choices for $k^{\prime}$, or equivalently

$\displaystyle\sum_{k^{\prime}\in{\cal K}}\mathbb{P}(x\in
H_{k^{\prime}}\setminus\Psi_{1}^{k^{\prime}})\leq 2^{d},$ (62)

for all finite or countably infinite choice of ${\cal
K}\subseteq\mathbb{R}^{+}$. In fact, we know that for each instance $x$,
$\mathop{\rm argmax}\limits_{j\in[1:d]}\big{(}\ell_{k}(x)\big{)}(j)$ can take
up to $2^{d}$ cases of all subsets of $\\{1,\ldots,d\\}$. Therefore, we need
to show that there cannot exist two values of $k,k^{\prime}$ such that for
$x\in\big{(}H_{k}\setminus\Psi_{1}^{k}\big{)}\cap\big{(}H_{k^{\prime}}\setminus\Psi_{1}^{k^{\prime}}\big{)}$
we have

$\displaystyle\mathop{\rm
argmax}\limits_{j}\big{(}\ell_{k}(x)\big{)}(j)=\mathop{\rm
argmax}\limits_{j}\big{(}\ell_{k^{\prime}}(x)\big{)}(j).$ (63)

If we prove such identity, then due to pigeonhole principle, we have

$\displaystyle\sum_{k^{\prime}\in{\cal K}}\mathds{1}_{x\in
H_{k^{\prime}}\setminus\Psi_{1}^{k^{\prime}}}\leq 2^{d},$ (64)

which by integration over all values of $x$ concludes in (62). We prove this
claim by contradiction. If we assume $k,k^{\prime}\in{\cal K}$ such that for
$x\in\big{(}H_{k}\setminus\Psi_{1}^{k}\big{)}\cap\big{(}H_{k^{\prime}}\setminus\Psi_{1}^{k^{\prime}}\big{)}$
the identity (63) holds, then because $x\in H_{k}\cap H_{k^{\prime}}$, then
the size of $\mathop{\rm argmax}\limits_{j}\big{(}\ell_{k}(x)\big{)}(j)$ and
$\mathop{\rm argmax}\limits_{j}\big{(}\ell_{k^{\prime}}(x)\big{)}(j)$ is at
least $2$. This concludes that

$\displaystyle\big{(}\psi_{0}(x)-k\psi_{1}(x)\big{)}(i)=\big{(}\psi_{0}(x)-k\psi_{1}(x)\big{)}(j)$

as well as

$\displaystyle\big{(}\psi_{0}(x)-k^{\prime}\psi_{1}(x)\big{)}(i)=\big{(}\psi_{0}(x)-k^{\prime}\psi_{1}(x)\big{)}(j)$

for all choices of $i,j\in\mathop{\rm argmax}\limits\ell_{k}(x)$. As a result,
we have

$\displaystyle(k-k^{\prime})\Big{(}\big{(}\psi_{1}(x)\big{)}(i)-\psi_{1}(x)\big{)}(j)\Big{)}=0,$

and because $k^{\prime}\neq k$, we have

$\displaystyle\big{(}\psi_{1}(x)\big{)}(i)=\psi_{1}(x)\big{)}(j),$

for all $i,j\in\mathop{\rm argmax}\limits\ell_{k}(x)$. Therefore,
$x\in\Psi_{1}^{k^{\prime}}$ and that is a contradiction.

Now that we know that the sum of the probabilities of $\mathbb{P}(x\in
H_{k^{\prime}}\setminus\Psi_{1}^{k^{\prime}})$ is bounded, we can renormalize
that and make a probability measure as

$\displaystyle g(A)=\frac{\sum_{k\in A,\mathbb{P}(x\in
H_{k}\setminus\Psi_{1}^{k})>0}\mathbb{P}(x\in
H_{k}\setminus\Psi_{1}^{k})}{\sum_{k:\mathbb{P}(x\in
H_{k}\setminus\Psi_{1}^{k})>0}\mathbb{P}(x\in H_{k}\setminus\Psi_{1}^{k})}.$
(65)

Due to Lemma I.1, for all $\epsilon\geq 0$ we can find a small enough
$\delta\geq 0$ such that $g([k-\delta,k))\leq\epsilon/2^{d+1}$, and therefore
for all $k^{\prime}\in[k-\delta,k)$ we have

$\displaystyle\mathbb{P}(x\in H_{k^{\prime}}\setminus\Psi_{1}^{k^{\prime}})$
$\displaystyle\leq\sum_{t\in[k-\delta,k),\mathbb{P}(x\in
H_{t}\setminus\Psi_{1}^{t})>0]}\mathbb{P}(x\in H_{t}\setminus\Psi_{1}^{t})$
$\displaystyle=g\big{(}[k-\delta,k)\big{)}\sum_{k:\mathbb{P}(x\in
H_{k}\setminus\Psi_{1}^{k})>0}\mathbb{P}(x\in H_{k}\setminus\Psi_{1}^{k})$
$\displaystyle\leq\frac{\epsilon}{2^{d+1}}2^{d}=\epsilon/2,$

where the last inequality holds because of (62).

Now, using this and due to (61), and by defining $g_{i}(x)=\langle
f^{*}_{k,i}(x),\psi_{0}(x)\rangle$ for $i=1,2$, we can bound the difference of
$D(k)$ and $C(k)$ as

$\displaystyle\big{|}D(k)-C(k)\big{|}$
$\displaystyle=\Big{|}\mathbb{E}\big{[}g_{1}(x)-g_{0}(x)|\,x\in
H_{k^{\prime}}\big{]}\mathbb{P}(x\in H_{k^{\prime}})\Big{|}$
$\displaystyle\leq\mathbb{P}(x\in
H_{k^{\prime}}\setminus\Psi_{1}^{k^{\prime}}|x\in
H_{k^{\prime}})\Big{|}\mathbb{E}\big{[}g_{1}(x)-g_{0}(x)|\,x\in
H_{k^{\prime}}\setminus\Psi_{1}^{k^{\prime}}\big{]}\Big{|}$
$\displaystyle\phantom{=}+\mathbb{P}(x\in
H_{k^{\prime}}\cap\Psi_{1}^{k^{\prime}}|x\in
H_{k^{\prime}})\Big{|}\mathbb{E}\big{[}g_{1}(x)-g_{0}(x)|\,x\in
H_{k^{\prime}}\cap\Psi_{1}^{k^{\prime}}\big{]}\Big{|}$
$\displaystyle\overset{(a)}{\leq}2(\epsilon/2)+\Big{|}\mathbb{E}\big{[}g_{1}(x)-g_{0}(x)|\,x\in
H_{k^{\prime}}\cap\Psi_{1}^{k^{\prime}}\big{]}\Big{|}$
$\displaystyle\overset{(b)}{=}\epsilon,$

where $(a)$ holds because
$\|f^{*}_{k,0}-f^{*}_{k,1}\|_{1}\leq\|f^{*}_{k,0}\|_{1}+\|f^{*}_{k,1}\|_{1}=2$
and because of Hölder inequality we have $\big{|}\langle
f^{*}_{k,0}(x)-f^{*}_{k,1},\psi_{1}(x)\rangle\big{|}\leq\|f^{*}_{k,0}-f^{*}_{k,1}\|_{1}\|\psi_{1}(x)\|_{\infty}\leq
2$. Moreover, to show that $(b)$ holds we know that for
$x\in\Psi_{1}^{k^{\prime}}$ we have
$\big{(}\psi_{1}(x)\big{)}(i)=\big{(}\psi_{1}(x)\big{)}(j)$ for all
$i,j\in\mathop{\rm argmax}\limits\ell_{k^{\prime}}(x)$. Therefore, because we
know $g_{0}(x)=\big{(}\psi_{1}(x)\big{)}(i)$ for $i\in\mathop{\rm
argmin}\limits_{j\in\mathop{\rm
argmax}\limits_{l}\big{(}\ell_{k^{\prime}}(x)\big{)}(l)}\big{(}\psi_{1}(x)\big{)}(j)\subseteq\mathop{\rm
argmax}\limits_{l}\big{(}\ell_{k^{\prime}}(x)\big{)}(l)$ and
$g_{1}(x)=\big{(}\psi_{1}(x)\big{)}(j)$ for $j\in\mathop{\rm
argmax}\limits_{j\in\mathop{\rm
argmax}\limits_{l}\big{(}\ell_{k^{\prime}}(x)\big{)}(l)}\big{(}\psi_{0}(x)\big{)}(j)\subseteq\mathop{\rm
argmax}\limits_{l}\big{(}\ell_{k^{\prime}}(x)\big{)}(l)$, we have
$g_{0}(x)=g_{1}(x)$. The above inequality proves that the limit of
$C(k^{\prime})$ and $D(k^{\prime})$ for $k^{\prime}\uparrow k$ are equal and
that completes the proof.

∎

To prove this theorem, we take the following steps: (i) We show that the set
${\cal K}$ has a non-negative member, (ii) we show that the prediction
function $f^{*}_{k,p}(x)$ achieves the inequality constraint tightly, and by
Theorem 4.1 we can conclude that $f^{*}_{k,p}(x)$ is the optimal solution.

  * •

step (i): It is easy to see that the Bayes optimal solution of the prediction
function in (3) without any constraint is

$\displaystyle\big{(}f^{*}(x)\big{)}(i)=\left\\{\begin{array}[]{cc}1&\big{(}\psi_{0}(x)\big{)}(i)>\big{(}\psi_{0}(x)\big{)}(j)\text{
for all }j\neq i\\\
0&\big{(}\psi_{0}(x)\big{)}(i)<\max_{j}\big{(}\psi_{0}(x)\big{)}(j)\\\
p_{i}(x)&\text{otherwise}\end{array}\right.,$

where $p_{i}(x)\in\Delta_{d}$ is an arbitrary vector. We can see that by
setting

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

then the two prediction functions $f^{*}(x)$ and $f^{*}_{0,0}(x)$ are equal
(See statement of Theorem 4.2).

Now, in the first and second part of Lemma I.2 we have shown that
$\mathbb{E}\big{[}\langle f^{*}_{k,0}(x),\psi_{1}(x)\rangle\big{]}$ is upper
semi-continuous and monotonically non-increasing. Therefore, for all
$k\in\mathbb{R}^{+}$ we have

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k,0}(x),\psi_{1}(x)\rangle\big{]}\leq\mathbb{E}\big{[}\langle
f^{*}_{0,0}(x),\psi_{1}(x)\rangle\big{]}=\mathbb{E}\big{[}\langle
f^{*}(x),\psi_{1}(x)\rangle\big{]}.$

Similarly, we can show that for $k\to\infty$, the solution is equivalent to
the Bayes minimizer of

$\displaystyle f^{**}(x)=\mathop{\rm argmin}\limits_{f\in\Delta_{d}^{{\cal
X}}}\mathbb{E}\big{[}\langle f(x),\psi_{1}(x)\rangle\big{]}.$

Therefore, since $\delta$ is an interior point of all possible values, it lays
on the interval $\big{(}\mathbb{E}\big{[}\langle
f^{**}(x),\psi_{1}(x)\rangle\big{]},\mathbb{E}\big{[}\langle
f^{*}(x),\psi_{1}(x)\rangle\big{]}\big{)}$, due to the montonicity and upper
semi-continuity of $\mathbb{E}\big{[}\langle
f^{*}_{k,0},\psi_{1}(x)\rangle\big{]}$, we can find $t$ such that

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{t,0}(x),\psi_{1}(x)\rangle\big{]}\leq\delta\leq\lim_{\tau\uparrow
t}\mathbb{E}\big{[}\langle f^{*}_{k,0}(x),\psi_{1}(x)\rangle\big{]}.$ (66)

Moreover, this $t$ should be a positive scalar, since otherwise we have

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{t,0}(x),\psi_{1}(x)\rangle\big{]}\geq\mathbb{E}\big{[}\langle
f^{*}_{0,0}(x),\psi_{1}(x)\rangle\big{]}=\mathbb{E}\big{[}\langle
f^{*}(x),\psi_{1}(x)\rangle\big{]}>\delta,$

which is a contradiction to (66).

  * •

step (ii): In this step, we consider the following two cases:

    * –

$C(t)$ is continuous at $t$: In this case, (66) is equivalent to
$\delta=C(t)=\mathbb{E}\big{[}\langle
f^{*}_{t,0}(x),\psi_{0}(x)\rangle\big{]}$, which means that the prediction
function $f^{*}_{k,0}(x)$ achieves the constraint tightly, and therefore using
Theorem 4.1 $f^{*}_{k,0}(x)$ is the optimal solution.

    * –

$C(t)$ is discontinuous at $t$: To show that we can achieve the highest
constraint in this case, we first condition the constraint into two events
$x\in G_{k}$ and $x\in{\cal X}\setminus G_{k}$, where $G_{k}$ is defined in
(57). We know that in the latter case $x\in{\cal X}\setminus G_{k}$, the
prediction function $f^{*}_{k,p}$ can be decomposed into two components

$\displaystyle f^{*}_{k,p}(x)=pf^{*}_{k,1}(x)+(1-p)f^{*}_{k,0}(x),$ (67)

while for $x\in G_{k}$ the prediction function
$f^{*}_{k,p}(x)=f^{*}_{k,0}(x)=f^{*}_{k,1}(x)$ for all $p\in[0,1]$. Therefore,
in both cases (67) holds, and we have

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k,p}(x),\psi_{1}(x)\rangle\big{]}$
$\displaystyle=\mathbb{E}\big{[}\langle
pf^{*}_{k,1}(x)+(1-p)f^{*}_{k,0}(x),\psi_{1}(x)\rangle\big{]}$
$\displaystyle=p\mathbb{E}\big{[}\langle
f^{*}_{k,1}(x),\psi_{1}(x)\rangle\big{]}+(1-p)\mathbb{E}\big{[}\langle
f^{*}_{k,0}(x),\psi_{1}(x)\rangle\big{]}$ $\displaystyle=pD(k)+(1-p)C(k),$
(68)

where $C(\cdot)$ and $D(\cdot)$ are defined in Lemma I.2. Using this lemma, we
know that $D(\cdot)$ is lower semi-continuous, and $\lim_{k^{\prime}\uparrow
k}C(k)=\lim_{k^{\prime}\uparrow k}D(k)$. Therefore, together with (68) and the
definition of $p$ in the statement of theorem, we have

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k,p}(x),\psi_{0}(x)\rangle\big{]}=$ $\displaystyle
p\lim_{k^{\prime}\uparrow k}C(k^{\prime})+(1-p)C(k)$ $\displaystyle=$
$\displaystyle\frac{C(k)-c}{C(k)-\lim_{k^{\prime}\uparrow
k}C(k^{\prime})}\lim_{k^{\prime}\uparrow k}C(k^{\prime})$
$\displaystyle+\frac{c-\lim_{k^{\prime}\uparrow
k}C(k^{\prime})}{C(k)-\lim_{k^{\prime}\uparrow k}C(k^{\prime})}C(k)=c.$ (69)

Equivalently, the prediction function achieves the constraint inequality
tightly, and therefore by Theorem 4.1 this is sufficient to be the optimal
solution to the constrained optimization problem.

##  Appendix J Proof of Theorem 5.1

Through the proof of this theorem, we use [5, Lemma 3.2.3] that implies that
the class of multiplications of $k$ binary functions $f_{i}(x)$ for
$i\in[1:k]$ within a hypothesis class with VC dimension $VC(f_{i})=d$ itself
has a VC dimension that is bounded as

$\displaystyle VC(\underbrace{\big{\\{}\prod_{i=1}^{k}f_{i}:f_{i}\in{\cal
H}_{i},VC({\cal H}_{i})=d\big{\\}}}_{{\cal H}^{\prime}})\leq 2dk\log 3k.$ (70)

In fact, we use a simple extension to this lemma for which the VC dimension of
the functions is not $d$ itself but is bounded above by $d$. In such case we
claim that (70) still holds. The starting point for the proof to this lemma is
bounding the size of the restriction $\Pi_{{\cal H}}(S)=|\\{h\cap S:h\in{\cal
H}\\}|$ for the hypothesis class ${\cal H}$ by

$\displaystyle\Pi_{{\cal H}}(S)\leq\big{(}\frac{em}{d}\big{)}^{d},$ (71)

where $VC({\cal H})=d$ and $m=|S|$. However, this inequality holds for the
hypothesis classes that have VC dimensions that are bounded by $d$. The reason
is increasingly monotonicity of RHS of (71). In fact, by obtaining the
gradient of $\big{(}\frac{em}{d}\big{)}^{d}$ in terms of $d$ we have

$\displaystyle\frac{\partial\big{(}\frac{em}{d}\big{)}^{d}}{\partial
d}=\frac{\partial\big{(}e^{d\log em/d}\big{)}}{\partial d}=(\log
em/d-1)(\frac{em}{d}\big{)}^{d},$

which is nonnegative as long as $m\geq d$. If we particularly set
$m^{*}=2dk\log 3k$, then $m^{*}\geq d$ and therefore (71) holds. Next, similar
to the proof of [5, Lemma 3.2.3], we can show that for the set $S$ with size
$m^{*}$ we have

$\displaystyle\Pi_{{\cal H}^{\prime}}(S)\leq\Pi_{{\cal
H}_{1}}^{k}(S)\leq\big{(}\frac{em^{*}}{d}\big{)}^{dk}\leq 2^{m^{*}},$

which means that $S$ cannot be shattered by ${\cal H}^{\prime}$, and therefore
the VC dimension of this hypothesis class must be bounded by $m^{*}$.

We further use the following lemma:

∎

######  Lemma J.1.

For arbitrary sets of functions $\\{\phi_{1}^{i}(x)\\}_{i=1}^{n}$ and
$\\{\phi_{2}^{i}(x)\\}_{i=1}^{n}$ on $\mathbb{R}$ and for a given
$d\in\mathbb{R}$ the hypothesis class

$\displaystyle{\cal H}=\big{\\{}\prod_{i=1}^{n}{\rm
sgn}\big{(}\phi_{1}^{i}(x)-k\phi_{2}^{i}(x)-d\big{)}\,:\,k\in\mathbb{R}\big{\\}},$

has the VC dimension of at most $4$.

###### Proof.

To prove this lemma, we show that the form of the product in the definition of
${\cal H}$ reduces to the form of an interval on $\mathbb{R}$, which is known
to have VC dimension of $2$. In fact, each term ${\rm
sgn}(\phi_{1}^{i}(x)-k\phi_{2}^{i}(x)-d)$ can be rewritten as

$\displaystyle{\rm sgn}(\phi_{1}^{i}(x)-k\phi_{2}^{i}(x)-d)=$
$\displaystyle{\rm sgn}(\tfrac{\phi_{1}^{i}(x)-d}{\phi_{2}^{i}(x)}-k){\rm
sgn}(\phi_{2}^{i}(x))+{\rm
sgn}(k-\tfrac{\phi_{1}^{i}(x)-d}{\phi_{2}^{i}(x)}){\rm sgn}(-\phi_{2}^{i}(x))$
$\displaystyle+{\rm sgn}(\phi_{1}^{i}(x)-d)\mathbb{I}_{\phi_{2}^{i}(x)=0}.$

As a result, by multiplying all terms we have

$\displaystyle\prod_{i=1}^{n}{\rm
sgn}\big{(}\phi_{1}^{i}(x)-k\phi_{2}^{i}(x)-d\big{)}={\rm sgn}(\min_{i\in{\cal
A}_{x}}\tfrac{\phi_{1}^{i}(x)-d}{\phi_{2}(x)}-k){\rm sgn}(k-\max_{i\in{\cal
B}_{x}}\tfrac{\phi_{1}^{i}(x)-d}{\phi_{2}(x)})\prod_{i\in{\cal C}_{x}}{\rm
sgn}(\phi_{1}^{i}(x)-d),$ (72)

where ${\cal A}_{x}$, ${\cal B}_{x}$, and ${\cal C}_{x}$ are defined as ${\cal
A}_{x}=\\{i\in[1:n]\,:\,\phi_{2}^{i}(x)>0\\}$, ${\cal
B}_{x}=\\{i\in[1:n]\,:\,\phi_{2}^{i}(x)<0\\}$, and ${\cal
C}_{x}=\\{i\in[1:n]\,:\,\phi_{2}^{i}(x)=0\\}$. Now, we see that the first two
terms define an interval for $k\in\big{(}f_{1}(x),f_{2}(x)\big{)}$ where
$f_{1}(x)=\max_{i\in{\cal B}_{x}}\frac{\phi_{1}^{i}(x)-d}{\phi_{2}^{i}(x)}$
and $f_{2}(x)=\min_{i\in{\cal
A}_{x}}\frac{\phi_{1}^{i}(x)-d}{\phi_{2}^{i}(x)}$. Next, we prove that the VC
dimension of the hypothesis class of all such functions is less than the VC
dimension of ${\cal
G}=\big{\\{}f:\mathbb{R}\times\mathbb{R}\to\\{0,1\\}\,:\,f(x,y)={\rm
sgn}(x-k_{1}){\rm sgn}(k_{2}-y),\,k_{1},k_{2}\in\mathbb{R}\big{\\}}$. The
reason is that if the aforementioned interval can shatter a set ${\cal S}$,
then we can find the corresponding values of $f_{1}(x)$ and $f_{2}(x)$ for
each $x\in{\cal S}$, and then form the pair $(x_{i},y_{i})$ where
$x_{i}=f_{1}(x)$ and $y_{i}=f_{2}(x)$, and by setting $k_{1}=k_{2}=k$, we can
shatter the set $\\{(x_{i},y_{i})\\}_{i=1}^{|{\cal S}|}$ with ${\cal G}$. Note
that here all pairs are identical. The reason is that if not, i.e., if
$f_{1}(x)=f_{1}(x^{\prime})$ and $f_{2}(x)=f_{2}(x^{\prime})$ for
$x,x^{\prime}\in{\cal S}$ and $x\neq x^{\prime}$, then, for all possible $k$,
we have ${\rm sgn}(k-f_{1}(x)){\rm sgn}(f_{2}(x)-k)={\rm
sgn}(k-f_{1}(x^{\prime})){\rm sgn}(f_{2}(x^{\prime})-k)$, and therefore we
cannot shatter ${\cal S}$ by ${\rm sgn}(k-f_{1}(x)){\rm sgn}(f_{2}(x)-k)$.
Therefore, the set $\\{(x_{i},y_{i})\\}_{i=1}^{|{\cal S}|}$ has the same
cardinality of ${\cal S}$, which in consequence proves that the VC dimension
of all ${\rm sgn}(k-f_{1}(x)){\rm sgn}(f_{2}(x)-k)$ is bounded by $VC({\cal
G})$. Moreover, $VC({\cal G})\leq 4$, since for each $5$ points in two-
dimensional space, one is in the convex hull of the others, and in case that
all others are labeled as $1$, the one in the convex hull also must be labeled
as $1$. As a result, ${\cal G}$ cannot shatter $5$ points, and therefore
$VC({\cal G})\leq 4$.

Up to now, we have shown that the class of functions equal to the first two
terms of (72) has a VC dimension that is bounded by $4$. Next, we show that
multiplying a hypothesis class ${\cal H}$ with a binary function $\phi(x)$
does not increase the VC dimension of that class. More formally, if we define

$\displaystyle{\cal H}=\\{\phi(x)f(x)\,:\,f\in{\cal H}^{\prime}\\},$

then $VC({\cal H})\leq VC({\cal H}^{\prime})$. The reason is that if we can
shatter a set ${\cal S}$ using ${\cal H}$, then for each member $x\in{\cal S}$
there exists two members $f_{1},f_{2}$ of ${\cal H}^{\prime}$ such that
$f_{1}(x)=1$ and $f_{2}(x)=0$. This means that $\phi(x)\neq 0$, because
otherwise $f_{1}(x)=1$ would not be achievable. Therefore, $\phi(x)=1$ for all
$x\in{\cal S}$, and as a result similarly ${\cal H}^{\prime}$ can shatter
${\cal S}$, which proves that $VC({\cal H})\leq VC({\cal H}^{\prime})$.

Finally, since we know that the class of all functions in ${\cal H}$ is in
form of ${\rm sgn}(k-f_{1}(x)){\rm sgn}(f_{2}(x)-k)$ multiplied with a binary
function, then we conclude that $VC({\cal H})\leq 4$. ∎

To prove the rest of the theorem, we need to show that for all choices of
$\hat{k}$ and $\hat{p}$ the difference of the empirical and the true loss is
bounded. In fact, we should find a bound in form of

$\displaystyle\mathbb{P}\Big{(}\sup_{k,p}\big{|}\mathbb{E}_{S^{n}}\big{[}\langle
f^{*}_{k,p}(x),\psi_{0}(x)\rangle\big{]}-\mathbb{E}_{\mu}\big{[}\langle
f^{*}_{k,p}(x),\psi_{0}(x)\rangle\big{]}\big{|}\leq d_{n}\Big{)}\geq
1-\epsilon.$

Here, we divide the class ${\cal X}$ into two subsets $G_{k}$ and $H_{k}={\cal
X}\setminus G_{k}$, where $G_{k}$ is defined in (57).

Now, using the definition of $f^{*}_{k,p}(x)$, we know that within $G_{k}$,
the inner-product $\langle f^{*}_{k,p}(x),\psi_{1}(x)\rangle$ can be rewritten
as

$\displaystyle\langle$ $\displaystyle
f^{*}_{k,p}(x),\psi_{1}(x)\rangle=\Big{(}\psi_{1}(x)\Big{)}(\mathop{\rm
argmax}\limits_{i}\big{(}\ell_{k}(x)\big{)}(i))$
$\displaystyle=\sum_{j=1}^{d}\big{(}\psi_{1}(x)\big{)}(j)\prod_{i\neq j}{\rm
sgn}\Big{(}\big{(}\ell_{k}(x)\big{)}(j)-\big{(}\ell_{k}(x)\big{)}(i)\Big{)}$
$\displaystyle=\sum_{j=1}^{d}\big{(}\psi_{1}(x)\big{)}(j)\underbrace{\prod_{i\neq
j}{\rm
sgn}\Big{(}\big{(}\psi_{0}(x)\big{)}(j)-\big{(}\psi_{0}(x)\big{)}(0)-k\big{[}\big{(}\psi_{1}(x)\big{)}(j)-\big{(}\psi_{1}(x)\big{)}(i)\big{]}\Big{)}}_{\Phi_{j}^{k}(x)}.$

Now, we can condition $x$ on being a member of $G_{k}$, and therefore the
maximum difference between the two empirical and true expectation is as

$\displaystyle\sup_{k,p}\Big{|}\mathbb{E}_{S^{n}}\big{[}\langle
f^{*}_{k,p}(x),\psi_{1}(x)\rangle\,|\,x\in
G_{k}\big{]}-\mathbb{E}_{\mu}\big{[}\langle
f^{*}_{k,p}(x),\psi_{1}(x)\rangle\,|\,x\in G_{k}\big{]}\Big{|}$
$\displaystyle\leq\sum_{j=1}^{d}\sup_{k,p}\Big{|}\mathbb{E}_{S^{n}}\Big{[}\big{(}\psi_{1}(x)\big{)}(j)\cdot\Phi_{j}^{k}(x)\,|x\in
G_{k}\Big{]}-\mathbb{E}_{\mu}\Big{[}\big{(}\psi_{1}(x)\big{)}(j)\cdot\Phi_{j}^{k}(x)\,|x\in
G_{k}\Big{]}\Big{|}.$ (73)

Now, we bound the inner term of (73) in a high probability setting. To that
end, we use Rademacher’s inequality in [63, Theorem 26.5], which shows that
maximum difference between the expected value of a function $h\in{\cal H}$
over empirical distribution and the true distribution is $2R({\cal
H})+4c\sqrt{\frac{\ln 4/\epsilon}{n}}$ where $R({\cal H})$ is the Rademacher’s
complexity of the class of function ${\cal H}$ and $c$ is maximum value that
$h$ can take. By defining

$\displaystyle h(x):=\big{(}\psi_{1}(x)\big{)}(j)\cdot\Phi_{j}^{k}(x),$

we have $c=\|\big{(}\psi_{1}(x)\big{)}(j)\|_{\infty}\leq 1$. Therefore, we
have for all $h$,

$\displaystyle\sup_{h\in{\cal
H}}\mathbb{E}_{S^{n}}\big{[}h(x)]-\mathbb{E}_{\mu}\big{[}h(x)]\leq 2R({\cal
H})+4\sqrt{\frac{\ln 4d/\epsilon}{n}},$ (74)

with probability at least $1-\frac{\epsilon}{d}$. Now, we can use contraction
Lemma [63, Lemma 26.9] to show that since
$\|\big{(}\psi_{1}(x)\big{)}(j)\|_{\infty}\leq 1$, then $R({\cal H})\leq
R({\cal F})$, where ${\cal F}=\\{\Phi_{j}^{k}(x),k\in\mathbb{R}\\}$. Moreover,
${\cal F}$ contains functions that are all multiplication of $d-1$ binary
functions all in form of

$\displaystyle{\rm
sgn}\Big{(}\big{(}\psi_{1}(x)\big{)}(j)-\big{(}\psi_{1}(x)\big{)}(0)-k\big{[}\big{(}\psi_{0}(x)\big{)}(j)-\big{(}\psi_{0}(x)\big{)}(i)\big{]}\Big{)}.$

Lemma J.1 shows that the hypothesis class that contains products of all such
function has a VC-dimension that is bounded by $4$. As a result, the
Rademacher’s complexity of ${\cal F}$ is bounded using [44, Corollary 3.8,
Corollary3.18] as

$\displaystyle R({\cal F})\leq\sqrt{\frac{4\log en/4}{n}},$

and therefore together with (74) for all $h\in{\cal H}$ we have

$\displaystyle\mathbb{E}_{S^{n}}\big{[}h(x)\big{]}-\mathbb{E}_{\mu}\big{[}h(x)\big{]}\leq
2\sqrt{\frac{4\log en/4}{n}}+4\sqrt{\frac{\ln 4d/\epsilon}{n}},$

with probability at least $1-\frac{\epsilon}{d}$. Hence, using (73) we have

$\displaystyle\sup_{k,p}\Big{|}\mathbb{E}_{S^{n}}\big{[}\langle
f^{*}_{k,p}(x),\psi_{1}(x)\rangle\,|\,x\in
G_{k}\big{]}-\mathbb{E}_{\mu}\big{[}\langle
f^{*}_{k,p}(x),\psi_{1}(x)\rangle\,|\,x\in G_{k}\big{]}\Big{|}$
$\displaystyle\leq 2d\sqrt{\frac{4\log el/4}{l}}+4d\sqrt{\frac{\ln
4d/\epsilon}{l}},$ (75)

with probability at least $1-\epsilon$. In the last inequality, we used
Bonferroni’s inequality on $\epsilon/d$ bad events that each summand of (73)
is not within the concentration bound.

Next, we consider the region $H_{k}$ in which there are at least two maximizer
components of $\ell_{k}(x)$. In this case, by definition of
$\hat{f}_{k,p}(x)$, among these maximizers, we choose the first maximizer of
$\psi_{0}(x)$ with probability $p$ and the first minimizer of $\psi_{1}(x)$
with probability $1-p$. Therefore, by condition on these cases, and if we
define

$\displaystyle
E(k,p):=\Big{|}\mathbb{E}_{S^{n}}\big{[}\langle\hat{f}_{k,p}(x),\psi_{1}(x)\rangle\,|\,x\in
H_{k}\big{]}-\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{k,p}(x),\psi_{1}(x)\rangle\,|\,x\in
H_{k}\big{]}\Big{|},$ (76)

then we have

$\displaystyle\sup_{k,p}E(k,p)\leq\sup_{k,p}pE(k,1)+(1-p)E(k,0)\leq\sup_{k,p}E(k,1)+\sup_{k,p}E(k,0).$
(77)

Now, to bound $E(k,1)$, we first rewrite the closed-form solution of
$\hat{f}_{k,1}(x)$ as

$\displaystyle\big{(}\hat{f}_{k,1}(x))(i)={\rm
sgn}\Big{(}\big{(}\ell_{k}(x)\big{)}(i)\geq\max_{j}\big{(}\ell_{k}(x)\big{)}(j)-d\Big{)}\prod_{j<i}l_{ij}(x)\prod_{j>i}u_{ij}(x),$
(78)

where $l_{ij}(x)$ and $u_{ij}(x)$ are defined as

$\displaystyle
l_{ij}(x):=1-\mathbb{I}_{\big{(}\psi_{0}(x)\big{)}(i)\leq\big{(}\psi_{0}(x)\big{)}(j)}\mathbb{I}_{\big{(}\ell_{k}(x)\big{)}(j)\geq\max_{t}\big{(}\ell_{k}(x)\big{)}(t)},$

and

$\displaystyle
u_{ij}(x):=1-\mathbb{I}_{\big{(}\psi_{0}(x)\big{)}(i)<\big{(}\psi_{0}(x)\big{)}(j)}\mathbb{I}_{\big{(}\ell_{k}(x)\big{)}(j)\geq\max_{t}\big{(}\ell_{k}(x)\big{)}(t)},$

respectively. Note that the only difference between the definition of
$u_{ij}(x)$ and $l_{ij}(x)$ is that $u_{ij}(x)$ permits the equality of
$\big{(}\psi_{0}(x)\big{)}(i)$ with other components, while that is not the
case for $l_{ij}(x)$. This difference lets us find the _first_ component with
the largest value of $\psi_{0}(x)$.

Now, we can rewrite ${\rm
sgn}\Big{(}\big{(}\ell_{k}(x)\big{)}(j)\geq\max_{t}\big{(}\ell_{k}(x)\big{)}(t)\Big{)}$
as the product

$\displaystyle{\rm
sgn}\Big{(}\big{(}\ell_{k}(x)\big{)}(j)\geq\max_{t}\big{(}\ell_{k}(x)\big{)}(t)-d\Big{)}:=\prod_{l\in[1:d]}{\rm
sgn}\Big{(}\big{(}\ell_{k}(x)\big{)}(j)\geq\big{(}\ell_{k}(x)\big{)}(l)\Big{)}.$

As shown in Lemma J.1, the class of such function has VC dimension of at most
$4$. Furthermore, multiplying a hypothesis class with a function such as ${\rm
sgn}\Big{(}\big{(}\psi_{0}(x)\big{)}(i)\geq\big{(}\psi_{0}(x)\big{)}(j)\Big{)}$
and ${\rm
sgn}\Big{(}\big{(}\psi_{0}(x)\big{)}(i)>\big{(}\psi_{0}(x)\big{)}(j)\Big{)}$
does not increase the VC dimension (See proof of Lemma J.1, and neither does
negation. Therefore, in RHS of (78) we can count $d$ number of functions, each
with a hypothesis class with the VC dimension of at most $4$, and therefore
using the early discussions in this proof (70),
$\big{(}\hat{f}_{k,1}(x)\big{)}(i)$ is within a function class with the VC
dimension of at most $8d\log(3d)$. Therefore, similar to (75) in previous
part, we can bound $\sup_{k,p}E(k,1)$ as

$\displaystyle\sup_{k,p}E(k,1)\leq$ $\displaystyle
2d\sqrt{\frac{8d\log(3d)\log(en/\big{(}8d\log(3d)\big{)}}{n}}$
$\displaystyle+4d\sqrt{\frac{\ln 4d/\epsilon}{n}},$ (79)

for $l\geq 8d\log(3d)$ with probability at least $1-\epsilon$.

We can similarly, show that $\sup_{k,p}E(k,0)$ is bounded as

$\displaystyle\sup_{k,p}E(k,0)\leq$ $\displaystyle
2d\sqrt{\frac{8d\log(3d)\log(en/\big{(}(8n+8)\log(3d)\big{)}}{n}}$
$\displaystyle+4d\sqrt{\frac{\ln 4d/\epsilon}{n}},$ (80)

Therefore, using (75), (76), (77), (79), (80), and the application
Bonferonni’s inequality we have

$\displaystyle\sup_{k,p}\Big{|}\mathbb{E}_{S^{n}}$
$\displaystyle\big{[}\langle
f^{*}_{k,p}(x),\psi_{0}(x)\rangle\big{]}-\mathbb{E}_{\mu}\big{[}\langle
f^{*}_{k,p}(x),\psi_{0}(x)\rangle\big{]}\Big{|}$ $\displaystyle\leq
6d\sqrt{\frac{8d\log(3d)\log\tfrac{el}{(8n+8)\log(3d)}}{l}}+12d\sqrt{\frac{\ln\frac{12d}{\epsilon}}{l}}$
(81) $\displaystyle:=d_{n}(\epsilon),$ (82)

with probability at least $1-\epsilon$. Therefore, by assuming
$\mathbb{E}_{S^{n}}\big{[}\langle
f^{*}_{k,p}(x),\psi_{1}(x)\rangle\big{]}\leq\alpha-d_{n}(\epsilon)$, we assure
that $\mathbb{E}_{\mu}\big{[}\langle
f^{*}_{k,p}(x),\psi_{1}(x)\rangle\big{]}\leq\alpha$, with probability at least
$1-\epsilon$, and this completes the proof.

##  Appendix K Proof of Theorem 5.3

We first introduce three lemmas that are useful in proving this theorem.

######  Lemma K.1.

If $\delta$ is an $\epsilon$-interior point of the set ${\cal
C}=\big{\\{}\mathbb{E}_{\mu}\big{[}\langle
f(x),\psi_{1}(x)\rangle\big{]}\,:\,f\in\Delta_{d}^{{\cal X}}\big{\\}}$, then
$\delta$ is $(\epsilon/2)$-interior point of ${\cal
D}=\big{\\{}\mathbb{E}_{S^{n}}\big{[}\langle
f(x),\psi_{1}(x)\rangle\big{]}\,:\,f\in\Delta_{d}^{{\cal X}}\big{\\}}$ with
probability $1-2e^{-\frac{l\epsilon^{2}}{4}}$.

###### Proof.

The proof of this lemma is a direct application of Hoeffding’s inequality. In
fact, for $\|\psi_{1}\|_{\infty}\leq C$ that inequality together with Hölder’s
inequality imply that

$\displaystyle\mathbb{P}\Big{(}\big{|}\mathbb{E}_{\mu}\big{[}\langle
f(x),\psi_{1}(x)\rangle\big{]}-\mathbb{E}_{S^{n}}\big{[}\langle
f(x),\psi_{1}(x)\rangle\big{]}\big{|}\geq\epsilon/2\Big{)}\leq
e^{-\frac{n\epsilon^{2}}{4C^{2}}}.$

Therefore, if there exists $f_{1}$ such that $\mathbb{E}_{\mu}\big{[}\langle
f_{1}(x),\psi_{1}(x)\rangle\big{]}=\epsilon$, then with probability at least
$1-e^{-\frac{n\epsilon^{2}}{4C^{2}}}$ we have
$\mathbb{E}_{S^{n}}\big{[}\langle
f_{1}(x),\psi_{1}(x)\rangle\big{]}\in[\epsilon/2,3\epsilon/2]$. Similarly, if
$f_{2}$ exists such that $\mathbb{E}_{\mu}\big{[}\langle
f_{1}(x),\psi_{1}(x)\rangle\big{]}=-\epsilon$, then with probability
$1-e^{-\frac{n\epsilon^{2}}{4C^{2}}}$ we have
$\mathbb{E}_{S^{n}}\big{[}\langle
f_{2}(x),\psi_{1}(x)\rangle\big{]}\in[-3\epsilon/2,-\epsilon/2]$. As a result
of Bonferroni’s inequality, with probability at least
$1-2e^{-\frac{n\epsilon^{2}}{4C^{2}}}$ both these events happen, and because
of the convexity of the set ${\cal D}$ we can say that with such probability
all values between $a_{0}\in[-3\epsilon/2,-\epsilon/2]$ and
$a_{1}\in[\epsilon/2,3\epsilon/2]$ are in ${\cal D}$ too. This, of course at
least contains the interval $[-\epsilon/2,\epsilon/2]$. ∎

######  Lemma K.2.

Assume that we have an approximation $\hat{\psi}_{1}(x)$ of $\psi_{1}(x)$ with
the error bounded as $\|\hat{\psi}_{1}(x)-\psi_{1}(x)\|_{\infty}\leq\epsilon$.
Further let $\epsilon^{\prime}\in\mathbb{R}^{+}$ such that
$\epsilon^{\prime}\geq\epsilon$. Now, if for
$\sigma\in\\{-\epsilon^{\prime},\epsilon^{\prime}\\}$ there exists a rule
$f\in\Delta_{d}^{{\cal X}}$ such that $\mathbb{E}_{\mu}\big{[}\langle
f(x),\psi_{1}(x)\rangle\big{]}=\delta+\sigma$, then there exists
$k\in\mathbb{R}$ as well as $p\in[0,1]$ such that
$\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{k,p}(x),\hat{\psi}_{1}(x)\rangle\big{]}=\delta+\frac{\epsilon^{\prime}-\epsilon}{2}$.

###### Proof.

Firstly, because of Hölder’s inequality we know that

$\displaystyle\Big{|}\mathbb{E}_{\mu}\big{[}\langle
f(x),\psi_{1}(x)\rangle\big{]}-\mathbb{E}_{\mu}\big{[}\langle
f(x),\hat{\psi}_{1}(x)\rangle\big{]}\Big{|}\leq\epsilon\|f^{*}_{k,p}(x)\|_{1}=\epsilon,$

for all $f\in\Delta_{d}^{{\cal X}}$. Therefore, by setting
$\sigma=\epsilon^{\prime}$ and $\sigma=-\epsilon^{\prime}$, we can show that
for $f_{1}\in\Delta_{d}^{{\cal X}}$ such that

$\displaystyle\mathbb{E}_{\mu}\big{[}\langle
f_{1}(x),\psi_{1}(x)\rangle\rangle\big{]}=\delta+\epsilon^{\prime},$

then

$\displaystyle\mathbb{E}_{\mu}\big{[}\langle
f_{1}(x),\hat{\psi}_{1}(x)\rangle\big{]}\geq\delta+\epsilon^{\prime}-\epsilon,$

and where for $f_{2}\in\Delta_{d}^{{\cal X}}$

$\displaystyle\mathbb{E}_{\mu}\big{[}\langle
f_{2}(x),\psi_{1}(x)\rangle\rangle\big{]}=\delta-\epsilon^{\prime},$

then

$\displaystyle\mathbb{E}_{\mu}\big{[}\langle
f_{2}(x),\hat{\psi}_{1}(x)\rangle\big{]}\leq\delta-\epsilon^{\prime}+\epsilon.$

Now, because of step (iii) of the proof of Theorem 4.1, we know that the set
of constraints for all rules within $\Delta_{d}^{{\cal X}}$ is convex.
Therefore, since we can achieve two points $f_{1},f_{2}$ such that the
constraint $\mathbb{E}_{\mu}\big{[}\langle
f_{i}(x),\hat{\psi}_{1}(x)\rangle\big{]}$ can achieve two points above
$\delta+\epsilon^{\prime}-\epsilon$ and below
$\delta-\epsilon^{\prime}+\epsilon$, then for each
$c\in[\delta-\epsilon^{\prime}+\epsilon,\delta+\epsilon^{\prime}-\epsilon]$
there exists $f\in\Delta_{d}^{{\cal X}}$ such that
$\mathbb{E}_{\mu}\big{[}\langle f(x),\hat{\psi}_{1}(x)\rangle\big{]}=c$. Now,
let $c=\delta+\frac{\epsilon^{\prime}-\epsilon}{2}$. In the following, we show
that there exists $k\in\mathbb{R}$ and $p\in[0,1]$ such that further
$\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{k,p}(x),\hat{\psi}_{1}(x)\rangle\big{]}=c$.

To that end, we first remind that Lemma I.2 shows that
$\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{k,0}(x),\hat{\psi}_{1}(x)\rangle\big{]}$
is monotonically non-increasing in terms of $k$. We show that for
$k\in\mathbb{R}^{-}$ we have
$\max\hat{\psi}_{1}(x)-\langle\hat{f}_{k,0}(x),\hat{\psi}_{1}(x)\rangle\leq-\frac{2}{k}$.
The reason is that if $j\in\mathop{\rm
argmax}\limits_{l}\big{(}\hat{\psi}_{0}(x)-k\hat{\psi}_{1}(x)\big{)}(l)$ and
$j^{\prime}\in\mathop{\rm
argmax}\limits_{l}\big{(}\hat{\psi}_{1}(x)\big{)}(l)$, then we have

$\displaystyle\big{(}\hat{\psi}_{0}(x)-k\hat{\psi}_{1}(x)\big{)}(j)\geq\big{(}\hat{\psi}_{0}(x)-k\hat{\psi}_{1}(x)\big{)}(j^{\prime}),$

which concludes that

$\displaystyle-k\big{[}\big{(}\hat{\psi}_{1}(x)\big{)}(j)-\big{(}\hat{\psi}_{1}(x)\big{)}(j^{\prime})\big{]}\geq\big{(}\hat{\psi}_{0}(x)\big{)}(j^{\prime})-\big{(}\hat{\psi}_{0}(x)\big{)}(j)\geq-2.$

Therefore, since

$\displaystyle\mathbb{E}_{\mu}\big{[}\langle\mathop{\rm
argmax}\limits\hat{\psi}_{1}(x),\hat{\psi}_{1}(x)\rangle\big{]}$
$\displaystyle=\max_{f\in\Delta_{d}^{{\cal X}}}\mathbb{E}_{\mu}\big{[}\langle
f(x),\hat{\psi}_{1}(x)\rangle\big{]}\geq\delta+\epsilon^{\prime}-\epsilon,$

where the last inequality holds due to the existence of $f_{1}$, then for
$k\leq-8/(\epsilon^{\prime}-\epsilon)$ we have

$\displaystyle\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{k,0}(x),\hat{\psi}_{1}(x)\rangle\big{]}\geq\delta+\epsilon^{\prime}-\epsilon-\frac{2}{-8/(\epsilon^{\prime}-\epsilon)}\geq\delta+3\frac{\epsilon^{\prime}-\epsilon}{4}.$

Similarly, if we let $k\geq 8/(\epsilon^{\prime}-\epsilon)$ we can prove that

$\displaystyle\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{k,0}(x),\hat{\psi}_{1}(x)\rangle\big{]}\leq\delta-\epsilon^{\prime}+\epsilon+2l\leq\delta-3\frac{\epsilon^{\prime}-\epsilon}{4}.$

As a result, the set ${\cal
C}=\\{k:\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{k,0}(x),\hat{\psi}_{1}(x)\rangle\big{]}\geq
c\\}$ is non-empty and bounded below by
$-\frac{8}{\epsilon^{\prime}-\epsilon}$. Therefore, its infimum exists and is
also bounded below by $-\frac{8}{\epsilon^{\prime}-\epsilon}$. Let us name
that infimum $\hat{k}$. Now, if
$\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{k,0,0}(x),\hat{\psi}_{1}(x)\rangle\big{]}$
is continuous at $k=\hat{k}$, then we can show that
$\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{\hat{k},0}(x),\hat{\psi}_{1}(x)\rangle\big{]}=c$.
If not, then as shown in step (ii) of the proof of Theorem 4.1, and in
particular in (69), there exists $p$ such that
$\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{\hat{k},p}(x),\hat{\psi}_{1}(x)\rangle\big{]}=c$.
This completes the proof. ∎

######  Lemma K.3.

If $\|\hat{\psi}_{0}-\psi_{0}\|_{\infty}\leq\delta_{0}$ and
$\|\hat{\psi}_{1}-\psi_{1}\|_{\infty}\leq\delta_{1}$, and for $k\in[-K,K]$,
and $k^{\prime}\leq k-\frac{2(\delta_{0}+K\delta_{1})}{T}$ for
$T\in\mathbb{R}^{+}$, then we have

$\displaystyle\mathbb{E}\big{[}\langle\hat{f}_{k,0,0}(x)-f^{*}_{k^{\prime},0}(x),\psi_{1}(x)\rangle\big{]}\leq
T.$

###### Proof.

The proof of this lemma bears similarity to that of Lemma I.2. Here too, we
define $\hat{\ell}_{k}(x)=\hat{\psi}_{0}(x)-k\hat{\psi}_{1}(x)$. Next, we have

$\displaystyle\hat{f}_{k,0}(x)=\left\\{\begin{array}[]{cc}1&i=\min\\{\mathop{\rm
argmin}\limits_{i\in\mathop{\rm
argmax}\limits_{l}\big{(}\hat{\ell}_{k}(x)\big{)}(l)}\hat{\psi}_{1}(x)\\}\\\
0&\text{otherwise}\end{array}\right..$ (85)

Next, we need to show that
$\big{(}\psi_{1}(x)\big{)}(j_{1})=\langle{r}_{k^{\prime},0}(x),\psi_{1}(x)\rangle\geq\langle\hat{f}_{k,0,0}(x),{\psi}_{0}(x)\rangle-T=\big{(}{\psi}_{0}(x)\big{)}(j_{2})-T$.
Assume otherwise, meaning that
$\big{(}\psi_{1}(x)\big{)}(j_{1})<\big{(}\psi_{1}(x)\big{)}(j_{2})-T$. In this
case, we have

$\displaystyle\max\hat{\ell}_{k}(x)$
$\displaystyle\overset{(a)}{=}\big{(}\hat{\ell}_{k}(x)\big{)}(j_{2})$
$\displaystyle=\big{(}\ell_{k}(x)\big{)}(j_{2})+\big{(}\hat{\psi}_{0}(x)-\psi_{0}(x)\big{)}(j_{2})-k\big{(}\hat{\psi}_{1}(x)-\psi_{1}(x)\big{)}(j_{2})$
$\displaystyle=\big{(}\ell_{k^{\prime}}(x)\big{)}(j_{2})-(k-k^{\prime})\big{(}\psi_{1}(x)\big{)}(j_{2})+\big{(}\hat{\psi}_{0}(x)-\psi_{0}(x)\big{)}(j_{2})-k\big{(}\hat{\psi}_{1}(x)-\psi_{1}(x)\big{)}(j_{2})$
$\displaystyle\overset{(b)}{\leq}\big{(}\ell_{k^{\prime}}(x)\big{)}(j_{2})-(k-k^{\prime})\big{(}\psi_{1}(x)\big{)}(j_{2})+(\delta_{0}+K\delta_{1})$
$\displaystyle\overset{(c)}{<}\big{(}\ell_{k^{\prime}}(x)\big{)}(j_{2})-(k-k^{\prime})\big{(}\psi_{1}(x)\big{)}(j_{1})-(k-k^{\prime})T+(\delta_{0}+K\delta_{1})$
$\displaystyle\overset{(d)}{\leq}\big{(}\ell_{k^{\prime}}(x)\big{)}(j_{1})-(k-k^{\prime})\big{(}\psi_{1}(x)\big{)}(j_{1})-(k-k^{\prime})T+(\delta_{0}+K\delta_{1})$
$\displaystyle\overset{(e)}{\leq}\big{(}\ell_{k^{\prime}}(x)\big{)}(j_{1})-(k-k^{\prime})\big{(}\psi_{1}(x)\big{)}(j_{1})-2\frac{\delta_{0}+K\delta_{1}}{T}T+(\delta_{0}+K\delta_{1})$
$\displaystyle=\big{(}\ell_{k^{\prime}}(x)\big{)}(j_{1})-(k-k^{\prime})\big{(}\psi_{1}(x)\big{)}(j_{1})-(\delta_{0}+K\delta_{1})$
$\displaystyle=\big{(}\ell_{k}(x)\big{)}(j_{1})-(\delta_{0}+K\delta_{1})$
$\displaystyle=\big{(}\hat{\ell}_{k}(x)\big{)}(j_{1})-(\delta_{0}+K\delta_{1})-\big{(}\hat{\psi}_{0}(x)-\psi_{0}(x)\big{)}(j_{1})+k\big{(}\hat{\psi}_{1}(x)-\psi_{1}(x)\big{)}(j_{1})$
$\displaystyle\overset{(f)}{\leq}\big{(}\hat{\ell}_{k}(x)\big{)}(j_{1})-(\delta_{0}+K\delta_{1})+(\delta_{0}+K\delta_{1})=\big{(}\hat{\ell}_{k}(x)\big{)}(j_{1}),$

which is a contradiction. Note that $(a)$ holds because of definition of
$j_{2}$ and (85), $(b)$ holds due to approximation assumptions
$\|\hat{\psi}_{0}-\psi_{0}\|_{\infty}\leq\delta_{0}$ and
$\|\hat{\psi}_{1}-\psi_{1}\|_{\infty}\leq\delta_{1}$, $(c)$ holds because of
the assumption
$\big{(}\psi_{1}(x)\big{)}(j_{1})<\big{(}\psi_{1}(x)\big{)}(j_{2})-T$, $(d)$
is followed by the definition of $j_{1}$ on maximizing $\ell_{k^{\prime}}(x)$,
and $(e)$ holds because $k\geq
k^{\prime}+\frac{2(\delta_{0}+K\delta_{1})}{T}$, and $(f)$ is followed by
approximation assumptions. ∎

In order to prove this theorem, we define a measure of distance between two
rules $f_{1},f_{2}\in\Delta_{d}^{\mathbb{R}}$ as

$\displaystyle D_{k}(f_{1},f_{2}):=\mathbb{E}\big{[}\langle
f_{1}(x)-f_{2}(x),\psi_{0}(x)-k\psi_{1}(x)\rangle\big{]}.$ (86)

Using this measure of distance, the difference of objectives between two rules
$f_{1}$ and $f_{2}$ can be written as

$\displaystyle\mathbb{E}\big{[}\langle
f_{1}(x),\psi_{0}(x)\rangle\big{]}-\mathbb{E}\big{[}\langle
f_{2}(x),\psi_{0}(x)\rangle\big{]}=$ $\displaystyle D_{k^{*}}(f_{1},f_{2})$
$\displaystyle+k^{*}\Big{(}\mathbb{E}\big{[}\langle
f_{1}(x),\psi_{1}(x)\rangle\big{]}-\mathbb{E}\big{[}\langle
f_{2}(x),\psi_{1}(x)\rangle\big{]}\Big{)}.$ (87)

Therefore, if two rules achieve similar constraints, and if
$D_{k}(f_{1},f_{2})$ is small enough, we can prove that the two rules achieve
similar objectives too, since $k$ is bounded above by $K$.

In fact, if we let $f_{1}(x)=f^{*}_{k,p}(x)$ and
$f_{2}(x):=\hat{f}_{\hat{k},\hat{p}}$, where $k$ and $p$ are optimal solutions
as in Theorem 4.2, then due to this optimality, and because
$\mathbb{E}\big{[}\langle\hat{f}_{\hat{k},\hat{p}},\psi_{1}(x)\rangle\big{]}\leq\delta$
with probability at least $1-\epsilon$ as shown in Theorem 5.1, then LHS of
(87) is positive with at least the same probability. In this proof, we show
that how large is that term, and therefore, we show that how sub-optimal is
$\hat{f}_{\hat{k},\hat{p}}$ in terms of the objective.

To that end, we first bound the difference between constraints. This bound can
be achieved similar to the proof of Theorem 5.1. In fact, there we showed that
if the empirical constraint
$\mathbb{E}_{S^{n}}\big{[}\langle\hat{f}_{\hat{k},\hat{p}},\psi_{1}(x)\rangle\big{]}\leq\delta-
d_{n}(\pi)$, then using (81) the true expectation is bounded as
$\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{\hat{k},\hat{p}},\psi_{1}(x)\rangle\big{]}\leq\delta$
with probability at least $1-\pi$. However, (81) is symmetric in empirical and
true constraint, i.e., if we show that
$\mathbb{E}_{S^{n}}\big{[}\langle\hat{f}_{\hat{k},\hat{p}},\psi_{1}(x)\rangle\big{]}\geq\delta-
d_{n}(\pi)$, then we have
$\mathbb{E}_{\mu}\big{[}\langle\hat{f}_{\hat{k},\hat{p}},\psi_{1}(x)\rangle\big{]}\geq\delta-2d_{n}(\pi)$
with probability at least $1-\pi$.

To show
$\mathbb{E}_{S^{n}}\big{[}\langle\hat{f}_{\hat{k},\hat{p}},\psi_{1}(x)\rangle\big{]}\geq\delta-
d_{n}(\pi)$, we follow three steps, (i) because $\delta$ is
$(\epsilon_{l},\epsilon_{u})$-interior point of the set of constraints, i.e.,
$(\delta-\epsilon_{l},\delta+\epsilon_{u})$ is a subset of all plausible
constraints, then $\delta-d_{n}(\pi)$ is
$(\epsilon_{l}-d_{n}(\pi),\epsilon_{u}+d_{n}(\pi))$-interior point. Now, using
Lemma K.1 and by setting
$\epsilon^{\prime}=\min\\{\epsilon_{l}-d_{n}(\pi),\epsilon_{u}+d_{n}(\pi)\\}$
we can show that $\delta-d_{n}(\pi)$ is $\epsilon^{\prime}/2$-interior point
of the empirical constraints with probability at least
$1-2e^{-\frac{n\epsilon^{\prime 2}}{4}}$, (ii) using the first step and
assuming $d_{n}(\pi)\leq\epsilon_{l}/2$ we conclude that $\delta-d_{n}(\pi)$
is $d_{n}(\pi)/2$-interior point of the empirical constraints with the
aforementioned probability, (iii) because of Lemma K.2, we conclude that for
$\epsilon=d_{n}(\pi)/2$, and with probability at least
$1-2e^{-\frac{n\epsilon^{\prime 2}}{4}}$ there exists $k\in\mathbb{R}$ and
$p\in[0,1]$ such that
$\mathbb{E}_{S^{n}}\big{[}\langle\hat{f}_{k,p}(x),\hat{\psi}_{1}(x)\rangle\big{]}=\delta-
d_{n}(\pi)+\frac{d_{n}(\pi)/2-\epsilon}{2}=\delta-d_{n}(\pi)$. As a result of
the above discussion we conclude that with probability at least
$1-\pi-2e^{-\frac{n\epsilon^{\prime 2}}{4}}$ there exists $k$ and $p$ such
that
$\delta\geq\mathbb{E}\big{[}\langle\hat{f}_{k,p}(x),\psi_{1}(x)\rangle\big{]}\geq\delta-2d_{n}(\pi)$.
Now, since we know that $\mathbb{E}\big{[}\langle
f_{1}(x),\psi_{1}(x)\rangle\big{]}=\mathbb{E}\big{[}\langle
f^{*}_{k,p}(x),\psi_{1}(x)\rangle\big{]}=\delta$, then we have

$\displaystyle 0\leq\mathbb{E}\big{[}\langle
f_{1}(x),\psi_{1}(x)\rangle\big{]}-\mathbb{E}\big{[}\langle
f_{2}(x),\psi_{1}(x)\rangle\big{]}\leq 2d_{l}(\pi),$ (88)

with probability at least $1-\pi-2e^{-\frac{n\epsilon^{\prime 2}}{4}}$.

The above discussion together with (87) and the assumption of boundedness of
$k$ shows that the difference of objectives is bounded with a high
probability, if we bound $D_{k}(f_{1},f_{2})$. However, before we proceed with
bounding that term, we should derive a relationship between $\hat{k}$ and
$k^{*}$ for the reasons that we see in proving boundedness of
$D_{k}(f_{1},f_{2})$.

We have already shown that there exists $\hat{p}\in[0,1]$ such that
$\delta\geq\mathbb{E}\big{[}\langle\hat{f}_{\hat{k},\hat{p}},\psi_{1}(x)\rangle\big{]}\geq\delta-2d_{l}(\pi)$.
Here, Lemma K.3 shows that for
$k^{\prime}=k-\frac{2(\delta_{0}+K\delta_{1})}{T}$ we have
$\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},0},\psi_{1}(x)\rangle\big{]}\geq\delta-2d_{l}(\pi)-T$ with
probability at least $1-\pi-2e^{-\frac{n\epsilon^{\prime 2}}{4}}$. Moreover,
using symmetry in Lemma K.3 and for
$k^{\prime\prime}=k+\frac{2(\delta_{0}+K\delta_{1})}{T}$ we have
$\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime\prime},0}(x)-\hat{f}_{k}(x),\hat{\psi}_{1}(x)\rangle\big{]}\leq
T$. Now, since $\|\psi_{1}(x)-\hat{\psi}_{1}(x)\|_{\infty}\leq\delta_{0}$,
using Hölder’s inequality we conclude that $\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime\prime},0}(x)-\hat{f}_{k}(x),\hat{\psi}_{1}(x)\rangle\big{]}\leq
T+2\delta_{1}$, and consequently $\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime\prime},0}(x),\hat{\psi}_{1}(x)\rangle\big{]}\leq\delta+T+2\delta_{0}$

Now that we have found a lower-bound on constraint of the rule
$f^{*}_{k-q}(x)$ for $q=\frac{2(\delta_{0}+K\delta_{1})}{T}$, then if we find
an upper bound on the constraint of the rule $f^{*}_{k^{*}+e}(x)$ for an
$e\in\mathbb{R}^{+}$, then we can use monotonicity of the constraint of
$f^{*}_{k}$ in terms of $k$ and prove a relationship between $k$ and $k^{*}$.
To that end, we use detection assumption with which we can show that

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k^{*}+\tfrac{1}{C}(2d_{n}(\pi)+T)^{1/\gamma}},\psi_{1}(x)\rangle\big{]}\leq\delta-2d_{n}(\pi)-T,$

where we assume that $d_{n}(\pi)\leq\frac{(C\Delta)^{\gamma}-T}{2}$. Now,
using previous discussions conclude that

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k^{*}+\tfrac{1}{C}(2d_{n}(\pi)+T)^{1/\gamma}},\psi_{1}(x)\rangle\big{]}\leq\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime},0},\psi_{1}(x)\rangle\big{]},$

with probability at least $1-\pi-2e^{-\frac{n\epsilon^{\prime 2}}{4}}$. This
together with the first part of Lemma I.2 shows that $k^{\prime}\leq
k^{*}+\tfrac{1}{C}(2d_{n}(\pi)+T)^{1/\gamma}$, or equivalently $k\leq
k^{*}+\frac{2(\delta_{0}+K\delta_{1})}{T}+\tfrac{1}{C}(2d_{n}(\pi)+T)^{1/\gamma}$
with probability at least $1-\pi-2e^{-\frac{n\epsilon^{\prime 2}}{4}}$. Since
we know that $\gamma$ is clamped above by $1$, and using the inequality
$(1+x)^{a}\leq 1+ax$ for $a\geq 1$ we can substitute the above inequality with
$k\leq
k^{*}+\frac{2(\delta_{0}+K\delta_{1})}{T}+\frac{\big{(}2d_{n}(\pi)\big{)}^{1/\gamma}}{C}\big{(}1+\frac{T}{\gamma(2d_{n}(\pi))^{1/\gamma}}\big{)}$.
Now optimizing over $T$ leads in $T=\sqrt{2\gamma C(\delta_{0}+K\delta_{1})}$,
which concludes that $k\leq k^{*}+\Delta_{u}k$ with the aforementioned
probability, where
$\Delta_{u}k=\frac{\big{(}2d_{n}(\pi)\big{)}^{1/\gamma}}{C}+2\sqrt{\frac{2(\delta_{0}+K\delta_{1})}{\gamma
C}}$, if we have $d_{n}(\pi)\leq\frac{(C\Delta)^{\gamma}-\sqrt{2\gamma
C(\delta_{0}+K\delta_{1})}}{2}$

Similarly, using sensitivity assumption, we have

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k^{*}+\tfrac{1}{C}(2\delta_{1}+T)^{1/\gamma}}(x),\psi_{1}(x)\rangle\big{]}\geq\delta+2\delta_{1}+T,$

where $\frac{(2\delta_{1}+T)^{1/\gamma}}{C}\leq\Delta$. Next, using previous
discussions conclude that

$\displaystyle\mathbb{E}\big{[}\langle
f^{*}_{k^{*}+\tfrac{1}{C}(2\delta_{1}+T)^{1/\gamma}}(x),\psi_{1}(x)\rangle\big{]}\geq\mathbb{E}\big{[}\langle
f^{*}_{k^{\prime\prime},0}(x),\psi_{1}(x)\rangle\big{]},$

with the aforementioned probability. This, again, together with the first part
of Lemma I.2 shows that $k^{\prime\prime}\geq
k^{*}-\tfrac{1}{C}(2\delta_{1}+T)^{1/\gamma}$, or equivalently $k\geq
k^{*}-\tfrac{1}{C}(2\delta_{1}+T)^{1/\gamma}-\frac{2(\delta_{0}+K\delta_{1})}{T}$.
Therefore, by setting $T=\sqrt{2\gamma C(\delta_{0}+K\delta_{1})}$ we conclude
that $k\geq k^{*}-\Delta_{l}k$ where
$\Delta_{l}k=\frac{(2\delta_{1})^{1/\gamma}}{C}+2\sqrt{\frac{2(\delta_{0}+K\delta_{1})}{\gamma
C}}$, and assuming $\frac{\big{(}2\delta_{1}+\sqrt{2\gamma
C(\delta_{0}+K\delta_{1})}\big{)}^{1/\gamma}}{C}\leq\Delta$.

Next, we turn into bounding $D_{k^{*}}(f_{1},f_{2})$. To that end, we first
note that

$\displaystyle t_{x}(k^{*}):=\langle
f^{*}_{k^{*},p}(x),\psi_{0}(x)-k^{*}\psi_{1}(x)\rangle=\max_{i}\big{(}\psi_{0}(x)-k^{*}\psi_{1}(x)\big{)}(i),$
(89)

for all $p\in[0,1]$. This is followed by the definition of
$f^{*}_{k^{*},p}(\cdot)$. Similarly, we can show that

$\displaystyle\hat{t}_{x}(\hat{k}):=\langle\hat{f}_{\hat{k},p}(x),\hat{\psi}_{0}(x)-k^{*}\hat{\psi}_{1}(x)\rangle=\max_{i}\big{(}\hat{\psi}_{0}(x)-\hat{k}\hat{\psi}_{1}(x)\big{)}(i),$

for all $p\in[0,1]$. Now, we can rewrite $D_{k^{*}}(f_{1},f_{2})$ as

$\displaystyle D_{k^{*}}(f_{1},f_{2})$ $\displaystyle=\mathbb{E}\big{[}\langle
f^{*}_{k^{*},p}(x)-\hat{f}_{\hat{k},\hat{p}}(x),\psi_{0}-k^{*}\psi_{1}(x)\rangle\big{]}$
$\displaystyle=\mathbb{E}[t_{x}(k^{*})]-\mathbb{E}\big{[}\langle\hat{f}_{\hat{k},\hat{p}}(x),\psi_{0}-k^{*}\psi_{1}(x)\rangle\big{]}$
$\displaystyle=\mathbb{E}[t_{x}(k^{*})]-\mathbb{E}\big{[}\langle\hat{f}_{\hat{k},\hat{p}}(x),\hat{\psi}_{0}-k^{*}\hat{\psi}_{1}(x)\rangle\big{]}$
$\displaystyle\phantom{=t(k^{*})}-\mathbb{E}\big{[}\langle\hat{f}_{\hat{k},\hat{p}}(x),(\psi_{0}(x)-\hat{\psi}_{0}(x))-k^{*}(\psi_{1}(x)-\hat{\psi}_{1}(x)\rangle\big{]}$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}[t_{x}(k^{*})]-\mathbb{E}\big{[}\langle\hat{f}_{\hat{k},\hat{p}}(x),\hat{\psi}_{0}-k^{*}\hat{\psi}_{1}(x)\rangle\big{]}+\delta_{0}+K\delta_{1}$
$\displaystyle=\mathbb{E}[t_{x}(k^{*})]-\mathbb{E}[\hat{t}_{x}(\hat{k})]+(k^{*}-k)\mathbb{E}\big{[}\langle\hat{f}_{\hat{k},\hat{p}}(x),\hat{\psi}_{0}(x)\rangle\big{]}+\delta_{0}+K\delta_{1}$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}[t_{x}(k^{*})]-\mathbb{E}[\hat{t}_{x}(\hat{k})]+|k^{*}-\hat{k}|+\delta_{0}+K\delta_{1},$
(90)

where $(a)$ and $(b)$ hold due to Hölder’s inequality.

Next, we show Lipschitzness of $t(k)$ using its structure. In fact, due to its
definition, $t(k)$ is the maximum of a set of lines with
$\\{t_{i}=\big{(}\psi_{0}(x)\big{)}(i)-k\big{(}\psi_{1}(x)\big{)}(i)\\}_{i=1}^{n+1}$
in terms of $k$ with slope $m_{i}=-\big{(}\psi_{1}(x)\big{)}(i)$ and
$y$-intercept of $b_{i}=\big{(}\psi_{0}(x)\big{)}(i)$. Therefore, such
piecewise-linear function has a Lipschitz factor equal to the maximum slope of
the lines, which in here is equal to
$\max_{i}m_{i}=\max_{i}\Big{|}\big{(}\psi_{1}(x)\big{)}(i)\Big{|}\leq 1$.
Therefore, $t(k)$ is a $1$-Lipschitz function. Therefore, using (90) we can
bound $D_{k^{*}}(f_{1},f_{2})$ as

$\displaystyle D_{k^{*}}(f_{1},f_{2})$
$\displaystyle\leq\mathbb{E}[t_{x}(\hat{k})-\hat{t}_{x}(\hat{k})]+2|k^{*}-\hat{k}|+\delta_{0}+K\delta_{1}$
$\displaystyle=\mathbb{E}[\max_{i}\big{(}\psi_{0}(x)-\hat{k}\psi_{1}(x)\big{)}(i)-\max_{i}\big{(}\hat{\psi}_{0}(x)-\hat{k}\hat{\psi}_{1}(x)\big{)}(i)+2|k^{*}-\hat{k}|+\delta_{0}+K\delta_{1}$
$\displaystyle\overset{(a)}{\leq}2|k^{*}-\hat{k}|+2(\delta_{0}+K\delta_{1}),$

where $(a)$ holds because each component of
$\big{(}\psi_{0}(x)-\hat{k}\psi_{1}(x)\big{)}$ and
$\big{(}\hat{\psi}_{0}(x)-\hat{k}\hat{\psi}_{1}(x)\big{)}$ is bounded by
$\delta_{0}+K\delta_{1}$, and because the maximum operator is a norm, and
therefore satisfies sub-additivity. Finally, since we have bounded $\Delta\leq
k^{*}-\hat{k}\leq\Delta_{l}$ with probability at least
$1-\pi-2e^{-n\epsilon^{\prime 2}/4}$, then we have

$\displaystyle D_{k}(f_{1},f_{2})$ $\displaystyle\leq
2\max\\{\Delta,\Delta_{l}\\}+2(\delta_{0}+K\delta_{1})$
$\displaystyle=2\frac{\big{(}2\max\\{d_{n}(\pi),\delta_{1}\\}\big{)}^{1/\gamma}}{C}+4\sqrt{\frac{2(\delta_{0}+K\delta_{1})}{\gamma
C}}+2(\delta_{0}+K\delta_{1}),$

with such probability. This, together with (87) and (88) shows that

$\displaystyle\mathbb{E}\big{[}\langle
f_{1}(x),\psi_{0}(x)\rangle\big{]}-\mathbb{E}\big{[}\langle
f_{2}(x),\psi_{0}(x)\rangle\big{]}\leq$ $\displaystyle
2\frac{\big{(}2\max\\{d_{n}(\pi),\delta_{1}\\}\big{)}^{1/\gamma}}{C}+4\sqrt{\frac{2(\delta_{0}+K\delta_{1})}{\gamma
C}}$ $\displaystyle+2(\delta_{0}+K\delta_{1})+2Kd_{n}(\pi),$

which completes the proof.

##  Appendix L Proof of Theorem F.1

To prove this theorem, we first prove the following auxiliary lemma

######  Lemma L.1.

For $\alpha,\epsilon\geq 0$, the following holds

$\displaystyle\min_{r_{i}\geq
0,\sum_{i=1}^{n}r_{i}\leq\alpha}\sum_{i=1}^{n}r_{i}d_{i}-\min_{r_{i}\geq
0,\sum_{i=1}^{n}r_{i}\leq\alpha+\epsilon}\sum_{i=1}^{n}r_{i}d_{i}\leq\epsilon\cdot\max_{i\in[1:n]}|d_{i}|$

###### Proof of lemma.

We know that for every positive vector $\mathbf{r}$ with
$\sum_{i=1}^{n}r_{i}\leq\alpha+\epsilon$, we could rewrite that as a sum of
two vectors $\mathbf{r}=\mathbf{r}^{\prime}+\mathbf{r}^{\prime\prime}$ for
which

$\displaystyle\sum_{i=1}^{n}r^{\prime}_{i}\leq\alpha,$

and

$\displaystyle\sum_{i=1}^{n}r^{\prime\prime}_{i}\leq\epsilon.$

As a result, we can rewrite $\min_{r_{i}\geq
0,\sum_{i=1}^{n}r_{i}\leq\alpha+\epsilon}\sum_{i=1}^{n}r_{i}d_{i}$ as

$\displaystyle\min_{r_{i}\geq
0,\sum_{i=1}^{n}r_{i}\leq\alpha+\epsilon}\sum_{i=1}^{n}r_{i}d_{i}$
$\displaystyle\geq\min_{r^{\prime}_{i}\geq
0,\sum_{i=1}^{n}r^{\prime}_{i}\leq\alpha}\min_{r^{\prime\prime}_{i}\geq
0,\sum_{i=1}^{n}r^{\prime\prime}_{i}\leq\epsilon}\sum_{i=1}^{n}(r^{\prime}_{i}+r^{\prime\prime}_{i})\cdot
d_{i}$ $\displaystyle=\min_{r^{\prime}_{i}\geq
0,\sum_{i=1}^{n}r^{\prime}_{i}\leq\alpha}r^{\prime}_{i}d_{i}+\min_{r^{\prime\prime}_{i}\geq
0,\sum_{i=1}^{n}r^{\prime\prime}_{i}\leq\epsilon}\sum_{i=1}^{n}r^{\prime\prime}_{i}d_{i}.$

Hence, we have that

$\displaystyle\min_{r_{i}\geq
0,\sum_{i=1}^{n}r_{i}\leq\alpha+\epsilon}\sum_{i=1}^{n}r_{i}d_{i}-\min_{r^{\prime}_{i}\geq
0,\sum_{i=1}^{n}r^{\prime}_{i}\leq\alpha}r^{\prime}_{i}d_{i}$
$\displaystyle\geq-\big{|}\min_{r^{\prime\prime}_{i}\geq
0,\sum_{i=1}^{n}r^{\prime\prime}_{i}\leq\epsilon}\sum_{i=1}^{n}r^{\prime\prime}_{i}d_{i}\big{|}$
$\displaystyle\overset{(a)}{\geq}-\sum_{i=1}^{n}r^{\prime\prime}_{i}\cdot\max_{i\in[1:n]}|d_{i}|\geq-\epsilon\cdot\max_{i\in[1:n]}|d_{i}|,$

where $(a)$ holds using Hölder’s inequality. ∎

Next, we know that the optimal deterministic deferral policy should satisfy

$\displaystyle\min_{r(x_{i})\in\\{0,1\\},\,\frac{1}{n}\sum_{i}r(x_{i})\leq
b}\frac{1}{n}\sum_{i}r(x_{i})\ell_{H}(x_{i},y_{i},m_{i})+\big{(}1-r(x_{i})\big{)}\cdot\ell_{AI}(x_{i},y_{i})$
$\displaystyle=\frac{1}{n}\sum_{i}\ell_{AI}(x_{i},y_{i})+\min_{r(x_{i})\in\\{0,1\\},\,\frac{1}{n}\sum_{i=1}^{n}r(x_{i})\leq
b}\frac{1}{n}\sum_{i=1}^{n}r(x_{i})\big{(}\ell_{H}(x_{i},y_{i},m_{i})-\ell_{AI}(x_{i},y_{i})\big{)}$
$\displaystyle\overset{(a)}{=}\frac{1}{n}\sum_{i}\ell_{AI}(x_{i},y_{i})+\underbrace{\min_{r(x_{i})\in\\{0,1\\},\,\sum_{i=1}^{n}r(x_{i})\leq\lfloor
bn\rfloor}\frac{1}{n}\sum_{i=1}^{n}r(x_{i})\big{(}\ell_{H}(x_{i},y_{i},m_{i})-\ell_{AI}(x_{i},y_{i})\big{)}}_{B},$

where $(a)$ holds because $r(x_{i})\in\\{0,1\\}$ and therefore $\sum
r(x_{i})\leq bn$ if and only if $\sum r(x_{i})\leq\lfloor bn\rfloor$. Now, we
turn to examining $B$. To that end, we first consider the following
optimization problem:

$\displaystyle\min_{r(x_{i})\in[0,1],\sum_{i=1}^{n}r(x_{i})\leq\lfloor
bn\rfloor}\frac{1}{n}\sum_{i=1}^{n}r(x_{i})\big{(}\ell_{H}(x_{i},y_{i},m_{i})-\ell_{AI}(x_{i},y_{i})\big{)}.$
(91)

For a minimizer $\mathbf{r}^{*}$ of the above problem, we could form
$\hat{\mathbf{r}}$ as

$\displaystyle\hat{r}_{i}=\left\\{\begin{array}[]{cc}r^{*}_{i}(x_{i})&\ell_{H}(x_{i},y_{i},m_{i})-\ell_{AI}(x_{i},y_{i})\leq
0\\\
0&\ell_{H}(x_{i},y_{i},m_{i})-\ell_{AI}(x_{i},y_{i})>0\end{array}\right..$

One can see that $\hat{\mathbf{r}}(x)$ is also a minimizer of the above
problem. Hence, without loss of generality, we assume that there is an optimal
deferral policy that has only non-zero value when $(x,y,m)\in
A=\\{(x,y,m)\in{\cal D}:\\}$. Furthermore, we know that since
$\hat{r}(x_{i})\leq 1$, then $\sum_{i}\hat{r}(x_{i})\leq\min\\{\lfloor
nb\rfloor,|A|\\}$. We argue that this inequality does not hold in a strict
form, i.e., we have $\sum_{i}\hat{r}(x_{i})=\min\\{\lfloor nb\rfloor,|A|\\}$.
The reason is that otherwise one can find $r^{\prime}(x)\in[0,1]^{{\cal X}}$
such that $\sum_{(x_{i},y_{i},m_{i})\in
A}\hat{f}(x_{i})+r^{\prime}(x_{i})=\min\\{nb,|A|\\}$ and because of negativity
of $\ell_{H}(x_{i},y_{i},m_{i})-\ell_{AI}(x_{i},y_{i})$, we can strictly
reduce the objective function that is a contradiction.

Next, we order $\ell_{H}(x_{i},y_{i},m_{i})-\ell_{AI}(x_{i},y_{i})$
increasingly and we name them $d_{j}$. In fact, we define $k_{j}$ such that
$d_{j}=\ell_{H}(x_{k_{j}},y_{k_{j}},m_{k_{j}})-\ell_{AI}(x_{k_{j}},y_{k_{j}})$
and that $d_{1}\leq d_{2}\ldots\leq d_{|A|}\leq 0$. For the sake of
simplicity, we further define $r_{j}:=r(x_{k_{j}})$. As a result, the
optimization problem in (91) can be rewritten as

$\displaystyle\min_{r_{i}\in[0,1],\,\sum_{i=1}^{n}r_{i}=\min\\{\lfloor
nb\rfloor,|A|\\}}\sum_{i=1}^{n}r_{i}d_{i}.$

Here, we show that the optimizer of the above problem is
$r_{i}=\mathds{1}_{i\leq\min\\{\lfloor nb\rfloor,|A|\\}}$. To show that, we
consider $r^{\prime}_{i}\in[0,1]$ such that
$\sum_{i=1}^{n}r^{\prime}_{i}=\min\\{\lfloor nb\rfloor,|A|\\}$. Then, we have

$\displaystyle\sum_{i=1}^{n}\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}d_{i}-\sum_{i=1}^{n}r^{\prime}_{i}d_{i}$
$\displaystyle=\sum_{i:\,\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}-r^{\prime}_{i}<0}(\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}-r^{\prime}_{i})\cdot d_{i}$
$\displaystyle~{}~{}~{}~{}+\sum_{i:\,\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}-r^{\prime}_{i}>0}(\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}-r^{\prime}_{i})\cdot d_{i}.$ (92)

Now, since we know that $\sum_{i}\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}=\sum_{i}r^{\prime}_{i}$, we can define a parameter $Q$ as

$\displaystyle Q:=\sum_{i:\,\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}-r^{\prime}_{i}>0}\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}-r^{\prime}_{i}=\sum_{i:\,\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}-r^{\prime}_{i}<0}r^{\prime}_{i}-\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}.$ (93)

Next, by defining $p_{i}:=\frac{\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}-r^{\prime}_{i}}{Q}$ for $i$s in which
$\mathds{1}_{i\leq\min\\{\lfloor nb\rfloor,|A|\\}}-r^{\prime}_{i}>0$ and
$q_{i}:=\frac{r^{\prime}_{i}\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}}{Q}$ for $i$s in which $\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}-r^{\prime}_{i}<0$ and $0$ otherwise, we conclude that
$\\{p_{i}\\}_{i}$ and $\\{q_{i}\\}_{i}$ are probability mass functions. Hence,
using (92) and (93), we have

$\displaystyle\sum_{i=1}^{n}\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}d_{i}-\sum_{i=1}^{n}r^{\prime}_{i}d_{i}=Q\big{(}\sum_{i=1}^{\min\\{\lfloor
nb\rfloor,|A|\\}}p_{i}d_{i}-\sum_{i=\min\\{\lfloor
nb\rfloor,|A|\\}+1}^{n}q_{i}d_{i}\big{)}.$

The above identity contains the difference of two expected value over random
variables that one is always smaller than the other. As a result, we show that

$\displaystyle\sum_{i=1}^{n}\mathds{1}_{i\leq\min\\{\lfloor
nb\rfloor,|A|\\}}d_{i}-\sum_{i=1}^{n}r^{\prime}_{i}d_{i}\leq 0,$

which completes the proof.