y_{j}=1;y_{j^{\prime}}=0\end{subarray}}\frac{2\prod_{i\neq\\{j,j^{\prime}\\}}\mathbb{P}(Y_{i}=y_{i}|\mathbf{\bm{x}})\mathbb{P}(Y_{j}=1|\mathbf{\bm{x}})\mathbb{P}(Y_{j^{\prime}}=0|\mathbf{\bm{x}})}{\tau+1+\|\mathbf{\bm{y}}_{jj^{\prime}}\|_{1}+\gamma}$
$\displaystyle\hskip 85.35826pt-\sum_{\begin{subarray}{c}\mathbf{\bm{y}}_{\sm
jj^{\prime}}\in\\{0,1\\}^{d-2}\\\
y_{j}=0;y_{j^{\prime}}=1\end{subarray}}\frac{2\prod_{i\neq\\{j,j^{\prime}\\}}\mathbb{P}(Y_{i}=y_{i}|\mathbf{\bm{x}})\mathbb{P}(Y_{j}=0|\mathbf{\bm{x}})\mathbb{P}(Y_{j^{\prime}}=1|\mathbf{\bm{x}})}{\tau+1+\|\mathbf{\bm{y}}_{jj^{\prime}}\|_{1}+\gamma}$
$\displaystyle=\big{(}\mathbb{P}(Y_{j}=1|\mathbf{\bm{x}})-\mathbb{P}(Y_{j^{\prime}}=1|\mathbf{\bm{x}})\big{)}\sum_{\begin{subarray}{c}\mathbf{\bm{y}}_{\sm
jj^{\prime}}\in\\{0,1\\}^{d-2}\end{subarray}}\frac{2\prod_{i\neq
j,j^{\prime}}\mathbb{P}(Y_{i}=y_{i}|\mathbf{\bm{x}})}{\tau+1+\|\mathbf{\bm{y}}_{\sm
jj^{\prime}}\|_{1}+\gamma},$ (26)

where $\mathbf{\bm{y}}_{\sm jj^{\prime}}$ is $\mathbf{\bm{y}}$ removing
$y_{j}$ and $y_{j^{\prime}}$, the second last inequality follows from the
conditional independence of $Y_{j}$ and $Y_{j^{\prime}}$ given
$\mathbf{\bm{X}}$ for any pair $j$ and $j^{\prime}$. According to (D.1), we
have

$D_{jj^{\prime}}(\tau)\geq
0\quad\iff\quad\mathbb{P}(Y_{j}=1|\mathbf{\bm{x}})-\mathbb{P}(Y_{j^{\prime}}=1|\mathbf{\bm{x}})\geq
0,$

thus sorting $s_{j}(\tau)$ is equivalent to sorting
$\mathbb{P}(Y_{j}=1|\mathbf{\bm{x}})$ for any given $\tau$. Let
$J_{\tau}=\big{\\{}j:\sum_{j^{\prime}=1}^{d}\mathbf{\bm{1}}\big{(}\mathbb{P}(Y_{j^{\prime}}=1|\mathbf{\bm{x}})\geq\mathbb{P}(Y_{j}=1|\mathbf{\bm{x}})\big{)}\leq\tau\big{\\}}$
be the index set of the $\tau$-largest conditional probabilities, it suffices
to solve

$\displaystyle\tau^{*}$ $\displaystyle=\mathop{\rm
argmax}_{\tau=0,\cdots,d}\sum_{j\in
J_{\tau}}\mathbb{E}\big{(}\frac{2Y_{j}}{\|\mathbf{\bm{Y}}\|_{1}+\tau+\gamma}\big{)}+\mathbb{E}\big{(}\frac{\gamma}{\|\mathbf{\bm{Y}}\|_{1}+\tau+\gamma}\big{)}$
$\displaystyle=\mathop{\rm argmax}_{\tau=0,\cdots,d}\sum_{j\in
J_{\tau}}\sum_{l=0}^{d-1}\frac{p_{j}(\mathbf{\bm{x}})}{\tau+l+\gamma+1}\mathbb{P}\big{(}\|\mathbf{\bm{Y}}_{\sm
j}\|_{1}=l|\mathbf{\bm{X}}=\mathbf{\bm{x}}\big{)}+\sum_{l=0}^{d}\frac{\gamma}{\tau+l+\gamma}\mathbb{P}\big{(}\|\mathbf{\bm{Y}}\|_{1}=l|\mathbf{\bm{X}}=\mathbf{\bm{x}}\big{)},$

where $\|\mathbf{\bm{Y}}_{\sm j}\|_{1}=\sum_{j^{\prime}\neq j}Y_{j^{\prime}}$
is a Poisson-binomial random variable with success probabilities
$\mathbf{\bm{p}}_{\sm j}(\mathbf{\bm{x}})$, since $Y_{j}$ ($j=1,\cdots,d$) is
an independent Bernoulli random variable given
$\mathbf{\bm{X}}=\mathbf{\bm{x}}$. The desirable result then follows.

###  D.2 Proof of Lemma 3

Proof  To proceed, we denote
$\xi_{l}(\mathbf{\bm{x}})=\mathbb{P}(\widehat{\Gamma}(\mathbf{\bm{x}})=l)$,
and $\xi_{jl}(\mathbf{\bm{x}})=\mathbb{P}(\widehat{\Gamma}_{\sm
j}(\mathbf{\bm{x}})=l)$, and $\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{\tau}=\mkern
1.5mu\overline{\mkern-1.5mu\omega\mkern-1.5mu}\mkern
1.5mu_{\tau}(\mathbf{\bm{x}})+\mkern
1.5mu\overline{\mkern-1.5mu\nu\mkern-1.5mu}\mkern
1.5mu_{\tau}(\mathbf{\bm{x}})$. For simplicity in presentation, we assume that
$\widehat{q}_{1}(\mathbf{\bm{x}})\geq\cdots\geq\widehat{q}_{d}(\mathbf{\bm{x}})$.
Then, for any $\tau^{\prime}>\tau$, since $\mkern
1.5mu\overline{\mkern-1.5mu\nu\mkern-1.5mu}\mkern 1.5mu_{\tau}\geq\mkern
1.5mu\overline{\mkern-1.5mu\nu\mkern-1.5mu}\mkern 1.5mu_{\tau^{\prime}}$, and

$\displaystyle\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\tau}(\mathbf{\bm{x}})-\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\tau^{\prime}}(\mathbf{\bm{x}})}{\tau^{\prime}-\tau}$
$\displaystyle\geq\sum_{j=1}^{\tau}\widehat{q}_{j}(\mathbf{\bm{x}})\sum_{l=0}^{d-1}\frac{\xi_{jl}(\mathbf{\bm{x}})}{(\tau+l+1+\gamma)(\tau^{\prime}+l+1+\gamma)}-\frac{1}{\tau^{\prime}-\tau}\sum_{j=\tau+1}^{\tau^{\prime}}\widehat{q}_{j}(\mathbf{\bm{x}})\sum_{l=0}^{d-1}\frac{\xi_{jl}(\mathbf{\bm{x}})}{\tau^{\prime}+l+\gamma+1}$
$\displaystyle\geq\sum_{j=1}^{\tau}\widehat{q}_{j}(\mathbf{\bm{x}})\sum_{l=0}^{d-1}\frac{\xi_{\tau
l}(\mathbf{\bm{x}})}{(\tau+l+\gamma+1)(\tau^{\prime}+l+\gamma+1)}-\widehat{q}_{\tau+1}(\mathbf{\bm{x}})\sum_{l=0}^{d-1}\frac{\xi_{\tau
l}(\mathbf{\bm{x}})}{\tau^{\prime}+l+\gamma+1}$
$\displaystyle\geq\widehat{q}_{\tau+1}(\mathbf{\bm{x}})\sum_{l=0}^{d-1}\frac{(\tau+\gamma+d)\xi_{\tau
l}(\mathbf{\bm{x}})}{(\tau+l+\gamma+1)(\tau^{\prime}+l+\gamma+1)}-\widehat{q}_{\tau+1}(\mathbf{\bm{x}})\sum_{l=0}^{d-1}\frac{\xi_{\tau
l}(\mathbf{\bm{x}})}{\tau^{\prime}+l+\gamma+1}\geq 0,$

where the first inequality follows from Lemma 17 with
$\zeta_{l}=(\tau+l+\gamma+1)(\tau^{\prime}+l+\gamma+1)$ and
$\zeta_{l}=\tau^{\prime}+l+\gamma+1$, and
$\widehat{q}_{1}(\mathbf{\bm{x}})\geq\cdots\geq\widehat{q}_{\tau}(\mathbf{\bm{x}})\geq\cdots\geq\widehat{q}_{\tau^{\prime}}(\mathbf{\bm{x}})$,
and the third inequality follows from the condition that
$\sum_{j=1}^{\tau}\widehat{q}_{j}(\mathbf{\bm{x}})/\widehat{q}_{\tau+1}(\mathbf{\bm{x}})\geq\tau+\gamma+d$.
The desirable result then follows. The upper bound provided by Lemma 3 is
illustrated in Figure 8 based on a random example of Example 1.

Figure 8: Dice score vs. $\tau$ based on a random example of Example 1. Note
that Lemma 3 indicates the optimal $\tau$ (red line) is always obtained before
the upper bound (green line). Thus, the searching region of $\tau$ can be
shrunk.

###  D.3 Proof of Lemma 4

Proof  Without loss of generality, assume
$\mathcal{L}(\epsilon)\subset\\{0,\cdots,d-1\\}$. Denote
$l_{L}=\lfloor\widehat{\sigma}(\mathbf{\bm{x}})\Psi^{-1}(\epsilon)+\widehat{\mu}(\mathbf{\bm{x}})\rfloor-1$
and
$l_{U}=\lceil-\widehat{\sigma}(\mathbf{\bm{x}})\Psi^{-1}(\epsilon)+\widehat{\mu}(\mathbf{\bm{x}})\rceil$,
$\xi_{l}=\mathbb{P}\big{(}\widehat{\Gamma}(\mathbf{\bm{x}})=l\big{)}$,
$\widetilde{\xi}_{l}=\widetilde{\mathbb{P}}\big{(}\widehat{\Gamma}(\mathbf{\bm{x}})=l\big{)}$,
$\xi_{\sm j,l}=\mathbb{P}\big{(}\widehat{\Gamma}_{\sm
j}(\mathbf{\bm{x}})=l\big{)}$, $\widetilde{\xi}_{\sm
j,l}=\widetilde{\mathbb{P}}\big{(}\widehat{\Gamma}_{\sm
j}(\mathbf{\bm{x}})=l\big{)}$, we treat
$\big{|}\widetilde{\omega}_{\tau}-\mkern
1.5mu\overline{\mkern-1.5mu\omega\mkern-1.5mu}\mkern 1.5mu_{\tau}\big{|}$ and
$\big{|}\widetilde{\nu}_{\tau}-\mkern
1.5mu\overline{\mkern-1.5mu\nu\mkern-1.5mu}\mkern 1.5mu_{\tau}\big{|}$
separately. First,

$\displaystyle\big{|}\widetilde{\omega}_{\tau}-\mkern
1.5mu\overline{\mkern-1.5mu\omega\mkern-1.5mu}\mkern 1.5mu_{\tau}\big{|}$
$\displaystyle\leq\sum_{l>l_{U}}\frac{2}{\tau+l+\gamma+1}\omega_{\tau,l}+\sum_{0\leq
l<l_{L}}\frac{2}{\tau+l+\gamma+1}\omega_{\tau,l}+\sum_{l_{L}\leq
l<l_{U}}\frac{2}{\tau+l+\gamma+1}\Big{|}\omega_{\tau,l}-\widetilde{\omega}_{\tau,l}\Big{|}$
$\displaystyle=:S_{1}+S_{2}+S_{3}.$

Next, we turn to bound $S_{1}$ \- $S_{3}$ separately.

$\displaystyle S_{1}$
$\displaystyle=\sum_{l>l_{U}}\frac{2}{\tau+l+\gamma+1}\sum_{s=1}^{\tau}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})\mathbb{P}\big{(}\widehat{\Gamma}_{\sm
j_{s}}(\mathbf{\bm{x}})=l\big{)}\leq\frac{2}{\tau+l_{U}+\gamma+1}\sum_{s=1}^{\tau}\sum_{l>l_{U}}\mathbb{P}\big{(}\widehat{\Gamma}_{\sm
j_{s}}(\mathbf{\bm{x}})=l\big{)}$
$\displaystyle\leq\frac{2}{\tau+l_{U}+\gamma+1}\sum_{s=1}^{\tau}\big{(}1-\mathbb{P}\big{(}\widehat{\Gamma}_{\sm
j_{s}}(\mathbf{\bm{x}})\leq
l_{U}\big{)}\big{)}\leq\frac{2\tau}{\tau+l_{U}+\gamma+1}\mathbb{P}\big{(}\widehat{\Gamma}(\mathbf{\bm{x}})>l_{U}\big{)},$

where the last inequality follows from Lemma 16. For $S_{2}$, we have

$\displaystyle S_{2}$
$\displaystyle\leq\frac{2}{\tau+\gamma+1}\sum_{s=1}^{\tau}\sum_{0\leq
l<l_{L}}\mathbb{P}\big{(}\widehat{\Gamma}_{\sm
j_{s}}(\mathbf{\bm{x}})=l\big{)}\leq\frac{2\tau}{\tau+\gamma+1}\mathbb{P}\big{(}\widehat{\Gamma}(\mathbf{\bm{x}})\leq
l_{L}+1\big{)},$

where the last inequality follows from Lemma 16. Next, according to Theorem
1.1 in Neammanee (2005),

$\mathbb{P}\big{(}\widehat{\Gamma}(\mathbf{\bm{x}})\leq
l_{L}+1\big{)}\leq\mathbb{P}\big{(}Z\leq\Psi^{-1}(\epsilon)\big{)}+\frac{C_{0}}{\widehat{\sigma}^{2}(\mathbf{\bm{x}})}=\epsilon+\frac{C_{0}}{\widehat{\sigma}^{2}(\mathbf{\bm{x}})},$

and

$\mathbb{P}\big{(}\widehat{\Gamma}(\mathbf{\bm{x}})>l_{U}\big{)}\leq\mathbb{P}\big{(}Z\geq\Psi^{-1}(1-\epsilon)\big{)}+\frac{C_{0}}{\widehat{\sigma}^{2}(\mathbf{\bm{x}})}=\epsilon+\frac{C_{0}}{\widehat{\sigma}^{2}(\mathbf{\bm{x}})},$

where $Z$ is a random variable following the refined normal distribution. For
$S_{3}$,

$\displaystyle S_{3}$
$\displaystyle\leq\sum_{l=0}^{d-1}\frac{2}{\tau+l+\gamma+1}\sum_{s=1}^{\tau}\widehat{\mathbf{\bm{q}}}_{j_{s}}(\mathbf{\bm{x}})|\widetilde{\xi}_{\sm
j,l}-\xi_{\sm
j,l}|\leq\sum_{s=1}^{\tau}\widehat{\mathbf{\bm{q}}}_{j_{s}}(\mathbf{\bm{x}})\sum_{l=0}^{d-1}\frac{2}{\tau+l+\gamma+1}\max_{j=1,\cdots,\tau}|\widetilde{\xi}_{\sm
j,l}-\xi_{\sm j,l}|$
$\displaystyle\leq\min(\widehat{\mu}(\mathbf{\bm{x}}),\tau)\sum_{l=0}^{d-1}\frac{2}{\tau+l+\gamma+1}\max_{s=1,\cdots,\tau}\frac{C_{0}}{\widehat{\sigma}^{2}(\mathbf{\bm{x}})-\widehat{q}_{j_{s}}(\mathbf{\bm{x}})\big{(}1-\widehat{q}_{j_{s}}(\mathbf{\bm{x}})\big{)}}$
$\displaystyle\leq\frac{2C_{0}\min(\widehat{\mu}(\mathbf{\bm{x}}),\tau)}{\widehat{\sigma}^{2}(\mathbf{\bm{x}})-1/4}\sum_{l=1}^{d}\frac{1}{\tau+l+\gamma}=\frac{2C_{0}\min(\widehat{\mu}(\mathbf{\bm{x}}),\tau)}{\widehat{\sigma}^{2}(\mathbf{\bm{x}})-1/4}\big{(}H_{\tau+d+\gamma}-H_{\tau+\gamma}\big{)}$
$\displaystyle\leq\frac{2C_{0}\min(\widehat{\mu}(\mathbf{\bm{x}}),\tau)}{\widehat{\sigma}^{2}(\mathbf{\bm{x}})-1/4}\Big{(}\log\big{(}1+\frac{d}{\tau+\gamma}\big{)}+1-\frac{1}{\tau+\gamma}\Big{)},$

where $H_{K}=\sum_{k=1}^{K}1/k$ is the harmonic number, and the last
inequality follows from the fact that $\log(K)+1/K\leq H_{K}\leq\log(K)+1$.
Taken together,

$\big{|}\widetilde{\omega}_{\tau}-\mkern
1.5mu\overline{\mkern-1.5mu\omega\mkern-1.5mu}\mkern
1.5mu_{\tau}\big{|}\leq\frac{4\tau}{\tau+\gamma+1}\big{(}\epsilon+\frac{C_{0}}{\widehat{\sigma}^{2}(\mathbf{\bm{x}})}\big{)}+\frac{2C_{0}\min(\widehat{\mu}(\mathbf{\bm{x}}),\tau)}{\widehat{\sigma}^{2}(\mathbf{\bm{x}})-1/4}\Big{(}\log\big{(}1+\frac{d}{\tau+\gamma}\big{)}+\frac{\tau+\gamma-1}{\tau+\gamma}\Big{)}.$

Similarly, for $|\widetilde{\nu}_{\tau}-\mkern
1.5mu\overline{\mkern-1.5mu\nu\mkern-1.5mu}\mkern 1.5mu_{\tau}|$,

$\displaystyle|\widetilde{\nu}_{\tau}-\mkern
1.5mu\overline{\mkern-1.5mu\nu\mkern-1.5mu}\mkern
1.5mu_{\tau}|\leq\frac{2\gamma}{\tau+\gamma}\epsilon+\frac{\gamma
C_{0}}{\widehat{\sigma}^{2}(\mathbf{\bm{x}})}\Big{(}\log\big{(}1+\frac{d}{\tau+\gamma-1}\big{)}+1-\frac{1}{\tau+\gamma-1}\Big{)}.$

This completes the proof.

###  D.4 Proof of Lemma 5

Proof  With the same argument in the proof of Lemma 4, it suffices to consider

$\displaystyle\big{|}\widetilde{\mathbb{P}}(\widehat{\Gamma}(\mathbf{\bm{x}})=l)-\widetilde{\mathbb{P}}(\widehat{\Gamma}_{\sm
j}(\mathbf{\bm{x}})=l)\big{|}\leq\sum_{l^{\prime}=l-1}^{l}\big{|}\widetilde{\mathbb{P}}(\widehat{\Gamma}(\mathbf{\bm{x}})\leq
l^{\prime})-\widetilde{\mathbb{P}}(\widehat{\Gamma}_{\sm
j}(\mathbf{\bm{x}})\leq l^{\prime})\big{|}.$

Denote
$I=\widehat{\sigma}(\mathbf{\bm{x}})^{-1}(l+1/2-\widehat{\mu}(\mathbf{\bm{x}}))$
and $I_{\sm j}=\widehat{\sigma}_{\sm
j}(\mathbf{\bm{x}})^{-1}(l+1/2-\widehat{\mu}_{\sm j}(\mathbf{\bm{x}}))$, we
have

$\displaystyle\big{|}\widetilde{\mathbb{P}}(\widehat{\Gamma}(\mathbf{\bm{x}})\leq
l)$ $\displaystyle-\widetilde{\mathbb{P}}(\widehat{\Gamma}_{\sm
j}(\mathbf{\bm{x}})\leq l)\big{|}=\big{|}\Psi(I)-\Psi_{\sm j}(I_{\sm
j})\big{|}$ $\displaystyle\leq\big{|}\Phi(I)-\Phi(I_{\sm
j})\big{|}+\frac{1}{6}\big{|}\widehat{\eta}(\mathbf{\bm{x}})(1-I^{2})\phi(I)-\widehat{\eta}_{\sm
j}(\mathbf{\bm{x}})(1-I_{\sm j}^{2})\phi(I_{\sm
j})\big{|}=:T_{1}+\frac{1}{6}T_{2}.$

Next, we turn to treat $T_{1}$ and $T_{2}$ separately. Without loss
generalization, we assume $|I_{\sm j}|\geq|I|$, then

$\displaystyle T_{1}$ $\displaystyle\leq\big{|}\int_{I}^{I_{\sm
j}}\phi(\mathbf{\bm{x}})d\mathbf{\bm{x}}\big{|}\leq|I_{\sm j}-I|\phi(I)$
$\displaystyle=\Big{(}|\widehat{\sigma}^{-1}(\mathbf{\bm{x}})-\widehat{\sigma}_{\sm
j}^{-1}(\mathbf{\bm{x}})|\big{|}l+1/2-\widehat{\mu}(\mathbf{\bm{x}})\big{|}+\widehat{\sigma}_{\sm
j}^{-1}(\mathbf{\bm{x}})\big{|}\widehat{\mu}(\mathbf{\bm{x}})-\widehat{\mu}_{\sm
j}(\mathbf{\bm{x}})\big{|}\Big{)}\phi(I)$
$\displaystyle=\widehat{\sigma}^{-1}_{\sm
j}(\mathbf{\bm{x}})(\widehat{\sigma}(\mathbf{\bm{x}})-\widehat{\sigma}_{\sm
j}(\mathbf{\bm{x}}))|I|\phi(I)+\widehat{\sigma}_{\sm
j}^{-1}(\mathbf{\bm{x}})\widehat{q}_{j}(\mathbf{\bm{x}})\phi(I)$
$\displaystyle\leq\frac{\widehat{q}_{j}(\mathbf{\bm{x}})(1-\widehat{q}_{j}(\mathbf{\bm{x}}))}{\widehat{\sigma}_{\sm
j}(\mathbf{\bm{x}})\big{(}\widehat{\sigma}_{\sm
j}(\mathbf{\bm{x}})+\widehat{\sigma}(\mathbf{\bm{x}})\big{)}}|I|\phi(I)+\frac{1}{\sqrt{2\pi}\widehat{\sigma}_{\sm
j}(\mathbf{\bm{x}})}\leq\frac{1}{4\sqrt{2\pi}}\Big{(}\frac{1}{2\sqrt{e}(\widehat{\sigma}^{2}(\mathbf{\bm{x}})-1/4)}+\frac{4}{\sqrt{\widehat{\sigma}^{2}(\mathbf{\bm{x}})-1/4}}\Big{)},$

where the last inequality follows the fact that $|u|\phi(u)\leq
1/\sqrt{2e\pi}$ and $0\leq\phi(u)\leq 1/\sqrt{2\pi}$. For $T_{2}$, let
$g(u)=(1-u^{2})\phi(u)$, we have

$\displaystyle T_{2}$
$\displaystyle\leq\big{|}\widehat{\eta}(\mathbf{\bm{x}})(1-I^{2})\phi(I)\big{|}+\big{|}\widehat{\eta}_{\sm
j}(\mathbf{\bm{x}})(1-I_{\sm j}^{2})\phi(I_{\sm
j})\big{|}\leq\frac{1}{\sqrt{2\pi}}\frac{\widehat{m}_{3}(\mathbf{\bm{x}})}{(\widehat{\sigma}^{2}(\mathbf{\bm{x}})-1/4)^{3/2}},$

where the last inequality follows from the fact that $|g(u)|\leq
1/\sqrt{2\pi}$, and
$\widehat{m}_{3}(\mathbf{\bm{x}})=\sum_{j=1}^{d}\widehat{p}_{j}(\mathbf{\bm{x}})(1-\widehat{p}_{j}(\mathbf{\bm{x}}))(1-2\widehat{p}_{j}(\mathbf{\bm{x}}))$.
Taken together, using the same argument in the proof of Lemma 4, we have

$\displaystyle\big{|}\widetilde{\omega}^{b}_{\tau}-\widetilde{\omega}_{\tau}\big{|}\leq\frac{1}{4\sqrt{2\pi}}\Big{(}\frac{1/(2\sqrt{e})}{\widehat{\sigma}^{2}(\mathbf{\bm{x}})-1/4}+\frac{4}{\sqrt{\widehat{\sigma}^{2}(\mathbf{\bm{x}})-1/4}}+\frac{4\widehat{m}_{3}(\mathbf{\bm{x}})}{(\widehat{\sigma}^{2}(\mathbf{\bm{x}})-1/4)^{3/2}}\Big{)}\big{(}\log\big{(}1+\frac{d}{\tau+\gamma}\big{)}+1\big{)}.$

Combining Lemma 4, the desirable result then follows.

###  D.5 Proof of Lemma 6

Proof  Denote $\mathcal{K}_{+}=\\{1\leq k\leq K:\alpha_{k}>0\\}$. We first
prove the necessity. Suppose $\boldsymbol{\Delta}^{*}_{k}$ is a global
minimizer of ${{\rm Dice}}_{k}(\cdot)$, for $k\in\mathcal{K}_{+}$. Then for
any
$\boldsymbol{\Delta}=(\boldsymbol{\Delta}_{1},\cdots,\boldsymbol{\Delta}_{K})$,
we have

${\rm
mDice}_{\gamma}(\boldsymbol{\Delta}^{*})=\sum_{k\in\mathcal{K}_{+}}\alpha_{k}{{\rm
Dice}}_{\gamma,k}(\boldsymbol{\Delta}^{*}_{k})\leq\sum_{k\in\mathcal{K}_{+}}\alpha_{k}{{\rm
Dice}}_{\gamma,k}(\boldsymbol{\Delta}_{k}),$

yields that $\boldsymbol{\Delta}^{*}$ is a global minimizer of ${\rm
mDice}_{\gamma}(\cdot)$. We next prove the sufficiency by contradiction.
Suppose $\boldsymbol{\Delta}^{*}$ is a global minimizer of ${\rm
mDice}_{\gamma}(\cdot)$, yet there exists $k_{0}\in\mathcal{K}_{+}$ such that
$\boldsymbol{\Delta}_{k_{0}}^{*}$ is not a minimizer of ${{\rm
Dice}}_{\gamma,k_{0}}(\cdot)$. Thus, there exists a segmentation rule
$\widetilde{\boldsymbol{\Delta}}$ such that ${{\rm
Dice}}_{\gamma,k_{0}}(\widetilde{\boldsymbol{\Delta}})<{{\rm
Dice}}_{\gamma,k_{0}}(\boldsymbol{\Delta}_{k_{0}}^{*})$, then let
$\widetilde{\boldsymbol{\Delta}}=(\boldsymbol{\Delta}^{*}_{1},\cdots,\boldsymbol{\Delta}^{*}_{k_{0}-1},\widetilde{\boldsymbol{\Delta}}_{k_{0}},\boldsymbol{\Delta}^{*}_{k_{0}+1},\cdots,\boldsymbol{\Delta}^{*}_{K})$

${\rm
mDice}_{\gamma}(\boldsymbol{\Delta}^{*})=\sum_{k\in\mathcal{K}_{+}}\alpha_{k}{{\rm
Dice}}_{\gamma,k}(\boldsymbol{\Delta}^{*}_{k})>\sum_{k\in\mathcal{K}_{+}}\alpha_{k}{{\rm
Dice}}_{\gamma,k}(\widetilde{\boldsymbol{\Delta}})={\rm
mDice}_{\gamma}(\widetilde{\boldsymbol{\Delta}}),$

which leads to contradiction of that $\boldsymbol{\Delta}^{*}$ is a global
minimizer of ${\rm mDice}_{\gamma}(\cdot)$. The desirable result then follows.

###  D.6 Proof of Lemma 7

Proof  Given a segmentation rule
$\boldsymbol{\Delta}(\mathbf{\bm{X}})=(\boldsymbol{\Delta}_{1}(\mathbf{\bm{X}}),\cdots,\boldsymbol{\Delta}_{K}(\mathbf{\bm{X}}))$,
${\rm mDice}_{\gamma}(\cdot)$ can be rewritten as

${\rm mDice}_{\gamma}(\boldsymbol{\Delta})=\sum_{k=1}^{K}\alpha_{k}{{\rm
Dice}}_{\gamma,k}(\boldsymbol{\Delta}_{k}(\mathbf{\bm{X}})).$

It is equivalent to consider the point-wise minimization on
$\mathbf{\bm{X}}=\mathbf{\bm{x}}$:

$\boldsymbol{\Delta}^{*}(\mathbf{\bm{x}})=\mathop{\rm
argmax}_{\mathbf{\bm{V}}\in\\{0,1\\}^{d\times K}}\ {\rm
mDice}_{\gamma}(\mathbf{\bm{V}}|\mathbf{\bm{x}}),\quad\text{s.t.}\sum_{k=1}^{K}\mathbf{\bm{V}}_{k}=\mathbf{\bm{1}}_{d},\quad{\rm
mDice}_{\gamma}(\mathbf{\bm{V}}|\mathbf{\bm{x}})=\sum_{k=1}^{K}\alpha_{k}{{\rm
Dice}}_{\gamma,k}(\mathbf{\bm{V}}_{k}|\mathbf{\bm{x}}),$

where $\mathbf{\bm{V}}_{k}$ is the $k$-th column of $\mathbf{\bm{V}}$.
According to (D.1), we have

$\displaystyle{\rm mDice}_{\gamma}(\mathbf{\bm{V}}|\mathbf{\bm{x}})$
$\displaystyle=\sum_{k=1}^{K}\alpha_{k}\sum_{j\in
I({\mathbf{\bm{V}}_{k}})}\sum_{\begin{subarray}{c}\mathbf{\bm{y}}_{\sm
j,k}\in\\{0,1\\}^{d-1}\\\
y_{j,k}=1\end{subarray}}\frac{2\mathbb{P}(\mathbf{\bm{Y}}_{k}=\mathbf{\bm{y}}_{k}|\mathbf{\bm{x}})}{\tau_{k}+\|\mathbf{\bm{y}}_{k}\|_{1}+\gamma}+\sum_{k=1}^{K}\alpha_{k}\mathbb{E}\Big{(}\frac{\gamma}{\|\mathbf{\bm{Y}}_{\cdot
k}\|_{1}+\tau_{k}+\gamma}\Big{)}$
$\displaystyle=\sum_{k=1}^{K}\sum_{j=1}^{d}R_{jk}(\tau_{k})v_{jk}+\sum_{k=1}^{K}\alpha_{k}\mkern
1.5mu\overline{\mkern-1.5mu\nu\mkern-1.5mu}\mkern 1.5mu(\tau_{k}),$

where $v_{jk}\in\\{0,1\\}$ is the segmentation indicator of the $j$-th feature
under the class-$k$, and $R_{jk}(\cdot)$ is a reward function defined as:

$R_{jk}(\tau_{k})=\alpha_{k}\sum_{\begin{subarray}{c}\mathbf{\bm{y}}_{\sm
j,k}\in\\{0,1\\}^{d-1}\\\
y_{j,k}=1\end{subarray}}\frac{2\mathbb{P}(\mathbf{\bm{Y}}_{k}=\mathbf{\bm{y}}_{k}|\mathbf{\bm{x}})}{\tau_{k}+\|\mathbf{\bm{y}}_{k}\|_{1}}.$

Now, suppose the optimal volume function
$\boldsymbol{\tau}^{*}(\mathbf{\bm{x}})=(\tau_{1}^{*}(\mathbf{\bm{x}}),\cdots,\tau_{K}^{*}(\mathbf{\bm{x}}))^{\intercal}$
is given, then $\mkern 1.5mu\overline{\mkern-1.5mu\nu\mkern-1.5mu}\mkern
1.5mu(\tau^{*}_{k})$ becomes a constant, and the point-wise maximization on
${\rm mDice}_{\gamma}$ is equivalent to:

$\displaystyle\max_{\mathbf{\bm{V}}\in\\{0,1\\}^{d\times K}}$
$\displaystyle\quad\sum_{k=1}^{K}\sum_{j=1}^{d}R^{*}_{jk}v_{jk},$ subject to
$\displaystyle\quad\sum_{j=1}^{d}v_{jk}=\tau^{*}_{k}(\mathbf{\bm{x}}),\quad\sum_{k=1}^{K}v_{jk}=1,\quad\text{for
}k=1,\cdots,K;\quad\text{for }j=1,\cdots,d,$ (28)

where $R^{*}_{jk}=R_{jk}(\tau^{*}_{k}(\mathbf{\bm{x}}))$ is the reward under
$\tau_{k}^{*}(\mathbf{\bm{x}})$. Note that (D.6) is the formulation for the
assignment problem (Kuhn, 1955). This completes the proof.

###  D.7 Proof of Lemma 9

Proof  For simplicity, we construct a counter example based on $\gamma=0$ and
$d=2$, that is, $\mathbf{\bm{Y}}=(Y_{1},Y_{2})^{\intercal}$ and
$\mathbf{\bm{p}}(\mathbf{\bm{x}})=(p_{1}(\mathbf{\bm{x}}),p_{2}(\mathbf{\bm{x}}))^{\intercal}$.
Without loss generality, we assume
$p_{1}(\mathbf{\bm{x}})>p_{2}(\mathbf{\bm{x}})$.

First, we derive the Bayes rule in Theorem 1 for this case. Note that it
suffices to compare the scores for $\tau=1$
($\mathbf{\bm{v}}=(1,0)^{\intercal}$) and $\tau=2$
$(\mathbf{\bm{v}}=(1,1)^{\intercal})$.

$\displaystyle{\rm
Dice}((1,0)^{\intercal}|\mathbf{\bm{x}})=p_{1}(\mathbf{\bm{x}})+\frac{1}{3}p_{1}(\mathbf{\bm{x}})p_{2}(\mathbf{\bm{x}}),\quad{\rm
Dice}((1,1)^{\intercal}|\mathbf{\bm{x}})=\frac{2}{3}(p_{1}(\mathbf{\bm{x}})+p_{2}(\mathbf{\bm{x}}))-\frac{1}{3}p_{1}(\mathbf{\bm{x}})p_{2}(\mathbf{\bm{x}}).$

Therefore, the Bayes rule for Dice optimal segmentation is:

$\boldsymbol{\delta}^{*}(\mathbf{\bm{x}})=(1,0)^{\intercal},\text{ if
}\frac{1}{2}p_{1}(\mathbf{\bm{x}})-p_{2}(\mathbf{\bm{x}})+p_{1}(\mathbf{\bm{x}})p_{2}(\mathbf{\bm{x}})\geq
0,\quad\boldsymbol{\delta}^{*}(\mathbf{\bm{x}})=(1,1)^{\intercal},\text{
otherwise}.$

Now, we check the Dice-calibrated (Fisher consistency) for classification-
calibrated losses (CCL). Let $p_{1}(\mathbf{\bm{x}})=0.45$ and
$p_{2}(\mathbf{\bm{x}})=0.44$, then
$\widetilde{\boldsymbol{\delta}}(\mathbf{\bm{x}})=\mathbf{\bm{1}}(\mathbf{\bm{p}}(\mathbf{\bm{x}})\geq
0.5)=(0,0)^{\intercal}\neq(1,1)^{\intercal}=\boldsymbol{\delta}^{*}(\mathbf{\bm{x}})$,
where the first equality follows from the definition of a classification-
calibrated loss. Therefore, ${\rm Dice}(\widetilde{\boldsymbol{\delta}})<{\rm
Dice}(\boldsymbol{\delta}^{*})$ yields that a classification-calibrated loss
with thresholding at 0.5 is not Dice-calibrated.

Next, we check the Dice calibration for soft-Dice loss. Again, it suffices to
consider the point-wise minimization given $\mathbf{\bm{X}}=\mathbf{\bm{x}}$,
and its gradients with respect to $c_{j}=q_{j}(\mathbf{\bm{x}})\in[0,1]$ for
$j=1,2$:

$\displaystyle\frac{\partial\mathbb{E}\big{(}l_{\text{SoftD}}(\mathbf{\bm{Y}},\mathbf{\bm{c}})\mid\mathbf{\bm{X}}=\mathbf{\bm{x}}\big{)}}{\partial
c_{1}}$
$\displaystyle=-2\mathbb{E}\Big{(}\frac{Y_{1}(Y_{1}+Y_{2}+c_{1}+c_{2})-(Y_{1}c_{1}+Y_{2}c_{2})}{(Y_{1}+Y_{2}+c_{1}+c_{2})^{2}}\mid\mathbf{\bm{X}}=\mathbf{\bm{x}}\Big{)}$
$\displaystyle=-2\Big{(}\frac{2p_{1}(\mathbf{\bm{x}})p_{1}(\mathbf{\bm{x}})}{(2+c_{1}+c_{2})^{2}}+\frac{p_{1}(\mathbf{\bm{x}})(1-p_{2}(\mathbf{\bm{x}}))+(p_{1}(\mathbf{\bm{x}})-p_{2}(\mathbf{\bm{x}}))c_{2}}{(1+c_{1}+c_{2})^{2}}\Big{)},$
$\displaystyle\frac{\partial\mathbb{E}\big{(}l_{\text{SoftD}}(\mathbf{\bm{Y}},\mathbf{\bm{c}})\mid\mathbf{\bm{X}}=\mathbf{\bm{x}}\big{)}}{\partial
c_{2}}$
$\displaystyle=-2\Big{(}\frac{2p_{1}(\mathbf{\bm{x}})p_{1}(\mathbf{\bm{x}})}{(2+c_{1}+c_{2})^{2}}+\frac{p_{2}(\mathbf{\bm{x}})(1-p_{1}(\mathbf{\bm{x}}))+(p_{2}(\mathbf{\bm{x}})-p_{1}(\mathbf{\bm{x}}))c_{1}}{(1+c_{1}+c_{2})^{2}}\Big{)}.$

Accordingly,
${\partial\mathbb{E}\big{(}l_{\text{SoftD}}(\mathbf{\bm{Y}},\mathbf{\bm{c}})\mid\mathbf{\bm{X}}=\mathbf{\bm{x}}\big{)}}/{\partial
c_{1}}\leq 0$ for any $c_{2}\in[0,1]$, and
${\partial\mathbb{E}\big{(}l_{\text{SoftD}}(\mathbf{\bm{Y}},\mathbf{\bm{c}})\mid\mathbf{\bm{X}}=\mathbf{\bm{x}}\big{)}}/{\partial
c_{2}}\leq 0$ when
$2p_{2}(\mathbf{\bm{x}})-p_{1}(\mathbf{\bm{x}})-p_{1}(\mathbf{\bm{x}})p_{2}(\mathbf{\bm{x}})\geq
0$. For example, let $p_{1}(\mathbf{\bm{x}})=0.45$ and
$p_{2}(\mathbf{\bm{x}})=0.4$, then
$\widetilde{\boldsymbol{\delta}}(\mathbf{\bm{x}})=(1,1)^{\intercal}\neq(1,0)^{\intercal}=\boldsymbol{\delta}^{*}(\mathbf{\bm{x}})$.
Therefore, ${\rm Dice}(\widetilde{\boldsymbol{\delta}})<{\rm
Dice}(\boldsymbol{\delta}^{*})$ yields that the soft-Dice loss with
thresholding at 0.5 is not Dice-calibrated. This completes the proof.

###  D.8 Proof of Lemma 10

Proof  By the definition of a strictly proper loss and the formulation in
(24), we have
$\widehat{\mathbf{\bm{q}}}(\mathbf{\bm{x}})=\mathbf{\bm{p}}(\mathbf{\bm{x}})=\big{(}\mathbb{P}(Y_{1}=1|\mathbf{\bm{X}}=\mathbf{\bm{x}}),\cdots,\mathbb{P}(Y_{d}=1|\mathbf{\bm{X}}=\mathbf{\bm{x}})\big{)}^{\intercal}$.
Then the estimation of $\widehat{\tau}(\mathbf{\bm{x}})$ and
$\widehat{\boldsymbol{\delta}}(\mathbf{\bm{x}})$ agrees with the definition of
$\tau^{*}(\mathbf{\bm{x}})$ and $\boldsymbol{\delta}^{*}(\mathbf{\bm{x}})$.
This completes the proof.

###  D.9 Proof of Theorem 11

Proof  First, we consider point-wise approximation of the Dice metric under
probabilities $\mathbf{\bm{p}}$ and $\widehat{\mathbf{\bm{q}}}$. For any
$\boldsymbol{\delta}$, such that $\delta_{j}(\mathbf{\bm{x}})=1$ for
$j=j_{1},\cdots,j_{\tau}$, and $\delta_{j}(\mathbf{\bm{x}})=0$ otherwise.
Define

$\displaystyle\widehat{{\rm
Dice}}_{\gamma}({\boldsymbol{\delta}}(\mathbf{\bm{x}})|\mathbf{\bm{X}}=\mathbf{\bm{x}})$
$\displaystyle:=\sum_{s=1}^{\tau}\sum_{l=0}^{d-1}\frac{2\widehat{q}_{j_{s}}(\mathbf{\bm{x}})\mathbb{P}\big{(}\widehat{\Gamma}_{\sm
j}(\mathbf{\bm{x}})=l\big{)}}{\tau+l+\gamma+1}+\sum_{l=0}^{d}\frac{\gamma\mathbb{P}\big{(}\widehat{\Gamma}(\mathbf{\bm{X}})=l\big{)}}{\tau+l+\gamma}$
$\displaystyle=\sum_{s=1}^{\tau}2\widehat{q}_{j_{s}}(\mathbf{\bm{x}})\mathbb{E}\big{(}\frac{1}{\tau+\gamma+1+\widehat{\Gamma}_{\sm
j_{s}}(\mathbf{\bm{x}})}\big{)}+\gamma\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\widehat{\Gamma}(\mathbf{\bm{x}})}\big{)}$
$\displaystyle{\rm
Dice}_{\gamma}({\boldsymbol{\delta}}(\mathbf{\bm{x}})|\mathbf{\bm{X}}=\mathbf{\bm{x}})$
$\displaystyle:=\sum_{s=1}^{\tau}\sum_{l=0}^{d-1}\frac{2p_{j_{s}}(\mathbf{\bm{x}})\mathbb{P}\big{(}\Gamma_{\sm
j}(\mathbf{\bm{x}})=l\big{)}}{\tau+l+\gamma+1}+\sum_{l=0}^{d}\frac{\gamma\mathbb{P}\big{(}{\Gamma}(\mathbf{\bm{X}})=l\big{)}}{\tau+l+\gamma}$
$\displaystyle=\sum_{s=1}^{\tau}2p_{j_{s}}(\mathbf{\bm{x}})\mathbb{E}\big{(}\frac{1}{\tau+\gamma+1+\Gamma_{\sm
j_{s}}(\mathbf{\bm{x}})}\big{)}+\gamma\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\Gamma(\mathbf{\bm{x}})}\big{)}.$

Now, we have

$\displaystyle\big{|}\widehat{{\rm
Dice}}_{\gamma}({\boldsymbol{\delta}}(\mathbf{\bm{x}})|\mathbf{\bm{X}}=\mathbf{\bm{x}})-{\rm
Dice}_{\gamma}({\boldsymbol{\delta}}(\mathbf{\bm{x}})|\mathbf{\bm{X}}=\mathbf{\bm{x}})\big{|}$
$\displaystyle\leq\Big{|}2\sum_{s=1}^{\tau}\Big{(}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})\mathbb{E}\big{(}\frac{1}{\tau+\gamma+1+\widehat{\Gamma}_{\sm
j_{s}}(\mathbf{\bm{x}})}\big{)}-p_{j_{s}}(\mathbf{\bm{x}})\mathbb{E}\big{(}\frac{1}{\tau+\gamma+1+\Gamma_{\sm
j_{s}}(\mathbf{\bm{x}})}\big{)}\Big{)}\Big{|}$
$\displaystyle\qquad+\gamma\Big{|}\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\widehat{\Gamma}(\mathbf{\bm{x}})}\big{)}-\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\Gamma(\mathbf{\bm{x}})}\big{)}\Big{|}$
$\displaystyle\leq\Big{|}2\sum_{s=1}^{\tau}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})\Big{(}\mathbb{E}\big{(}\frac{1}{\tau+\gamma+1+\widehat{\Gamma}_{\sm
j_{s}}(\mathbf{\bm{x}})}\big{)}-\mathbb{E}\big{(}\frac{1}{\tau+\gamma+1+\Gamma_{\sm
j_{s}}(\mathbf{\bm{x}})}\big{)}\Big{)}\Big{|}$
$\displaystyle\quad+\Big{|}2\sum_{s=1}^{\tau}\big{(}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})-p_{j_{s}}(\mathbf{\bm{x}})\big{)}\mathbb{E}\big{(}\frac{1}{\tau+\gamma+1+\Gamma_{\sm
j_{s}}(\mathbf{\bm{x}})}\big{)}\Big{)}\Big{|}+\gamma\Big{|}\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\widehat{\Gamma}(\mathbf{\bm{x}})}\big{)}-\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\Gamma(\mathbf{\bm{x}})}\big{)}\Big{|}$
$\displaystyle\leq 2\sum_{s=1}^{\tau}\Big{|}\frac{\mathbb{E}\big{(}\Gamma_{\sm
j_{s}}(\mathbf{\bm{x}})-\widehat{\Gamma}_{\sm
j_{s}}(\mathbf{\bm{x}})\big{)}}{(\tau+\gamma+1)^{2}}\Big{|}+2\sum_{s=1}^{\tau}\frac{\big{|}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})-p_{j_{s}}(\mathbf{\bm{x}})\big{|}}{\tau+\gamma+1}+\gamma\Big{|}\frac{\mathbb{E}\big{(}\Gamma(\mathbf{\bm{x}})-\widehat{\Gamma}(\mathbf{\bm{x}})\big{)}}{(\tau+\gamma)^{2}}\Big{|}$
$\displaystyle\leq
2\sum_{s=1}^{\tau}\frac{|\|\widehat{\mathbf{\bm{q}}}(\mathbf{\bm{x}})\|_{1}-\|\mathbf{\bm{p}}(\mathbf{\bm{x}})\|_{1}|+|\widehat{q}_{j_{s}}(\mathbf{\bm{x}})-p_{j_{s}}(\mathbf{\bm{x}})|}{(\tau+\gamma+1)^{2}}+2\sum_{s=1}^{\tau}\frac{\big{|}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})-p_{j_{s}}(\mathbf{\bm{x}})\big{|}}{\tau+\gamma+1}+\gamma\frac{|\|\widehat{\mathbf{\bm{q}}}(\mathbf{\bm{x}})\|_{1}-\|\mathbf{\bm{p}}(\mathbf{\bm{x}})\|_{1}|}{(\tau+\gamma)^{2}}$
$\displaystyle\leq\big{(}\frac{3}{{2(1+\gamma)}}+c_{1}\big{)}{\|\widehat{\mathbf{\bm{q}}}(\mathbf{\bm{x}})-\mathbf{\bm{p}}(\mathbf{\bm{x}})\|_{1}},$

where the second inequality follows from the triangle inequality, $c_{1}=0$ if
$\gamma=0$, $c_{1}=1/\gamma$ if $\gamma>0$. Therefore,

$\displaystyle{\rm Dice}_{\gamma}(\boldsymbol{\delta}^{*})$
$\displaystyle-{\rm Dice}_{\gamma}(\widehat{\boldsymbol{\delta}})={\rm
Dice}_{\gamma}(\boldsymbol{\delta}^{*})-\widehat{{\rm
Dice}}_{\gamma}(\boldsymbol{\delta}^{*})+\widehat{{\rm
Dice}}_{\gamma}(\boldsymbol{\delta}^{*})-\widehat{{\rm
Dice}}_{\gamma}(\widehat{\boldsymbol{\delta}})+\widehat{{\rm
Dice}}_{\gamma}(\widehat{\boldsymbol{\delta}})-{\rm
Dice}_{\gamma}(\widehat{\boldsymbol{\delta}})$ $\displaystyle\leq{\rm
Dice}_{\gamma}(\boldsymbol{\delta}^{*})-\widehat{{\rm
Dice}}_{\gamma}(\boldsymbol{\delta}^{*})+\widehat{{\rm
Dice}}_{\gamma}(\widehat{\boldsymbol{\delta}})-{\rm
Dice}_{\gamma}(\widehat{\boldsymbol{\delta}})$
$\displaystyle\leq\mathbb{E}_{\mathbf{\bm{X}}}\big{|}\widehat{{\rm
Dice}}_{\gamma}({\boldsymbol{\delta}^{*}}(\mathbf{\bm{X}})|\mathbf{\bm{X}})-{\rm
Dice}_{\gamma}({\boldsymbol{\delta}^{*}}(\mathbf{\bm{X}})|\mathbf{\bm{X}})\big{|}+\mathbb{E}_{\mathbf{\bm{X}}}\big{|}\widehat{{\rm
Dice}}_{\gamma}(\widehat{\boldsymbol{\delta}}(\mathbf{\bm{X}})|\mathbf{\bm{X}})-{\rm
Dice}_{\gamma}(\widehat{\boldsymbol{\delta}}(\mathbf{\bm{X}})|\mathbf{\bm{X}})\big{|}$
$\displaystyle\leq\big{(}\frac{3}{1+\gamma}+2c_{1}\big{)}\mathbb{E}{\|\widehat{\mathbf{\bm{q}}}(\mathbf{\bm{X}})-\mathbf{\bm{p}}(\mathbf{\bm{X}})\|_{1}},$

where the first inequality follows from the definition of
$\widehat{\boldsymbol{\delta}}$ such that $\widehat{{\rm
Dice}}_{\gamma}(\boldsymbol{\delta}^{*})-\widehat{{\rm
Dice}}_{\gamma}(\widehat{\boldsymbol{\delta}})\leq 0$. This completes the
proof.

### Proof of Corollary 12

Proof  According to the Pinsker’s inequality, we have

$\displaystyle\mathbb{E}_{\mathbf{\bm{X}}}$
$\displaystyle{\|\widehat{\mathbf{\bm{q}}}(\mathbf{\bm{X}})-\mathbf{\bm{p}}(\mathbf{\bm{X}})\|_{1}}=\sum_{j=1}^{d}\mathbb{E}_{\mathbf{\bm{X}}}{|\widehat{{q}}_{j}(\mathbf{\bm{X}})-{p}_{j}(\mathbf{\bm{X}})|}\leq\sum_{j=1}^{d}\mathbb{E}_{\mathbf{\bm{X}}}\sqrt{\frac{1}{2}{\rm
KL}\big{(}\mathbb{P}(Y_{j}|\mathbf{\bm{X}}),\widehat{\mathbb{P}}(Y_{j}|\mathbf{\bm{X}})\big{)}}$
$\displaystyle\leq\sqrt{\frac{d}{2}\sum_{j=1}^{d}\mathbb{E}_{\mathbf{\bm{X}}}{\rm
KL}\big{(}\mathbb{P}(Y_{j}|\mathbf{\bm{X}}),\widehat{\mathbb{P}}(Y_{j}|\mathbf{\bm{X}})\big{)}}=\sqrt{\frac{d}{2}}\sqrt{\mathbb{E}\Big{(}l_{\text{CE}}\big{(}\mathbf{\bm{Y}},\widehat{\mathbf{\bm{q}}}(\mathbf{\bm{X}})\big{)}\Big{)}-\mathbb{E}\Big{(}l_{\text{CE}}\big{(}\mathbf{\bm{Y}},\mathbf{\bm{p}}(\mathbf{\bm{X}})\big{)}\Big{)}},$

where the last inequality follows from the Cauchy-Schwarz inequality and the
Jensen’s inequality, and ${\rm
KL}\big{(}\mathbb{P}(Y_{j}|\mathbf{\bm{x}}),\widehat{\mathbb{P}}(Y_{j}|\mathbf{\bm{x}})\big{)}:=p_{j}(\mathbf{\bm{x}})\log\big{(}p_{j}(\mathbf{\bm{x}})/\widehat{q}_{j}(\mathbf{\bm{x}})\big{)}+(1-p_{j}(\mathbf{\bm{x}}))\log((1-p_{j}(\mathbf{\bm{x}}))/(1-\widehat{q}_{j}(\mathbf{\bm{x}})))$
is the KL divergence between $\mathbb{P}(Y_{j}|\mathbf{\bm{x}})$ under
$\mathbf{\bm{p}}$ and $\widehat{\mathbb{P}}(Y_{j}|\mathbf{\bm{x}})$ under
$\widehat{\mathbf{\bm{q}}}$. The desirable result then follows by combining
(19) in Theorem 11. This completes the proof.

###  D.10 Proof of Lemma 13

Proof  Denote $\mathbf{\bm{y}}_{I}=(y_{j}:j\in I)^{\intercal}$,
$\mathbf{\bm{y}}_{\sm I}=(y_{j}:j\notin I)^{\intercal}$, and let
$I(\mathbf{\bm{v}})=I(\boldsymbol{\delta}(\mathbf{\bm{x}}))=\\{j:v_{j}=1\\}$
be a segmentation index set, and $\|\mathbf{\bm{v}}\|_{1}=\tau$. Again,
consider the point-wise maximization:

$\boldsymbol{\delta}^{*}(\mathbf{\bm{x}})=\mathop{\rm
argmax}_{\mathbf{\bm{v}}\in\\{0,1\\}^{d}}\ {{\rm
IoU}}_{\gamma}(\mathbf{\bm{v}}|\mathbf{\bm{x}}),$

where ${{\rm IoU}}_{\gamma}(\mathbf{\bm{v}}|\mathbf{\bm{x}})$ is defined as

$\displaystyle{{\rm IoU}}_{\gamma}(\mathbf{\bm{v}}|\mathbf{\bm{x}})$
$\displaystyle=\mathbb{E}\Big{(}\frac{\|\mathbf{\bm{Y}}_{I(\mathbf{\bm{v}})}\|_{1}+\gamma}{\|\mathbf{\bm{Y}}_{\sm
I(\mathbf{\bm{v}})}\|_{1}+\|\mathbf{\bm{v}}\|_{1}+\gamma}\Big{|}\mathbf{\bm{X}}=\mathbf{\bm{x}}\Big{)}$
$\displaystyle=\mathbb{E}\Big{(}\frac{\|\mathbf{\bm{Y}}_{I(\mathbf{\bm{v}})}\|_{1}}{\|\mathbf{\bm{Y}}_{\sm
I(\mathbf{\bm{v}})}\|_{1}+\tau+\gamma}\Big{|}\mathbf{\bm{X}}=\mathbf{\bm{x}}\Big{)}+\mathbb{E}\Big{(}\frac{\gamma}{\|\mathbf{\bm{Y}}_{\sm
I(\mathbf{\bm{v}})}\|_{1}+\tau+\gamma}\Big{|}\mathbf{\bm{X}}=\mathbf{\bm{x}}\Big{)}$
$\displaystyle=\Big{(}\mathbb{E}(\|\mathbf{\bm{Y}}_{I(\mathbf{\bm{v}})}\|_{1}|\mathbf{\bm{X}}=\mathbf{\bm{x}})+\gamma\Big{)}\mathbb{E}\Big{(}\frac{1}{\|\mathbf{\bm{Y}}_{\sm
I(\mathbf{\bm{v}})}\|_{1}+\tau+\gamma}\Big{|}\mathbf{\bm{X}}=\mathbf{\bm{x}}\Big{)},$

where the last equality follows from the fact that
$\mathbf{\bm{Y}}_{I(\mathbf{\bm{v}})}\perp\mathbf{\bm{Y}}_{\sm
I(\mathbf{\bm{v}})}\mid\mathbf{\bm{X}}$. Fix $\tau=\|\mathbf{\bm{v}}\|_{1}$.
The first term is maximized at
$\mathbf{\bm{v}}^{*}=(v_{1}^{*},\cdots,v_{d}^{*})$ with

$\displaystyle{v}^{*}_{j}=\begin{cases}1&\text{if
}p_{j}(\mathbf{\bm{x}})\text{ ranks top }\tau,\\\
0&\text{otherwise},\end{cases}$

and the maximum value is $\sum_{j\in
J_{\tau}(\mathbf{\bm{x}})}p_{j}(\mathbf{\bm{x}})+\gamma$. The second term is

$\displaystyle\mathbb{E}\Big{(}\frac{1}{\|\mathbf{\bm{Y}}_{\sm
I(\mathbf{\bm{v}})}\|_{1}+\tau+\gamma}\Big{|}\mathbf{\bm{X}}=\mathbf{\bm{x}}\Big{)}=\mathbb{E}\Big{(}\frac{1}{\Gamma_{\sm
I(\mathbf{\bm{v}})}(\mathbf{\bm{x}})+\tau+\gamma}\Big{)}.$

Given $I(\mathbf{\bm{v}})\neq I(\mathbf{\bm{v}}^{*})$, we have $\Gamma_{\sm
I(\mathbf{\bm{v}})}(\mathbf{\bm{x}})=\sum_{j=1}^{d-\tau}B_{j}$ and
$\Gamma_{\sm
I(\mathbf{\bm{v}}^{*})}(\mathbf{\bm{x}})=\sum_{j=1}^{d-\tau}B^{*}_{j}$, where
$B_{j}$ and $B^{*}_{j}$ are independent Bernoulli variables with success
probability $p_{j}\geq p^{*}_{j}$, respectively, for $j=1,\cdots,d-\tau$. By
Theorem 2.2.9 of Belzunce et al. (2015), $\Gamma_{\sm
I(\mathbf{\bm{v}})}(\mathbf{\bm{x}})$ is stochastically greater than
$\Gamma_{\sm I(\mathbf{\bm{v}}^{*})}(\mathbf{\bm{x}})$, namely

$\mathbb{P}(\Gamma_{\sm
I(\mathbf{\bm{v}})}(\mathbf{\bm{x}})\leq\varsigma)\leq\mathbb{P}(\Gamma_{\sm
I(\mathbf{\bm{v}}^{*})}(\mathbf{\bm{x}})\leq\varsigma)$

for any $\varsigma\in\mathbb{R}$. Thus,

$\displaystyle\mathbb{E}\Big{(}\frac{1}{\Gamma_{\sm
I(\mathbf{\bm{v}})}(\mathbf{\bm{x}})+\tau+\gamma}\Big{)}$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}\Big{(}\frac{1}{\Gamma_{\sm
I(\mathbf{\bm{v}})}(\mathbf{\bm{x}})+\tau+\gamma}\geq\varsigma\Big{)}d\varsigma$
$\displaystyle\leq\int_{0}^{\infty}\mathbb{P}\Big{(}\frac{1}{\Gamma_{\sm
I(\mathbf{\bm{v}}^{*})}(\mathbf{\bm{x}})+\tau+\gamma}\geq\varsigma\Big{)}d\varsigma=\mathbb{E}\Big{(}\frac{1}{\Gamma_{\sm
I(\mathbf{\bm{v}}^{*})}(\mathbf{\bm{x}})+\tau+\gamma}\Big{)}.$

As a result, the second term is also maximized at $\mathbf{\bm{v}}^{*}$.
Therefore, $\mathbf{\bm{v}}^{*}$ maximizes ${\rm
IoU}_{\gamma}(\mathbf{\bm{v}}|\mathbf{\bm{x}})$ for a fixed $\tau$. The
desired result follows.

###  D.11 Proof of Lemma 14

Proof  Without loss of generality, assuming
$\widehat{q}_{1}(\mathbf{\bm{x}})\geq\cdots\geq\widehat{q}_{d}(\mathbf{\bm{x}})$
are fixed, then for any $\tau^{\prime}>\tau$,

$\begin{split}&\varpi_{\tau}(\mathbf{\bm{x}})-\varpi_{\tau^{\prime}}(\mathbf{\bm{x}})\\\
&=\Big{(}\sum_{j=1}^{\tau}\widehat{q}_{j}(\mathbf{\bm{x}})+\gamma\Big{)}\mathbb{E}\Big{(}\frac{1}{\widehat{\Gamma}_{\sm
J_{\tau}(\mathbf{\bm{x}})}+\tau+\gamma}\Big{)}-\Big{(}\sum_{j=1}^{\tau^{\prime}}\widehat{q}_{j}(\mathbf{\bm{x}})+\gamma\Big{)}\mathbb{E}\Big{(}\frac{1}{\widehat{\Gamma}_{\sm
J_{\tau^{\prime}}(\mathbf{\bm{x}})}+\tau^{\prime}+\gamma}\Big{)}\\\
&=\Big{(}\sum_{j=1}^{\tau}\widehat{q}_{j}(\mathbf{\bm{x}})+\gamma\Big{)}\mathbb{E}\Big{(}\frac{1}{\widehat{\Gamma}_{\sm
J_{\tau^{\prime}}(\mathbf{\bm{x}})}+\sum_{j=\tau+1}^{\tau^{\prime}}\widehat{B}_{j}(\mathbf{\bm{x}})+\tau+\gamma}\Big{)}-\Big{(}\sum_{j=1}^{\tau^{\prime}}\widehat{q}_{j}(\mathbf{\bm{x}})+\gamma\Big{)}\mathbb{E}\Big{(}\frac{1}{\widehat{\Gamma}_{\sm
J_{\tau^{\prime}}(\mathbf{\bm{x}})}+\tau^{\prime}+\gamma}\Big{)}\\\
&=\mathbb{E}\Big{(}\frac{(\sum_{j=1}^{\tau}\widehat{q}_{j}(\mathbf{\bm{x}})+\gamma)(\widehat{\Gamma}_{\sm
J_{\tau^{\prime}}(\mathbf{\bm{x}})}+\tau^{\prime}+\gamma)-(\sum_{j=1}^{\tau^{\prime}}\widehat{q}_{j}(\mathbf{\bm{x}})+\gamma)(\widehat{\Gamma}_{\sm
J_{\tau^{\prime}}(\mathbf{\bm{x}})}+\sum_{j=\tau+1}^{\tau^{\prime}}\widehat{B}_{j}(\mathbf{\bm{x}})+\tau+\gamma)}{(\widehat{\Gamma}_{\sm
J_{\tau^{\prime}}(\mathbf{\bm{x}})}+\sum_{j=\tau+1}^{\tau^{\prime}}\widehat{B}_{j}(\mathbf{\bm{x}})+\tau+\gamma)(\widehat{\Gamma}_{\sm
J_{\tau^{\prime}}(\mathbf{\bm{x}})}+\tau^{\prime}+\gamma)}\Big{)}\\\
&=\mathbb{E}\Big{(}\frac{(\sum_{j=1}^{\tau}\widehat{q}_{j}(\mathbf{\bm{x}})+\gamma)(\tau^{\prime}-\tau-\sum_{j=\tau+1}^{\tau^{\prime}}\widehat{B}_{j}(\mathbf{\bm{x}}))}{(\widehat{\Gamma}_{\sm
J_{\tau^{\prime}}(\mathbf{\bm{x}})}+\sum_{j=\tau+1}^{\tau^{\prime}}\widehat{B}_{j}(\mathbf{\bm{x}})+\tau+\gamma)(\widehat{\Gamma}_{\sm
J_{\tau^{\prime}}(\mathbf{\bm{x}})}+\tau^{\prime}+\gamma)}\Big{)}-\mathbb{E}\Big{(}\frac{\sum_{j=\tau+1}^{\tau^{\prime}}\widehat{q}_{j}(\mathbf{\bm{x}})}{\widehat{\Gamma}_{\sm
J_{\tau^{\prime}}(\mathbf{\bm{x}})}+\tau^{\prime}+\gamma}\Big{)}\\\
&\geq\frac{(\sum_{j=1}^{\tau}\widehat{q}_{j}(\mathbf{\bm{x}})+\gamma)(\tau^{\prime}-\tau-\sum_{j=\tau+1}^{\tau^{\prime}}\widehat{q}_{j}(\mathbf{\bm{x}}))}{((d-\tau^{\prime})\widehat{q}_{\tau+1}(\mathbf{\bm{x}})+\tau^{\prime}+\gamma)^{2}}-\frac{\sum_{j=\tau+1}^{\tau^{\prime}}\widehat{q}_{j}(\mathbf{\bm{x}})}{\tau^{\prime}+\gamma}\\\
&\geq\frac{(\sum_{j=1}^{\tau}\widehat{q}_{j}(\mathbf{\bm{x}})+\gamma)(\tau^{\prime}-\tau)(1-\widehat{q}_{\tau+1}(\mathbf{\bm{x}}))}{((d-\tau^{\prime})\widehat{q}_{\tau+1}(\mathbf{\bm{x}})+\tau^{\prime}+\gamma)^{2}}-\frac{(\tau^{\prime}-\tau)\widehat{q}_{\tau+1}(\mathbf{\bm{x}})}{\tau^{\prime}+\gamma}\geq
0,\end{split}$

whenever

$\begin{split}\sum_{j=1}^{\tau}\widehat{q}_{j}(\mathbf{\bm{x}})+\gamma&\geq\frac{\widehat{q}_{\tau+1}(\mathbf{\bm{x}})}{1-\widehat{q}_{\tau+1}(\mathbf{\bm{x}})}\max_{\tau^{\prime}>\tau}\frac{((d-\tau^{\prime})\widehat{q}_{\tau+1}(\mathbf{\bm{x}})+\tau^{\prime}+\gamma)^{2}}{\tau^{\prime}+\gamma}\\\
&=\frac{\widehat{q}_{\tau+1}(\mathbf{\bm{x}})}{1-\widehat{q}_{\tau+1}(\mathbf{\bm{x}})}\max\Big{(}d+\gamma,\frac{((d-\tau)\widehat{q}_{\tau+1}(\mathbf{\bm{x}})+\tau+\gamma)^{2}}{\tau+\gamma}\Big{)}.\end{split}$

This completes the proof.

###  D.12 Proof of Theorem 15

Proof  Similar to the proof of Theorem 11, we consider point-wise
approximation of IoU metric under $\mathbf{\bm{p}}$ and
$\widehat{\mathbf{\bm{q}}}$. For any $\mathbf{\bm{\delta}}$ such that
$\delta_{j}(\mathbf{\bm{x}})=1$ for $j\in J_{\tau}(\mathbf{\bm{x}})$ and
$\delta_{j}(\mathbf{\bm{x}})=0$ otherwise. Define

$\displaystyle\widehat{{\rm
IoU}}_{\gamma}({\boldsymbol{\delta}}(\mathbf{\bm{x}})|\mathbf{\bm{X}}=\mathbf{\bm{x}})$
$\displaystyle:=\Big{(}\sum_{s=1}^{\tau}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})+\gamma\Big{)}\sum_{l=0}^{d-\tau}\frac{\mathbb{P}\big{(}\widehat{\Gamma}_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})=l\big{)}}{\tau+l+\gamma}$
$\displaystyle=\Big{(}\sum_{s=1}^{\tau}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})+\gamma\Big{)}\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\widehat{\Gamma}_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})}\big{)},$ $\displaystyle{\rm
IoU}_{\gamma}({\boldsymbol{\delta}}(\mathbf{\bm{x}})|\mathbf{\bm{X}}=\mathbf{\bm{x}})$
$\displaystyle:=\Big{(}\sum_{s=1}^{\tau}p_{j}(\mathbf{\bm{x}})+\gamma\Big{)}\sum_{l=0}^{d-\tau}\frac{\mathbb{P}\big{(}\Gamma_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})=l\big{)}}{\tau+l+\gamma}$
$\displaystyle=\Big{(}\sum_{s=1}^{\tau}p_{j}(\mathbf{\bm{x}})+\gamma\Big{)}\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\Gamma_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})}\big{)}.$

We have

$\displaystyle\big{|}\widehat{{\rm
IoU}}_{\gamma}({\boldsymbol{\delta}}(\mathbf{\bm{x}})|\mathbf{\bm{X}}=\mathbf{\bm{x}})-{\rm
IoU}_{\gamma}({\boldsymbol{\delta}}(\mathbf{\bm{x}})|\mathbf{\bm{X}}=\mathbf{\bm{x}})\big{|}$
$\displaystyle\leq\Big{|}\sum_{s=1}^{\tau}\Big{(}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\widehat{\Gamma}_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})}\big{)}-p_{j_{s}}(\mathbf{\bm{x}})\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\Gamma_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})}\big{)}\Big{)}\Big{|}$
$\displaystyle\qquad+\gamma\Big{|}\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\widehat{\Gamma}_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})}\big{)}-\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\Gamma_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})}\big{)}\Big{|}$
$\displaystyle\leq\Big{|}\sum_{s=1}^{\tau}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})\Big{(}\mathbb{E}\big{(}\frac{1}{\tau+\gamma+1+\widehat{\Gamma}_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})}\big{)}-\mathbb{E}\big{(}\frac{1}{\tau+\gamma+1+\Gamma_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})}\big{)}\Big{)}\Big{|}$
$\displaystyle\qquad+\Big{|}\sum_{s=1}^{\tau}\big{(}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})-p_{j_{s}}(\mathbf{\bm{x}})\big{)}\mathbb{E}\big{(}\frac{1}{\tau+\gamma+1+\Gamma_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})}\big{)}\Big{)}\Big{|}$
$\displaystyle\qquad+\gamma\Big{|}\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\widehat{\Gamma}_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})}\big{)}-\mathbb{E}\big{(}\frac{1}{\tau+\gamma+\Gamma_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})}\big{)}\Big{|}$
$\displaystyle\leq\sum_{s=1}^{\tau}\Big{|}\frac{\mathbb{E}\big{(}\Gamma_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})-\widehat{\Gamma}_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})\big{)}}{(\tau+\gamma+1)^{2}}\Big{|}+\sum_{s=1}^{\tau}\frac{\big{|}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})-p_{j_{s}}(\mathbf{\bm{x}})\big{|}}{\tau+\gamma+1}+\gamma\Big{|}\frac{\mathbb{E}\big{(}\Gamma_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})-\widehat{\Gamma}_{\sm
J_{\tau}(\mathbf{\bm{x}})}(\mathbf{\bm{x}})\big{)}}{(\tau+\gamma)^{2}}\Big{|}$
$\displaystyle\leq\sum_{s=1}^{\tau}\frac{\|\widehat{\mathbf{\bm{q}}}(\mathbf{\bm{x}})-\mathbf{\bm{p}}(\mathbf{\bm{x}})\|_{1}}{(\tau+\gamma+1)^{2}}+\sum_{s=1}^{\tau}\frac{\big{|}\widehat{q}_{j_{s}}(\mathbf{\bm{x}})-p_{j_{s}}(\mathbf{\bm{x}})\big{|}}{\tau+\gamma+1}+\gamma\frac{\|\widehat{\mathbf{\bm{q}}}(\mathbf{\bm{x}})-\mathbf{\bm{p}}(\mathbf{\bm{x}})\|_{1}}{(\tau+\gamma)^{2}}$
$\displaystyle\leq
C_{2}{\|\widehat{\mathbf{\bm{q}}}(\mathbf{\bm{x}})-\mathbf{\bm{p}}(\mathbf{\bm{x}})\|_{1}},$

where $C_{2}$ is a constant that may depend on $\gamma$. Then the rest of the
proof follows from the same arguments for Theorems 11 and 12 with Dice
replaced by IoU, and is omitted.

##  Appendix E Auxiliary Lemmas

###### Lemma 16

Suppose $\Gamma=\sum_{j=1}^{d}B_{j}$ is a Poisson binomial random variable,
and $B_{j}(j=1,\cdots,d)$ are independent Bernoulli trials with success
probabilities $p_{1},\cdots,p_{d}$. Then, for any $j=1,\cdots,d$, we have

$\mathbb{P}\big{(}\Gamma_{\sm j}\leq l-1\big{)}\leq\mathbb{P}\big{(}\Gamma\leq
l\big{)}\leq\mathbb{P}\big{(}\Gamma_{\sm j}\leq l\big{)},$

where $\Gamma_{\sm j}=\sum_{j^{\prime}\neq j}B_{j^{\prime}}$.

Proof  Note that $\Gamma=\Gamma_{\sm j}+B_{j}$, then

$\displaystyle\mathbb{P}(\Gamma\leq l)$ $\displaystyle=\mathbb{P}(\Gamma_{\sm
j}+B_{j}\leq l)=\mathbb{P}(\Gamma_{\sm j}\leq l\mid
B_{j}=0)(1-p_{j})+\mathbb{P}(\Gamma_{\sm j}\leq l-1\mid B_{j}=1)p_{j}$
$\displaystyle=\mathbb{P}(\Gamma_{\sm j}\leq
l)(1-p_{j})+\mathbb{P}(\Gamma_{\sm j}\leq l-1)p_{j},$

where the last equality follows from the fact that $B_{j}\perp B_{j^{\prime}}$
for $j\neq j^{\prime}$. The desirable result then follows since
$\mathbb{P}(\Gamma_{\sm j}\leq l)\geq\mathbb{P}(\Gamma_{\sm j}\leq l-1)$.

###### Lemma 17

Suppose $\Gamma=\sum_{j=1}^{d}B_{j}$ is a Poisson binomial random variable,
and $B_{j}(j=1,\cdots,d)$ are independent Bernoulli trials with success
probabilities $p_{1}\geq p_{2}\geq\cdots\geq p_{d}$. Then, for an arbitrary
positive non-decreasing sequence $\zeta_{l}$ $(l=0,\cdots,d-1)$,

$Q_{j}=\sum_{l=0}^{d-1}\frac{1}{\zeta_{l}}\mathbb{P}(\Gamma_{\sm j}=l)$

is a non-increasing function with respect to $j=1,\cdots,d$.

Proof  Note that for any $j^{\prime}\neq j$, $\Gamma_{\sm j}=\sum_{i\neq
j}B_{i}=\sum_{i\neq j,j^{\prime}}B_{i}+B_{j^{\prime}}=:\Gamma_{\sm
jj^{\prime}}+B_{j^{\prime}}$. Denote $\xi_{\sm
jj^{\prime},l}=\mathbb{P}\big{(}\Gamma_{\sm jj^{\prime}}=l\big{)}$, we have

$\displaystyle\mathbb{P}\big{(}\Gamma_{\sm
j}=l\big{)}=(1-p_{j^{\prime}})\xi_{\sm jj^{\prime},l}+p_{j^{\prime}}\xi_{\sm
jj^{\prime},l-1}.$

Then,

$\displaystyle Q_{j}-Q_{j^{\prime}}$
$\displaystyle=\sum_{l=0}^{d}\frac{1}{\zeta_{l}}\big{(}(1-p_{j^{\prime}})\xi_{\sm
jj^{\prime},l}+p_{j^{\prime}}\xi_{\sm jj^{\prime},l-1}-(1-p_{j})\xi_{\sm
jj^{\prime},l}-p_{j}\xi_{\sm jj^{\prime},l-1}\big{)}$
$\displaystyle=\sum_{l=0}^{d}\frac{1}{\zeta_{l}}(\xi_{\sm
jj^{\prime},l}-\xi_{\sm
jj^{\prime},l-1})=(p_{j}-p_{j^{\prime}})\Big{(}\sum_{l=0}^{d}\frac{1}{\zeta_{l}}\xi_{\sm
jj^{\prime},l}-\sum_{l=0}^{d}\frac{1}{\zeta_{l}}\xi_{\sm
jj^{\prime},l-1}\Big{)}$
$\displaystyle=(p_{j}-p_{j^{\prime}})\Big{(}\sum_{l=0}^{d}\big{(}\frac{1}{\zeta_{l}}-\frac{1}{\zeta_{l+1}})\xi_{\sm
jj^{\prime},l}\Big{)},$

where the first equality follows from the fact that $\mathbb{P}(\Gamma_{\sm
j}=d)=0$, and the last equality follows from the fact that $\xi_{\sm
jj^{\prime},l}=0$ for $l<0$. Hence, we have $Q_{j}-Q_{j^{\prime}}$ has the
same sign with $p_{j}-p_{j^{\prime}}$, and the desirable result then follows.

###### Lemma 18

Let $\Gamma$ be a Poisson-binomial random variable with the success
probability $(p_{j})_{j=1,\cdots,d}$, then for any $\tau\geq 1$, we have

$(\sum_{j=1}^{d}p_{j}+\tau)^{-1}\leq\mathbb{E}\big{(}\frac{1}{\Gamma+\tau}\big{)}\leq(\frac{d+1}{d}\sum_{j=1}^{d}p_{j}+\tau-1)^{-1}.$

Proof  According to the corollary in Chao and Strawderman (1972), we have

$\displaystyle\mathbb{E}\big{(}\frac{1}{\Gamma+\tau}\big{)}$
$\displaystyle=\int_{0}^{1}t^{\tau-1}P_{\Gamma}(t)dt=\int_{0}^{1}t^{\tau-1}\big{(}\prod_{j=1}^{d}(1-p_{j}+p_{j}t)\big{)}dt\leq\int_{0}^{1}t^{\tau-1}(1-\bar{p}+\bar{p}t)^{d}dt$
$\displaystyle=\mathbb{E}\big{(}\frac{1}{\Lambda+\tau}\big{)}\leq(\frac{d+1}{d}\sum_{j=1}^{d}p_{j}+\tau-1)^{-1},$

where $\bar{p}=d^{-1}\sum_{j=1}^{d}p_{j}$, the first inequality follows from
the inequality of arithmetic and geometric means, the last equality follows
from Section 3.1 of Chao and Strawderman (1972), and the last inequality
follows from (25) in Wooff (1985). This completes the proof.

## References

  * Ajtai et al. (1983) Miklós Ajtai, János Komlós, and Endre Szemerédi.  An ${O}$($nlogn$) sorting network.  In _Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing_ , pages 1–9, 1983.
  * Assidiq et al. (2008) Abdulhakam AM Assidiq, Othman O Khalifa, Md Rafiqul Islam, and Sheroz Khan.  Real time lane detection for autonomous vehicles.  In _2008 International Conference on Computer and Communication Engineering_ , pages 82–88. IEEE, 2008.
  * Badrinarayanan et al. (2017) Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla.  Segnet: A deep convolutional encoder-decoder architecture for image segmentation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 39(12):2481–2495, 2017.
  * Bao and Sugiyama (2020) Han Bao and Masashi Sugiyama.  Calibrated surrogate maximization of linear-fractional utility in binary classification.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2337–2347. PMLR, 2020.
  * Bartlett et al. (2005) Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson.  Local rademacher complexities.  _Annals of Statistics_ , 33(4):1497–1537, 2005\.
  * Bartlett et al. (2006) Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe.  Convexity, classification, and risk bounds.  _Journal of the American Statistical Association_ , 101(473):138–156, 2006.
  * Belzunce et al. (2015) Felix Belzunce, Carolina Martinez Riquelme, and Julio Mulero.  _An introduction to stochastic orders_.  Academic Press, 2015.
  * Berman et al. (2018) Maxim Berman, Amal Rannen Triki, and Matthew B Blaschko.  The lovász-softmax loss: A tractable surrogate for the optimization of the intersection-over-union measure in neural networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 4413–4421, 2018.
  * Bertels et al. (2019) Jeroen Bertels, David Robben, Dirk Vandermeulen, and Paul Suetens.  Optimization with soft dice can lead to a volumetric bias.  In _International MICCAI Brainlesion Workshop_ , pages 89–97. Springer, 2019.
  * Bice et al. (2021) Noah Bice, Neil Kirby, Ruiqi Li, Dan Nguyen, Tyler Bahr, Christopher Kabat, Pamela Myers, Niko Papanikolaou, and Mohamad Fakhreddine.  A sensitivity analysis of probability maps in deep-learning-based anatomical segmentation.  _Journal of Applied Clinical Medical Physics_ , 22(8):105–119, 2021.
  * Bracewell and Bracewell (1986) Ronald Newbold Bracewell and Ronald N Bracewell.  _The Fourier Transform and Its Applications_ , volume 31999.  McGraw-hill New York, 1986.
  * Chao and Strawderman (1972) Min-Te Chao and WE Strawderman.  Negative moments of positive random variables.  _Journal of the American Statistical Association_ , 67(338):429–431, 1972.
  * Chapelle and Chang (2011) Olivier Chapelle and Yi Chang.  Yahoo! learning to rank challenge overview.  In _Proceedings of the learning to rank challenge_ , pages 1–24. PMLR, 2011.
  * Charoenphakdee et al. (2021) Nontawat Charoenphakdee, Jayakorn Vongkulbhisal, Nuttapong Chairatanakul, and Masashi Sugiyama.  On focal loss for class-posterior probability estimation: A theoretical perspective.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5202–5211, 2021.
  * Chen et al. (2018) Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.  Encoder-decoder with atrous separable convolution for semantic image segmentation.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 801–818, 2018.
  * Clémençon et al. (2008) Stéphan Clémençon, Gábor Lugosi, and Nicolas Vayatis.  Ranking and empirical minimization of u-statistics.  _Annals of Statistics_ , 36(2):844–874, 2008\.
  * Cordts et al. (2016) Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The Cityscapes dataset for semantic urban scene understanding.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 3213–3223, 2016.
  * Cortes and Vapnik (1995) Corinna Cortes and Vladimir Vapnik.  Support-vector networks.  _Machine Learning_ , 20(3):273–297, 1995.
  * Cox (1958) David R Cox.  The regression analysis of binary sequences.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 20(2):215–232, 1958.
  * Crouse (2016) David F Crouse.  On implementing 2d rectangular assignment algorithms.  _IEEE Transactions on Aerospace and Electronic Systems_ , 52(4):1679–1696, 2016.
  * D’Ambrosio et al. (2020) Claudia D’Ambrosio, Silvano Martello, and Michele Monaci.  Lower and upper bounds for the non-linear generalized assignment problem.  _Computers & Operations Research_, 120:104933, 2020.
  * Edmonds and Karp (1972) Jack Edmonds and Richard M Karp.  Theoretical improvements in algorithmic efficiency for network flow problems.  _Journal of the ACM (JACM)_ , 19(2):248–264, 1972\.
  * Everingham et al. (2012) M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman.  The PASCAL Visual Object Classes Challenge 2012 (VOC2012) Results.  http://www.pascal-network.org/challenges/VOC/voc2012/workshop/index.html, 2012\.
  * Giné and Koltchinskii (2006) Evarist Giné and Vladimir Koltchinskii.  Concentration inequalities and asymptotic results for ratio type empirical processes.  _Annals of Probability_ , 34(3):1143–1216, 2006\.
  * Gneiting and Raftery (2007) Tilmann Gneiting and Adrian E Raftery.  Strictly proper scoring rules, prediction, and estimation.  _Journal of the American statistical Association_ , 102(477):359–378, 2007.
  * Guo et al. (2017) Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger.  On calibration of modern neural networks.  In _International Conference on Machine Learning_ , pages 1321–1330. PMLR, 2017.
  * Hariharan et al. (2011) Bharath Hariharan, Pablo Arbeláez, Lubomir Bourdev, Subhransu Maji, and Jitendra Malik.  Semantic contours from inverse detectors.  In _2011 International Conference on Computer Vision_ , pages 991–998. IEEE, 2011.
  * Hong (2013) Yili Hong.  On computing the distribution function for the poisson binomial distribution.  _Computational Statistics & Data Analysis_, 59:41–51, 2013.
  * Jadon (2021) Shruti Jadon.  Semsegloss: A python package of loss functions for semantic segmentation.  _Software Impacts_ , 9:100078, 2021.
  * Kuhn (1955) Harold W Kuhn.  The hungarian method for the assignment problem.  _Naval Research Logistics Quarterly_ , 2(1-2):83–97, 1955.
  * Lin et al. (2017) Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2980–2988, 2017.
  * Lin (2004) Yi Lin.  A note on margin-based loss functions in classification.  _Statistics & Probability Letters_, 68(1):73–82, 2004.
  * Lipton et al. (2014) Zachary C Lipton, Charles Elkan, and Balakrishnan Naryanaswamy.  Optimal thresholding of classifiers to maximize F1 measure.  In _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings, Part II 14_ , pages 225–239. Springer, 2014.
  * Liu et al. (2021) Sheng Liu, Aakash Kaku, Weicheng Zhu, Matan Leibovich, Sreyas Mohan, Boyang Yu, Haoxiang Huang, Laure Zanna, Narges Razavian, Jonathan Niles-Weed, et al.  Deep probability estimation.  _arXiv preprint arXiv:2111.10734_ , 2021.
  * Long et al. (2015) Jonathan Long, Evan Shelhamer, and Trevor Darrell.  Fully convolutional networks for semantic segmentation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 3431–3440, 2015.
  * Milletari et al. (2016) Fausto Milletari, Nassir Navab, and Seyed-Ahmad Ahmadi.  V-net: Fully convolutional neural networks for volumetric medical image segmentation.  In _2016 Fourth International Conference on 3D Vision (3DV)_ , pages 565–571. IEEE, 2016.
  * Murty and Kabadi (1985) Katta G Murty and Santosh N Kabadi.  Some np-complete problems in quadratic and nonlinear programming.  Technical report, 1985.
  * Neammanee (2005) Kritsana Neammanee.  A refinement of normal approximation to poisson binomial.  _International Journal of Mathematics and Mathematical Sciences_ , 2005(5):717–728, 2005.
  * Nickolls et al. (2008) John Nickolls, Ian Buck, Michael Garland, and Kevin Skadron.  Scalable parallel programming with cuda: Is cuda the parallel programming model that application developers have been waiting for?  _Queue_ , 6(2):40–53, 2008.
  * Nordström et al. (2020) Marcus Nordström, Han Bao, Fredrik Löfman, Henrik Hult, Atsuto Maki, and Masashi Sugiyama.  Calibrated surrogate maximization of Dice.  In _Medical Image Computing and Computer Assisted Intervention–MICCAI 2020: 23rd International Conference, Lima, Peru, October 4–8, 2020, Proceedings, Part IV 23_ , pages 269–278. Springer, 2020.
  * Ouali (2022) Yassine Ouali.  Github repository: pytorch-segmentation.  https://github.com/yassouali/pytorch-segmentation, 2022.
  * Pollard (1984) David Pollard.  _Convergence of Stochastic Processes_.  Springer Science & Business Media, 1984.
  * Popordanoska et al. (2021) Teodora Popordanoska, Jeroen Bertels, Dirk Vandermeulen, Frederik Maes, and Matthew B Blaschko.  On the relationship between calibrated predictors and unbiased volume estimation.  In _Medical Image Computing and Computer Assisted Intervention–MICCAI 2021: 24th International Conference, Strasbourg, France, September 27–October 1, 2021, Proceedings, Part I 24_ , pages 678–688. Springer, 2021.
  * Ronneberger et al. (2015) Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ , pages 234–241. Springer, 2015.
  * Salehi et al. (2017) Seyed Sadegh Mohseni Salehi, Deniz Erdogmus, and Ali Gholipour.  Tversky loss function for image segmentation using 3d fully convolutional deep networks.  In _International Workshop on Machine Learning in Medical Imaging_ , pages 379–387. Springer, 2017.
  * Shen (1997) Xiaotong Shen.  On methods of sieves and penalization.  _Annals of Statistics_ , 25(6):2555–2591, 1997\.
  * Shou et al. (2017) Zheng Shou, Jonathan Chan, Alireza Zareian, Kazuyuki Miyazawa, and Shih-Fu Chang.  Cdc: Convolutional-de-convolutional networks for precise temporal action localization in untrimmed videos.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5734–5743, 2017.
  * Sudre et al. (2017) Carole H Sudre, Wenqi Li, Tom Vercauteren, Sebastien Ourselin, and M Jorge Cardoso.  Generalised dice overlap as a deep learning loss function for highly unbalanced segmentations.  In _Deep Learning in Medical Image Analysis and Multimodal Learning for Clinical Decision Support_ , pages 240–248. Springer, 2017.
  * Tahmasebi et al. (2012) Pejman Tahmasebi, Ardeshir Hezarkhani, and Muhammad Sahimi.  Multiple-point geostatistical modeling based on the cross-correlation functions.  _Computational Geosciences_ , 16(3):779–797, 2012\.
  * Tewari and Bartlett (2007) Ambuj Tewari and Peter L Bartlett.  On the consistency of multiclass classification methods.  _Journal of Machine Learning Research_ , 8(5), 2007.
  * Tomizawa (1971) Nobuaki Tomizawa.  On some techniques useful for solution of transportation network problems.  _Networks_ , 1(2):173–194, 1971.
  * Wang et al. (2018) Guotai Wang, Maria A Zuluaga, Wenqi Li, Rosalind Pratt, Premal A Patel, Michael Aertsen, Tom Doel, Anna L David, Jan Deprest, Sébastien Ourselin, et al.  Deepigeos: a deep interactive geodesic framework for medical image segmentation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 41(7):1559–1572, 2018.
  * Wooff (1985) David A Wooff.  Bounds on reciprocal moments with applications and developments in stein estimation and post-stratification.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 47(2):362–371, 1985.
  * Xin et al. (2018) Yang Xin, Lingshuang Kong, Zhi Liu, Chunhua Wang, Hongliang Zhu, Mingcheng Gao, Chensu Zhao, and Xiaoke Xu.  Multimodal feature-level fusion for biometrics identification system on iomt platform.  _IEEE Access_ , 6:21418–21426, 2018.
  * Zhang (2004) Tong Zhang.  Statistical behavior and consistency of classification methods based on convex risk minimization.  _Annals of Statistics_ , 32(1):56–85, 2004.
  * Zhao et al. (2017) Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia.  Pyramid scene parsing network.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 2881–2890, 2017.