$\mathscr{H}$-Consistency Estimation Error of Surrogate Loss Minimizers
We present a detailed study of estimation errors in terms of surrogate loss
estimation errors. We refer to such guarantees as $\mathscr{H}$-consistency
estimation error bounds, since they account for the hypothesis set
$\mathscr{H}$ adopted. These guarantees are significantly stronger than
$\mathscr{H}$-calibration or $\mathscr{H}$-consistency. They are also more
informative than similar excess error bounds derived in the literature, when
$\mathscr{H}$ is the family of all measurable functions. We prove general
theorems providing such guarantees, for both the distribution-dependent and
distribution-independent settings. We show that our bounds are tight, modulo a
convexity assumption. We also show that previous excess error bounds can be
recovered as special cases of our general results.
  We then present a series of explicit bounds in the case of the zero-one loss,
with multiple choices of the surrogate loss and for both the family of linear
functions and neural networks with one hidden-layer. We further prove more
favorable distribution-dependent guarantees in that case. We also present a
series of explicit bounds in the case of the adversarial loss, with surrogate
losses based on the supremum of the $\rho$-margin, hinge or sigmoid loss and
for the same two general hypothesis sets. Here too, we prove several
enhancements of these guarantees under natural distributional assumptions.
Finally, we report the results of simulations illustrating our bounds and their
tightness.