The Structured Abstain Problem and the Lov\'asz Hinge
  The Lov\'asz hinge is a convex surrogate recently proposed for structured
binary classification, in which $k$ binary predictions are made simultaneously
and the error is judged by a submodular set function. Despite its wide usage in
image segmentation and related problems, its consistency has remained open. We
resolve this open question, showing that the Lov\'asz hinge is inconsistent for
its desired target unless the set function is modular. Leveraging a recent
embedding framework, we instead derive the target loss for which the Lov\'asz
hinge is consistent. This target, which we call the structured abstain problem,
allows one to abstain on any subset of the $k$ predictions. We derive two link
functions, each of which are consistent for all submodular set functions
simultaneously.
