A General Theory for Structured Prediction with Smooth Convex Surrogates

Abstract

In this work we provide a theoretical framework for structured prediction that generalizes the existing theory of surrogate methods for binary and multiclass classification based on estimating conditional probabilities with smooth convex surrogates (e.g. logistic regression). The theory relies on a natural characterization of structural properties of the task loss and allows to derive statistical guarantees for many widely used methods in the context of multilabeling, ranking, ordinal regression and graph matching. In particular, we characterize the smooth convex surrogates compatible with a given task loss in terms of a suitable Bregman divergence composed with a link function. This allows to derive tight bounds for the calibration function and to obtain novel results on existing surrogate frameworks for structured prediction such as conditional random fields and quadratic surrogates.

References in corpus (9)

• Fast learning rates for plug-in classifiers
• Estimating conditional quantiles with the help of the pinball loss
• Composite Binary Losses
• A Consistent Regularization Approach for Structured Prediction
• Exponential Family Graph Matching and Ranking
• Consistent Algorithms for Multiclass Classification with a Reject Option
• Exponential convergence of testing error for stochastic gradient methods
• On Structured Prediction Theory with Calibrated Convex Surrogate Losses
• Learning with Fenchel-Young Losses

Cited by in corpus (5)

• Learning with Fenchel-Young Losses
• Lower-Bounded Proper Losses for Weakly Supervised Classification
• Fast rates in structured prediction
• Learning Output Embeddings in Structured Prediction
• Surrogate Regret Bounds for Polyhedral Losses