We provide novel theoretical insights on structured prediction in the context of efficient convex surrogate loss minimization with consistency guarantees. For any task loss, we construct a convex surrogate that can be optimized via stochastic gradient descent and we prove tight bounds on the so-called "calibration function" relating the excess surrogate risk to the actual risk. In contrast to prior related work, we carefully monitor the effect of the exponential number of classes in the learning guarantees as well as on the optimization complexity. As an interesting consequence, we formalize the intuition that some task losses make learning harder than others, and that the classical 0-1 loss is ill-suited for structured prediction. Structured prediction is a subfield of machine learning aiming at making multiple interrelated predictions simultaneously. The desired outputs (labels) are typically organized in some structured object such as a sequence, a graph, an image, etc. Tasks of this type appear in many practical domains such as computer vision [31] , natural language processing [38] and bioinformatics [17] . The structured prediction setup has at least two typical properties differentiating it from the classical binary classification problems extensively studied in learning theory: 1. Exponential number of classes: this brings both additional computational and statistical challenges. By exponential, we mean exponentially large in the size of the natural dimension of output, e.g., the number of all possible sequences is exponential w.r.t. the sequence length. 2. Cost-sensitive learning: in typical applications, prediction mistakes are not all equally costly. The prediction error is usually measured with a highly-structured task-specific loss function, e.g., Hamming distance between sequences of multi-label variables or mean average precision for ranking. Despite many algorithmic advances to tackle structured prediction problems [3, 32] , there have been relatively few papers devoted to its theoretical understanding. Notable recent exceptions that made significant progress include Cortes et al. [12] and London et al. [25] (see references therein) which proposed data-dependent generalization error bounds in terms of popular empirical convex surrogate losses such as the structured hinge loss [40, 41, 43] . A question not addressed by these works is whether their algorithms are consistent: does minimizing their convex bounds with infinite data lead to the minimization of the task loss as well? Alternatively, the structured probit and ramp losses are consistent [28, 27] , but non-convex and thus it is hard to obtain computational guarantees for them. In this paper, we aim at getting the property of consistency for surrogate losses that can be efficiently minimized with guarantees, and thus we consider convex surrogate losses. The consistency of convex surrogates is well understood in the case of binary classification [46, 4, 39] and there is significant progress in the case of multi-class 0-1 loss [45, 42] and general loss
Osokin et al. REF consider structured prediction with convex surrogate losses for decompose multiclass classification metrics (i.e. metrics that can be expressed as an average over samples).
On Structured Prediction Theory with Calibrated Convex Surrogate Losses
ArXiv
ArXiv
Computer Science Mathematics