On Structured Prediction Theory with Calibrated Convex Surrogate Losses
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 general structured prediction.
Code (1)
Tasks
PredictionStructured PredictionSimilar Papers 제목 키워드 기반
A General Theory for Structured Prediction with Smooth Convex Surrogates
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 w…
General ClassificationGraph MatchingregressionStructured PredictionConvex Calibrated Surrogates for Low-Rank Loss Matrices with Applications to Subset Ranking Losses
The design of convex, calibrated surrogate losses, whose minimization entails consistency with respect to a desired target loss, is an important concept to have emerged in the theory of machine learning in recent years. …
Convex Calibration Dimension for Multiclass Loss Matrices
We study consistency properties of surrogate loss functions for general multiclass learning problems, defined by a general multiclass loss matrix. We extend the notion of classification calibration, which has been studie…
General ClassificationStructured Prediction with Projection Oracles
We propose in this paper a general framework for deriving loss functions for structured prediction. In our framework, the user chooses a convex set including the output space and provides an oracle for projecting onto th…
PredictionStructured PredictionCalibrated Surrogate Losses for Adversarially Robust Classification
Adversarially robust classification seeks a classifier that is insensitive to adversarial perturbations of test patterns. This problem is often formulated via a minimax objective, where the target loss is the worst-case …
ClassificationGeneral ClassificationRobust classification