Quantifying Learning Guarantees for Convex but Inconsistent Surrogates
We study consistency properties of machine learning methods based on minimizing convex surrogates. We extend the recent framework of Osokin et al. [14] for the quantitative analysis of consistency properties to the case of inconsistent surrogates. Our key technical contribution consists in a new lower bound on the calibration function for the quadratic surrogate, which is non-trivial (not always zero) for inconsistent cases. The new bound allows to quantify the level of inconsistency of the setting and shows how learning with inconsistent surrogates can have guarantees on sample complexity and optimization difficulty. We apply our theory to two concrete cases: multi-class classification with the tree-structured loss and ranking with the mean average precision loss. The results show the approximation-computation trade-offs caused by inconsistent surrogates and their potential benefits.
Summary  The paper provides a new lower bound in consistency analysis of convex surrogate loss functions. Section 1 provides an introduction which discusses previous work and contributions. The main previous work is Osokin et al, which is frequently referenced in the text. The main contribution is a generalization of the results of Osokin et al to inconsistent surrogates, and a new tighter lower bound. An additional contribution is a study the behavior of the proposed bound for two prediction problems.  Section 2 provides definitions of the task loss and surrogate loss, while section 3 defines the calibration function which links them. The concept of level-eta consistency is defined. Level-0 consistency is the same as Fisher consistency, whereas with eta>0 "the surrogate is not consistent meaning that the actual risk cannot be minimized globally." Section 4 provides a new lower bound, with discussion that clarifies how the paper is novel wrt previous work. Section 5 analyzes the bounds in two problem settings: multi-class classification with tree-structured loss and ranking with mean average precision loss. Section 6 provides a discussion and conclusion.  Pros: - frequent references to previous work which help clarify the novelty. - new proof technique and lower bound. - results include a comparison with previous work (Figure 1b) in order to show a visual example of how the previous bound is trivial and the proposed bound is tighter.  Cons: - no clear discussion of how the analysis may lead to new loss functions or efficient learning algorithms.