Surrogate regret controls classification regret with explicit tie and scale terms

Under AC [A1], the event identities [F1] imply, first for indicators and finite nonnegative simple functions and then by [F3] for every nonnegative measurable $f:\mathsf{X}\to [0,\mathrm{\infty }]$, that $\mathbb{E}[{\mathbf{1}}_{\{Y=+1\}}f(X)]=\mathbb{E}[\eta (X)f(X)],\mathbb{E}[{\mathbf{1}}_{\{Y=-1\}}f(X)]=\mathbb{E}[(1-\eta (X))f(X)]\mathrm{.}$ For simple $f$ this follows by finite additivity of the event identities; increasing simple approximation and monotone convergence give the general case.

The function $\mathrm{\Phi }$ is continuous by [F4], hence Borel; its endpoint extension by one-sided limits is Borel on the extended real line. Since $h$ is measurable, the measurable-map definition [F7] makes $\mathrm{\Phi }\circ h$ and $\mathrm{\Phi }\circ (-h)$ measurable and nonnegative. Applying step 1.1 to these functions gives $L_{\mathrm{\Phi }}(h)=\mathbb{E}[L_{\mathrm{\Phi }}(X,h(X))]\mathrm{.}$ This identity also verifies measurability of the conditional-risk integrand used below.

Put $m(x)=L_{\mathrm{\Phi }}(x,h_{\mathrm{\Phi }}^{\ast }(x))$ and $g(x)=L_{\mathrm{\Phi }}(x,0)-m(x)$. Minimality gives $0\le m(x)\le L_{\mathrm{\Phi }}(x,0)=\mathrm{\Phi }(0)$ and $g(x)\ge 0$ for every $x$, so $L_{\mathrm{\Phi }}^{\ast }=\mathbb{E}m(X)<\mathrm{\infty }$. Here $m$ is measurable: for the endpoint-valued minimizer, each weighted term is the limit of the measurable functions $\eta (x)\min \{\mathrm{\Phi }(-h_{\mathrm{\Phi }}^{\ast }(x)),n\}$ or $(1-\eta (x))\min \{\mathrm{\Phi }(h_{\mathrm{\Phi }}^{\ast }(x)),n\}$, respectively; this also implements $0\cdot \mathrm{\infty }=0$. For the score $h$, put $R(x)=L_{\mathrm{\Phi }}(x,h(x))$ and $D_0(x)=R(x)-m(x)\ge 0$. By step 2.1, $\mathbb{E}R(X)=L_{\mathrm{\Phi }}(h)$, while $R=D_0+m$ pointwise because $m$ is finite. Additivity [F8] gives $\mathbb{E}{D}_0(X)=L_{\mathrm{\Phi }}(h)-L_{\mathrm{\Phi }}^{\ast }<\mathrm{\infty }$. By [F9], $N=\{D_0=+\mathrm{\infty }\}$ is measurable and null. Set $D=D_0$ on $N^c$ and $D=0$ on $N$; [F7] makes this finite representative measurable. Additivity [F8] and [F10] show that it has $\mathbb{E}D=\mathbb{E}{D}_0=L_{\mathrm{\Phi }}(h)-L_{\mathrm{\Phi }}^{\ast }$.

Fix $x$, write $a=\eta (x)$, and let $u$ be a real score satisfying $u(a-1\mathrm{/}2)\le 0$. For all real $u$, convexity gives $\mathrm{\Phi }(-u)+\mathrm{\Phi }(u)-2\mathrm{\Phi }(0)\ge 0$. If $a>1\mathrm{/}2$ then $u\le 0$, so monotonicity gives $\mathrm{\Phi }(-u)-\mathrm{\Phi }(u)\ge 0$; if $a<1\mathrm{/}2$ then $u\ge 0$, so $\mathrm{\Phi }(-u)-\mathrm{\Phi }(u)\le 0$. The identity $L_{\mathrm{\Phi }}(x,u)-L_{\mathrm{\Phi }}(x,0)=\frac{1}{2}[\mathrm{\Phi }(-u)+\mathrm{\Phi }(u)-2\mathrm{\Phi }(0)]+(a-\frac{1}{2})[\mathrm{\Phi }(-u)-\mathrm{\Phi }(u)]$ therefore shows $L_{\mathrm{\Phi }}(x,u)\ge L_{\mathrm{\Phi }}(x,0)$ whenever $a\mathrm{\ne }1\mathrm{/}2$ and $u(a-1\mathrm{/}2)\le 0$. When $a=1\mathrm{/}2$, the same identity has zero second term and proves $L_{\mathrm{\Phi }}(x,u)\ge L_{\mathrm{\Phi }}(x,0)$ for every $u$, so the conditional minimum is at $0$ and $g(x)=0$. Consequently, on $\{h(x)(a-1\mathrm{/}2)\le 0\}\setminus N$ one has $D(x)=D_0(x)\ge g(x)\ge 0$; the excluded set is null.

Almost surely on the event $h(X)(\eta (X)-1\mathrm{/}2)\le 0$, we are outside the null set $N$ from step 3.1, so the margin hypothesis and step 4.1 give $\mathrm{\mid }\eta (X)-1\mathrm{/}2{\mathrm{\mid }}^s\le cg(X)\le cD(X)$, hence $\mathrm{\mid }\eta (X)-1\mathrm{/}2\mathrm{\mid }\le c^{1\mathrm{/}s}D(X{)}^{1\mathrm{/}s}$. For nonnegative measurable integrands, [F8] and [F10] identify each full expectation with its integral on $N^c$; on that set the displayed inequality is pointwise, so monotonicity and positive-scalar homogeneity [F11] pass it to expectations and extract the factor $2c^{1\mathrm{/}s}$. Apply the exact excess identity [F6], bound its first integrand in this way, and use ${\mathbf{1}}_{\{h=0\}}\le 1$ to obtain $R_{01}(h)-R_{01}^{\ast }\le 2c^{1\mathrm{/}s}\mathbb{E}[D(X{)}^{1\mathrm{/}s}]+\mathbb{E}[\min \{\eta (X),1-\eta (X)\}{\mathbf{1}}_{\{h(X)=0\}}]\mathrm{.}$

Put $\alpha =1\mathrm{/}s\in (0,1]$. For $0\le t\le 1$, $t^{\alpha }\le 1$, while for $t\ge 1$, $t^{\alpha }\le t$; hence $D^{\alpha }\le 1+D$. Monotonicity [F11] and additivity [F8] give $\mathbb{E}[D^{\alpha }]\le \mathbb{E}[1+D]=1+\mathbb{E}D<\mathrm{\infty }$ by step 3.1, so $D^{\alpha }$ is integrable. By [F5], Jensen applied to the integrable convex function $-t^{\alpha }$ gives $\mathbb{E}[D^{1\mathrm{/}s}]\le (\mathbb{E}D{)}^{1\mathrm{/}s}=[L_{\mathrm{\Phi }}(h)-L_{\mathrm{\Phi }}^{\ast }{]}^{1\mathrm{/}s}$ by step 3.1. Substitution in step 5.1 proves the zero-score-is-error bound.

Under $P(h(X)=0)=0$ the correction has expectation zero. For the label classifier $f_h$, at each $x$ its conditional excess over $\min (\eta (x),1-\eta (x))$ is $2\mathrm{\mid }\eta (x)-1\mathrm{/}2\mathrm{\mid }$ on $\{h(x)<0,\eta (x)>1\mathrm{/}2\}\cup \{h(x)\ge 0,\eta (x)<1\mathrm{/}2\}$ and zero elsewhere. This follows by comparing the conditional error $\eta (x)$ for prediction $-1$ and $1-\eta (x)$ for prediction $+1$. This adverse-sign set is contained in the event of step 5.1, so steps 5.1 and 6.1 bound its expectation by $2c^{1\mathrm{/}s}[L_{\mathrm{\Phi }}(h)-L_{\mathrm{\Phi }}^{\ast }{]}^{1\mathrm{/}s}$ without a tie correction. Finally, replacing $c$ by $a^s$ makes $c^{1\mathrm{/}s}=a$ and proves the equivalent source parameterization.