On Structured Prediction Theory with Calibrated Convex Surrogate Losses

By Anton Osokin, Francis R. Bach, Simon Lacoste-Julien. 2017

67 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Quantifying Learning Guarantees for Convex but Inconsistent Surrogates (2018, methodology): “[14] for the quantitative analysis of consistency properties to the case of inconsistent surrogates.”
Learning with SGD and Random Features (2018, methodology): “Moreover, (d) we can apply the proposed method in the more general context of least squares frameworks for multitask learning [43, 44] or structured prediction [45, 46, 47], with the goal of obtaining faster algorithms, while retaining strong statistical guarantees.”
Exponential convergence of testing error for stochastic gradient methods (2017, unknown): “…other losses, such as the logistic or hinge loss; (b) going beyond binary classiﬁcation is also natural with the square loss (Ciliberto et al., 2016; Osokin et al., 2017) or without (Taskar et al., 2005); (c) in our experiments, we use regularization, but we have experimented with unregularized…”
Parametric Adversarial Divergences are Good Task Losses for Generative Modeling (2017, background): “The theoretical results proved by Osokin et al. (2017) formalize that intuition in a specific setting.”
Smart "Predict, then Optimize" (2017, unknown): “Finally, we note that our framework is related to the general setting of structured prediction (see, e.g., Osokin et al. (2017), Goh and Jaillet (2016) and the references therein).”
On the Consistency of Ordinal Regression Methods (2014, background): “, 2012), structured prediction (Ciliberto et al., 2016; Osokin et al., 2017) and multiclass classification with an arbitrary loss function (Ramaswamy and Agarwal, 2012, 2016), a setting that subsumes ordinal regression.”
Cross-Entropy Loss Functions: Theoretical Analysis and Applications (2023, background): “, 2013; Pires & Szepesvári, 2016), structured prediction (Ciliberto et al., 2016; Osokin et al., 2017; Blondel, 2019), top-k classification (Thilagar et al.”