A Consistent Regularization Approach for Structured Prediction

By Carlo Ciliberto, Lorenzo Rosasco, Alessandro Rudi. 2016

86 citations recorded by the source corpus.

We propose and analyze a regularization approach for structured prediction problems. We characterize a large class of loss functions that allows to naturally embed structured outputs in a linear space. We exploit this fact to design learning algorithms using a surrogate loss approach and regularization techniques. We prove universal consistency and finite sample bounds characterizing the generalization properties of the proposed methods. Experimental results are provided to demonstrate the practical usefulness of the proposed approach.

Subfields: Computational Mechanics, Control and Systems Engineering, Natural Language Processing

How researchers see this paper

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

In Computational Mechanics

In Control and Systems Engineering

In Natural Language Processing

Citations in the corpus

Quantifying Learning Guarantees for Convex but Inconsistent Surrogates (2018, background): “Consistency of convex surrogates has been the central question of many studies for such problems as binary classification [2, 24, 19], multi-class classification [23, 21, 1, 17], ranking [11, 4, 5, 18, 15] and, more recently, structured prediction [7, 14].”
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.”
Exponential convergence of testing error for stochastic gradient methods (2017, unknown): “…natural to extend it to 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…”
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.”
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.”