Skip to yearly menu bar Skip to main content


Structured Prediction with Stronger Consistency Guarantees

Anqi Mao · Mehryar Mohri · Yutao Zhong

Great Hall & Hall B1+B2 (level 1) #1810
[ ]
Wed 13 Dec 3 p.m. PST — 5 p.m. PST

Abstract: We present an extensive study of surrogate losses for structured prediction supported by *$H$-consistency bounds*. These are recently introduced guarantees that are more relevant to learning than Bayes-consistency, since they are not asymptotic and since they take into account the hypothesis set $H$ used. We first show that no non-trivial $H$-consistency bound can be derived for widely used surrogate structured prediction losses. We then define several new families of surrogate losses, including *structured comp-sum losses* and *structured constrained losses*, for which we prove $H$-consistency bounds and thus Bayes-consistency. These loss functions readily lead to new structured prediction algorithms with stronger theoretical guarantees, based on their minimization. We describe efficient algorithms for minimizing several of these surrogate losses, including a new *structured logistic loss*.

Chat is not available.