Multi-Class $H$-Consistency Bounds

We present an extensive study of H -consistency bounds for multi-class classification. These are upper bounds on the target loss estimation error of a predictor in a hypothesis set H , expressed in terms of the surrogate loss estimation error of that predictor. They are stronger and more significant guarantees than Bayes-consistency, H -calibration or H -consistency, and more informative than excess error bounds derived for H being the family of all measurable functions. We give a series of new H -consistency bounds for surrogate multi-class losses, including max losses, sum losses, and constrained losses, both in the non-adversarial and adversarial cases, and for different differentiable or convex auxiliary functions used. We also prove that no non-trivial H -consistency bound can be given in some cases. To our knowledge, these are the first H -consistency bounds proven for the multi-class setting. Our proof techniques are also novel and likely to be useful in the analysis of other such guarantees.